[PYTHON] J'ai résolu le problème le plus profond d'Hiroshi Yuki.

J'ai résolu le problème le plus profond d'Hiroshi Yuki.

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

Évaluation 5 Badge Kitakore!

https://codeiq.jp/achievement/34

Comment résoudre

・ Ce n'était pas un problème pour trouver l'itinéraire le plus court ・ En raison de la nature du problème de recherche du prochain vol direct à l'aide de WebAPI, nous prévoyons qu'un grand nombre de branches se cachent et effectuons la taille suivante.

• Dans la recherche de priorité de largeur, le nombre de branches à partir d'un point peut atteindre 100
• Ne permettez pas aux étoiles déjà trouvées dans d'autres chemins de recherche de passer deux fois. ・ À propos, la carte des vols directs doit être mise en cache sous forme de fichier.

Ce que j'ai fait était vraiment 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()