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.

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()

Recommended Posts

I solved the deepest problem of Hiroshi Yuki.
I tried face recognition of the laughter problem using Keras.
I investigated the mechanism of flask-login!
Illustration of the results of the knapsack problem
I checked the contents of docker volume
I tried the asynchronous server of Django 3.0
I checked the options of copyMakeBorder of OpenCV
I summarized the folder structure of Flask
I didn't know the basics of Python
Python: I tried the traveling salesman problem
The Python project template I think of.
I read the implementation of golang channel
I tried the pivot table function of pandas
I read the implementation of range (Objects / rangeobject.c)
2016 The University of Tokyo Mathematics Solved with Python
I checked the list of shortcut keys of Jupyter
I tried to touch the API of ebay
I tried to correct the keystone of the image
Try the free version of Progate [Python I]
I checked the session retention period of django
I checked the processing speed of numpy one-dimensionalization
[At Coder] Solve the problem of binary search
I touched some of the new features of Python 3.8 ①
I read and implemented the Variants of UKR
I want to customize the appearance of zabbix
I tried using the image filter of OpenCV
I tried to implement the traveling salesman problem
I tried to predict the price of ETF
I tried to vectorize the lyrics of Hinatazaka46!
Solved the problem that MacVim installed by Homebrew was not built by python of pyenv
[Probability] I will explain because the robot problem of Center 2020 Mathematics 1 ・ A was interesting.
I ran the TensorFlow tutorial with comments (first neural network: the beginning of the classification problem)
The 15th offline real-time I tried to solve the problem of how to write with python
[Trainer's Recipe] I touched the flame of the Python framework.
I tried to summarize the basic form of GPLVM
I tried the MNIST tutorial for beginners of tensorflow.
I followed the implementation of the du command (first half)
I compared the identity of the images by Hu moment
Maybe I overestimated the impact of ShellShock on CGI
I checked the output specifications of PyTorch's Bidirectional LSTM
I checked out the versions of Blender and Python
I want to fully understand the basics of Bokeh
The performance of PHP was better than I expected
I examined the argument class_weight of Chainer's softmax_cross_entropy function.
python chrome driver ver. Solving the problem of difference
I measured the performance of 1 million documents with mongoDB
I checked the default OS and shell of docker-machine
I followed the implementation of the du command (second half)
I tried using the API of the salmon data project
I tried to visualize the spacha information of VTuber
I tried to erase the negative part of Meros
I tried to solve the problem with Python Vol.1
I tried scraping the advertisement of the pirated cartoon site
Zip 4 Gbyte problem is a story of the past
I investigated the reinforcement learning algorithm of algorithmic trading
I tried the simplest method of multi-label document classification
Animate the basics of dynamic programming and the knapsack problem
I tried to classify the voices of voice actors
I want to increase the security of ssh connections
I searched for the contents of CloudWatch Logs Agent
I tried running the sample code of the Ansible module