Time for an esoteric one. Day 20 has you model the behavior of a circuit board. A broadcaster sends a low pulse along a wire toward several modules. Each is either a flip-flop (which toggle between off and on when they receive a low pulse) and conjunction modules (which track the most recent type of pulse received in each of their inputs, and sends a low pulse if all are high and a high pulse if all are low).
Part 1 asks you to multiply the total numbers of low and high pulses sent after 1000 pulses are broadcast. This takes some tricky programming to model the network, but nothing too demanding.
Part 2 instead asks how many pulses it will take before a single low pulse is sent to module rx. As you might expect, a general solution is hopeless; the answer is too big. Instead, as the subreddit revealed, the input contains several hidden bit counters. By examining the structure of each, you can read binary numbers equal to their period lengths. Multiplying these gives the answer.
```{python}
from collections import defaultdict
from collections import deque
from math import prod
from utils.utils import split_lines
class Module():
def __init__(self, name, inputs, outputs):
self.name = name
self.inputs = inputs
self.outputs = outputs
class Broadcaster(Module):
def receive(self, _, pulse):
return pulse
class FlipFlop(Module):
def __init__(self, *args, **kwargs):
super().__init__(*args, **kwargs)
self.on = False
def receive(self, _, pulse):
if pulse:
return
self.on = not self.on
return self.on
class Conjunction(Module):
def __init__(self, *args, **kwargs):
super().__init__(*args, **kwargs)
self.inputs = {i : False for i in self.inputs}
self.n_inputs = len(self.inputs)
def receive(self, name, pulse):
self.inputs[name] = pulse
return sum(self.inputs.values()) != self.n_inputs
def __repr__(self):
return str(self.inputs)
def parse(lines):
inputs = defaultdict(list)
data = []
end = None
for line in lines:
name, outputs = line.split(" -> ")
kind = FlipFlop if name[0] == "%" else Conjunction if name[0] == "&" else Broadcaster
name = name.lstrip("&%")
outputs = outputs.split(", ")
if outputs == ["rx"]:
end = name
for o in outputs:
inputs[o].append(name)
data.append((name, kind , outputs))
return {t[0] : t[1](t[0], inputs[t[0]], t[2]) for t in data}, end
def pulse(data, iterations):
low = iterations
high = 0
for _ in range(iterations):
# Only one set of pulses in queue at once
queue = deque([ ("broadcaster", "", False) ])
while queue:
new = deque()
while queue:
target, source, pulse = queue.popleft()
outputs = data[target].outputs
kind = data[target].receive(source, pulse)
if kind is not None:
sent = len(outputs)
if kind:
high += sent
else:
low += sent
for o in outputs:
if o not in data:
continue
if o not in new:
new.append((o, target, kind))
queue = new
return low, high
def find_targets(data, end):
result = []
for t in data[end].inputs.keys():
result.append(next(iter(data[t].inputs.keys())))
return result
def read_number(start, ends, data):
num = ""
current = start
while current is not None :
digit = "0"
next = None
for o in data[current].outputs:
if o in ends:
digit = "1"
else:
next = o
num += digit
current = next
return int(num[-1::-1], 2)
raw_input = split_lines("inputs/day20.txt")
data, end = parse(raw_input)
low, high = pulse(data, 1000)
print(low * high)
targets = set(find_targets(data, end))
nums = [ read_number(num, targets, data) for num in data["broadcaster"].outputs]
part2 = prod(nums)
print(part2)
```