1  from lib import *
 2  
 3  input = read_input(2016, 24)
 4  
 5  
 6  grid = input.splitlines()
 7  
 8  nodes = {}
 9  
10  rnodes = {}
11  
12  for i, line in enumerate(grid):
13      for j, c in enumerate(line):
14          if c.isnumeric():
15              nodes[int(c)] = j, i
16  
17              rnodes[(j, i)] = int(c)
18  
19  
20  def asp(x, y):
21      queue = [(0, x, y)]
22  
23      out = {}
24  
25      visited = set()
26  
27      while queue:
28          d, x, y = queue.pop(0)
29  
30          if (x, y) in visited:
31              continue
32  
33          visited.add((x, y))
34  
35          if (x, y) in rnodes:
36              out[rnodes[(x, y)]] = d
37  
38          for p, q in [(x, y - 1), (x, y + 1), (x - 1, y), (x + 1, y)]:
39              if p not in range(len(grid[0])) or q not in range(len(grid)) or grid[q][p] == "#":
40                  continue
41  
42              queue.append((d + 1, p, q))
43  
44      return out
45  
46  
47  sp = {k: asp(*v) for k, v in nodes.items()}
48  
49  best = 1e1337
50  
51  for order in itertools.permutations(set(sp) - {0}):
52      pos = 0
53  
54      cost = 0
55  
56      for x in order:
57          cost += sp[pos][x]
58  
59          pos = x
60  
61      best = min(best, cost)
62  
63  print(best)
64  
65  
66  best = 1e1337
67  
68  for order in itertools.permutations(set(sp) - {0}):
69      pos = 0
70  
71      cost = 0
72  
73      for x in order:
74          cost += sp[pos][x]
75  
76          pos = x
77  
78      best = min(best, cost + sp[pos][0])
79  
80  print(best)