Created
June 19, 2016 05:07
-
-
Save matts1/94f6c1e969370256f1cfb7d92ab1db79 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# create a new city (the 0th city), and set distance to every other city to be 0 | |
from copy import deepcopy | |
def memoize(fn): | |
CACHE = {} | |
def newfn(*args): | |
if tuple(args) not in CACHE: | |
CACHE[tuple(args)] = fn(*args) | |
return CACHE[tuple(args)] | |
return newfn | |
@memoize | |
def best(first, second): | |
if first == 0 and second == 1: return (0, set(), set([1])) | |
low = (float('inf'), set(), set()) | |
check = [(i, second) for i in range(first)] | |
if first != second - 1: | |
check.append(first, second - 1) | |
for oldfirst, oldsecond in check: | |
dist, firstset, secondset = best(*sorted(oldfirst, oldsecond)) | |
if oldfirst != first: dist += distances[oldfirst][first] | |
if oldsecond != second: dist += distances[oldsecond][second] | |
if dist < low[0]: | |
low = (dist, deepcopy(firstset), deepcopy(secondset)) | |
return low | |
print(min([best(i, n) for i in range(n)])[0]) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment