My Advent of Code solutions in Python.
kevinyap.ca/2019/12/going-fast-in-advent-of-code/
advent-of-code
python
1import fileinput
2from string import ascii_uppercase, ascii_lowercase
3from collections import defaultdict, deque
4from heapq import heappush, heappop
5
6from utils import Point
7
8
9BOARD = defaultdict(lambda: '#')
10KEYS = {}
11DOORS = {}
12
13ent = None
14
15for i, line in enumerate(fileinput.input()):
16 for x, c in enumerate(line.strip()):
17 BOARD[Point(x, i)] = c
18 if c == '@':
19 ent = Point(x, i)
20
21 if c in ascii_lowercase:
22 KEYS[c] = Point(x, i)
23
24 if c in ascii_uppercase:
25 DOORS[c] = Point(x, i)
26
27NUM_KEYS = len(KEYS)
28
29
30def part_1(start):
31 horizon = [(start, frozenset())]
32 seen = set()
33
34 level = 0
35 while horizon:
36 new_horizon = []
37
38 for p, k in horizon:
39 for np in p.neighbours_4():
40 if (np, k) in seen:
41 continue
42
43 if BOARD[np] != '#':
44 c = BOARD[np]
45
46 if c in DOORS and c.lower() not in k:
47 continue
48
49 if c in KEYS:
50 if c in k:
51 state = (np, k)
52 else:
53 state = (np, k | set([c]))
54 # print state
55
56 if len(state[1]) == NUM_KEYS:
57 return level + 1
58
59 new_horizon.append(state)
60 seen.add(state)
61 else:
62 new_horizon.append((np, k))
63 seen.add((np, k))
64
65 # print "yes"
66
67 horizon = new_horizon
68 level += 1
69
70print "Minimal steps for Part 1:", part_1(ent)
71
72# Manual maze replacement for Part 2
73ents = []
74
75for np in ent.neighbours_8():
76 if np.dist_manhattan(ent) == 2:
77 ents.append(np)
78 BOARD[np] = '@'
79 else:
80 BOARD[np] = '#'
81
82BOARD[ent] = '#'
83
84points = KEYS
85for i, ent in enumerate(ents):
86 points[str(i)] = ent
87# print points
88
89# Preprocess graph to determine distances from each key to each other key
90# Edges are represented as start_pos: (steps, new_key, doors_passed).
91graph = defaultdict(list)
92
93for i, node in enumerate(points):
94 # BFS from start pos to each key in quadrant
95 # state is (pos, doors_passed)
96 level = 1
97 horizon = [(points[node], frozenset())]
98 seen = set()
99 while horizon:
100 new_horizon = []
101 for pos, doors in horizon:
102 for np in pos.neighbours_4():
103 if (np, doors) in seen:
104 continue
105
106 if BOARD[np] == '#':
107 continue
108
109 tile = BOARD[np]
110 ndoors = doors
111 if tile in ascii_uppercase:
112 ndoors |= set([tile.lower()])
113
114 if tile in ascii_lowercase and tile != node:
115 graph[node].append((level, tile, ndoors))
116 seen.add((np, ndoors))
117 continue
118
119 new_horizon.append((np, ndoors))
120 seen.add((np, ndoors))
121
122 horizon = new_horizon
123 level += 1
124
125heap = [(0, '0', '1', '2', '3', frozenset())]
126seen = set()
127
128while heap:
129 steps, a, b, c, d, keys = heappop(heap)
130
131 if len(keys) == NUM_KEYS:
132 print "Minimal steps for Part 2:", steps
133 break
134
135 for i, p in enumerate((a, b, c, d), start=1):
136 for ns, np, nd in graph[p]:
137 if not keys.issuperset(nd):
138 continue
139
140 next_state = [steps + ns, a, b, c, d, keys | set([np])]
141
142 next_state[i] = np
143 next_state = tuple(next_state)
144 if next_state[1:] in seen:
145 continue
146
147 seen.add(next_state[1:])
148 heappush(heap, next_state)