My Advent of Code solutions in Python.
kevinyap.ca/2019/12/going-fast-in-advent-of-code/
advent-of-code
python
1import fileinput
2from functools import cache
3
4def bfs(start):
5 """Returns the number of splits from `start`."""
6 splits = 0
7 horizon = [start]
8 seen = set()
9 while horizon:
10 p = horizon.pop()
11 if p in seen:
12 continue
13 if p not in BOARD:
14 continue
15
16 seen.add(p)
17 x, y = p
18
19 if BOARD[p] == '^':
20 splits += 1
21 horizon.append((x - 1, y))
22 horizon.append((x + 1, y))
23 else:
24 horizon.append((x, y + 1))
25
26 return splits
27
28
29@cache
30def dp(pos):
31 """Returns the number of ways a tachyon travels from x, y"""
32 x, y = pos
33 if pos not in BOARD:
34 return 1
35
36 if BOARD[pos] == '^':
37 return dp((x - 1, y)) + dp((x + 1, y))
38
39 return dp((x, y + 1))
40
41
42# Parse problem input.
43BOARD = {}
44START = None
45for y, line in enumerate(fileinput.input()):
46 for x, c in enumerate(line.strip()):
47 BOARD[x, y] = c
48 if c == 'S':
49 START = (x, y)
50
51
52# Solve problem.
53print("Part 1:", bfs(START))
54print("Part 2:", dp(START))