My Advent of Code solutions in Python.
kevinyap.ca/2019/12/going-fast-in-advent-of-code/
advent-of-code
python
1import fileinput
2from collections import defaultdict
3from utils import Point, DIRS_4
4
5
6REGEX = fileinput.input()[0].strip().replace('$', '').replace('^', '')
7DIRS = {a: b for a, b in zip('NESW', DIRS_4)}
8
9# Build graph of facility
10graph = defaultdict(set)
11start = Point(0, 0)
12curr = start
13stk = []
14
15for d in REGEX:
16 if d in DIRS:
17 nx = curr + DIRS[d]
18 graph[curr].add(nx)
19 graph[nx].add(curr)
20 curr = nx
21 elif d == '(':
22 stk.append(curr)
23 elif d == '|':
24 curr = stk[-1]
25 elif d == ')':
26 curr = stk.pop()
27
28seen = set()
29horizon = [start]
30dist = {}
31
32# BFS to solve for minimum distances to rooms
33depth = 0
34while horizon:
35 next_horizon = []
36
37 for h in horizon:
38 if h in seen:
39 continue
40
41 dist[h] = depth
42 seen.add(h)
43
44 for g in graph[h]:
45 next_horizon.append(g)
46
47 depth += 1
48 horizon = next_horizon
49
50
51print "Largest number of doors passed through:", max(d for d in dist.values())
52print "Rooms passing through at least 1000 doors:", sum(d >= 1000 for d in dist.values())