[PYTHON] I solved the deepest problem of Hiroshi Yuki.

I solved the deepest problem of Hiroshi Yuki.

https://codeiq.jp/ace/yuki_hiroshi/q411

Rating 5 Badge Kitakore!

https://codeiq.jp/achievement/34

How to solve

・ It was not a problem to find the shortest path ・ Due to the nature of the problem of finding the next direct flight using WebAPI, we anticipate that a large number of branches are lurking and carry out the following pruning.

• In breadth-first search, the number of branches from one point is up to 100
• Do not allow stars already found in other search paths to pass twice. ・ In addition, the map of the direct flight should be cached as a file.

What I did was really simple.

code

star-flight.py

'''
Created on 2013/07/31

@author: nubilum
'''
import urllib2
import time
import os.path

limit   = 5
start   = 5426528869786
deep    = 4363616111476
deeper  = 5092488161056
deepest = 8838746292440
goal_points  = [start, deep, deeper, deepest]
cache_path   = 'cache.txt'
cache = {}
already = {}

def search(start, goal):
    global cache
    global already
    load_cache()
    now = start
    queue = []
    idx = 0
    counter = 0
    queue.append([[start]])
    while True:
        current = []
        routes_list = queue[idx]
        for routes in routes_list:
            print routes
            last = routes[-1]
            if last in cache:
                pathes = cache[last]
                for path in pathes:
                    if path == 0:
                        break
                    if path in already:
                        continue
                    already[path] = 1
                    next = routes[:]
                    next.append(path)
                    current.append(next)
                    if path == goal:
                        return next
            else:
                next_pathes = []
                for i in xrange(0, 100):
                    response = get_response(last, i)
                    counter += 1
                    if response == 0:
                        break
                    if response in already:
                        continue
                    already[response] = 1
                    next_pathes.append(response)
                    next = routes[:]
                    next.append(response)
                    current.append(next)
                    if response == goal:
                        return next
                    if counter % limit == 0:
                        time.sleep(0.1)
                write_cache(last, next_pathes)
        now = next
        queue.append(current)
        idx += 1

def write_cache(start, path):
    global cache_path
    f = open(cache_path, "a")
    f.write(str(start) + ":" + ','.join([ str(p) for p in path ]) + "\n")
    f.close()

def load_cache():
    global cache
    global cache_path
    if os.path.exists(cache_path) ==False:
        return
    f = open(cache_path, "r")
    data = f.read()
    f.close()
    for line in data.split('\n'):
        if line == '': continue
        start, path  = line.split(':')
        cache[int(start)] = [int(p) if len(p) > 0 else 0 for p in path.split(',')]

def get_response(id, nth):
    response = urllib2.urlopen('http://133.242.134.37/deepest.cgi?id=%d&nth=%d' % (id, nth))
    return int(response.read().rstrip('rn'))

def main():
    global goal_points
    result = []
    for i in xrange(0, len(goal_points) - 1):
        answer_routes = search(goal_points[i], goal_points[i + 1])
        print "answer:", answer_routes
        for point in answer_routes:
            result.append(point)
    print ",".join([str(p) for p in result])
    print "ENV: Python"

if __name__ == '__main__':
    main()