blob: d082678e11abee4f549c03bfa3fdfaf46d6ff3bc (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
|
#!/usr/bin/python
from itertools import permutations
def parse_input(lines):
edges = {}
for line in lines:
words = line.split()
x = words[0]
y = words[2]
d = int(words[4])
if x not in edges:
edges[x] = {}
if y not in edges:
edges[y] = {}
edges[x][y] = d
edges[y][x] = d
return edges
def solve_partn(partn, lines):
edges = parse_input(lines)
nodes = list(edges.keys())
# This is simply the famous travelling salesman problem,
# so exhaustively trying all routes is the only solution.
routes = permutations(nodes)
totals = []
for r in routes:
t = 0
for i in range(len(r) - 1):
t += edges[r[i]][r[i + 1]]
totals.append(t)
if partn == 1:
return min(totals)
else: # partn == 2
return max(totals)
def main():
# Read distances (graph edges) from input text file
with open("input.txt", "r") as f:
lines = f.read().splitlines()
print("Part 1 solution:", solve_partn(1, lines)) # 207 for me
print("Part 2 solution:", solve_partn(2, lines)) # 804 for me
if __name__ == "__main__":
main()
|
