Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Memoization - educational solution in Uncategorized category for Disposable Teleports by macobo
# migrated from python 2.7
from collections import defaultdict
# While unneccesary for this task, if there would be more
# than 8 teleports, most time would be spent on recomputation
# of similar states. (There are many ways to arrive at a station
# by using the same teleports, just in different order).
# To avoid that, let's make a memory tradeoff and try to
# save already computed states and use those results when
# we arrive at the same state the second time.
#
# This techinque is called memoization in Dynamic Programming.
def memoize(f):
""" This is a decorator, that saves each call to a function
into a hash table. If the function is called a second time
with the same arguments, the previous result is returned """
cache = {}
def g(*args):
if args not in cache:
cache[args] = f(*args)
return cache[args]
return g
def available_routes(frm, all_routes, used):
is_used = lambda to: (frm, to) in used or (to, frm) in used
return [to for to in all_routes[frm] if not is_used(to)]
def checkio(teleports_string):
@memoize
def recurse(at, visited, used_routes):
routes = available_routes(at, all_routes, used_routes)
if "1" in routes and len(visited) == 8:
return "1"
for to in routes:
new_routes = used_routes | frozenset([(at, to)])
solution = recurse(to, visited | frozenset([to]), new_routes)
if solution:
return to + solution
all_routes = defaultdict(set)
for pair in teleports_string.split(","):
all_routes[pair[0]].add(pair[1])
all_routes[pair[1]].add(pair[0])
return "1" + recurse("1", frozenset("1"), frozenset())
if __name__ == "__main__":
print((checkio("12,23,34,45,56,67,78,81"))) #"123456781"
print((checkio("12,28,87,71,13,14,34,35,45,46,63,65"))) #"1365417821"
print((checkio("12,15,16,23,24,28,83,85,86,87,71,74,56"))) #"12382478561"
print((checkio("13,14,23,25,34,35,47,56,58,76,68"))) #"132586741"
April 27, 2013
Comments:
