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, Counter, deque
3from itertools import count
4
5from utils import mul
6
7
8# Parse problem input.
9broadcaster = []
10flip_flops = defaultdict(list)
11conjunctions = defaultdict(list)
12graph = defaultdict(list)
13
14for line in fileinput.input():
15 line = line.strip()
16 if line.startswith('broadcaster'):
17 outputs = line.split(' -> ')[1]
18 for out in outputs.split(', '):
19 broadcaster.append(out)
20
21 elif line.startswith('%'):
22 mod, outputs = line.split(' -> ')
23 mod = mod[1:]
24 for out in outputs.split(', '):
25 flip_flops[mod].append(out)
26 graph[out].append(mod)
27
28 elif line.startswith('&'):
29 mod, outputs = line.split(' -> ')
30 mod = mod[1:]
31 for out in outputs.split(', '):
32 conjunctions[mod].append(out)
33 graph[out].append(mod)
34
35
36def press_button(state):
37 # Start the cycle with the broadcaster receiving a
38 # low pulse from the button.
39 horizon = deque([('broadcaster', False, 'button')])
40
41 while horizon:
42 dst, pulse, frm = horizon.popleft()
43
44 # Output all pulses to be examined.
45 yield dst, pulse
46
47 if dst == 'broadcaster':
48 for r in broadcaster:
49 horizon.append((r, pulse, dst))
50
51 elif dst in flip_flops:
52 # If a flip-flop receives a high pulse, do nothing.
53 if pulse is True:
54 continue
55
56 # Invert the state of the flip-flop.
57 STATE[dst] = not STATE[dst]
58
59 # Broadcast the new state to all output modules.
60 for r in flip_flops[dst]:
61 horizon.append((r, STATE[dst], dst))
62
63 elif dst in conjunctions:
64 # Set memory of this pulse.
65 STATE[dst][frm] = pulse
66
67 # If memory is all high pulses...
68 for inp, mem in STATE[dst].items():
69 if not mem:
70 break
71 else:
72 # ...send a low pulse to all output modules.
73 for r in conjunctions[dst]:
74 horizon.append((r, False, dst))
75
76 continue
77
78 # Otherwise, send a high pulse to all output modules.
79 for r in conjunctions[dst]:
80 horizon.append((r, True, dst))
81
82
83# Solve problem.
84STATE = {k: False for k in flip_flops}
85
86for mod in conjunctions:
87 STATE[mod] = {inp: False for inp in graph[mod]}
88
89# Need to find the aligned cycle of the four modules that
90# feed into conjunction X, where X feeds into `rx`.
91key_regs = graph[graph['rx'][0]]
92cycle_lens = {mod: -1 for mod in key_regs}
93
94pulse_counts = Counter()
95
96for cycle in count(start=1):
97 for module, pulse in press_button(STATE):
98 if pulse is False and cycle_lens.get(module) == -1:
99 cycle_lens[module] = cycle
100
101 if cycle <= 1000:
102 pulse_counts[pulse] += 1
103
104 if all(v != -1 for v in cycle_lens.values()):
105 break
106
107print("Part 1:", mul(pulse_counts.values()))
108print("Part 2:", mul(cycle_lens.values()))