brief note
| Part 1 | Part 2 | Total | |
|---|---|---|---|
| Time | 57:21 | 17:22 | 1:14:43 |
Wow, that's a lot of reading. It wasn't even hard, it was just implementing it took forever due to slowness in wrapping my head arond it and scrolling up and down a lot!
I used a dictionary to hold the states of all flip-flop modules and of conjunction modules. Then the logic with the queue for updating states and sending pulses is inside the for loop. Note: I sent None to conjunction modules just to remind me that it didn't matter if the pulse was high or low.
I used lh to keep track of the numbers of low and high pulses sent. I quite like how elegant lh[output] += len(modules[name][1]) is, using a boolean as an index into an array! Could have done the same thing with ints, but this still satisfies me. Then the result is the product of the numbers of high and low pulses sent.
from helpers.datagetter import aocd_data_in
from collections import defaultdict
din, aocd_submit = aocd_data_in(split=True, numbers=False)
modules = defaultdict(lambda: ("", []))
states = defaultdict(lambda: False)
for line in din:
if line[0].isalpha():
type = ""
else:
type = line[0]
line = line[1:]
name, out = line.split(" -> ")
out = out.split(", ")
modules[name] = (type, out)
if type == "&":
cons = {}
for i in range(len(din)):
if name in din[i].split(" -> ")[1].split(", "):
cons[din[i].split(" -> ")[0] if din[i][0].isalpha() else din[i].split(" -> ")[0][1:]] = False
states[name] = cons
lh = [0, 0]
for i in range(1000):
lh[0] += 1
queue = [("broadcaster", False)]
while queue:
name, pulse = queue.pop(0)
output = None
if modules[name][0] == "":
output = pulse
elif modules[name][0] == "%":
states[name] = not states[name]
output = states[name]
elif modules[name][0] == "&":
output = not all(states[name].values())
lh[output] += len(modules[name][1])
for out in modules[name][1]:
if modules[out][0] == "%":
if not output:
queue.append((out, pulse))
elif modules[out][0] == "&":
states[out][name] = output
queue.append((out, None))
aocd_submit(lh[0] * lh[1])A rare example of aocd_submit() not appearing at the bottom.
Easy, I thought, just run it. Nope! I let it run for something like 10,000,000 button presses before giving up. Loops came to mind first, so I looked at the example i-- there is no example input! Time to look at the real input closely for the first time.
I saw that rx was the result of a conjunction module which had four inputs, which were also conjunction modules themselves. Would I have to trace rx back and figure out when the inputs to the conjunctions would all line up, etc. What if those were also conjunctions?
I had no idea what to do, so I decided to just do something, hoping it wouldn't be that hard. I looked in my input and found four modules that would need to be pulsed to result in a high sent to rx. I picked these out manually. Then, I added these to a set called prereqs and updated the number of button presses the first time they received a high signal.
For a few minutes, I tried to verify that the cycle lengths were regular, but then I realized that it might not matter or that I might be checking for that incorrectly. I didn't notice this at the time, so I just tried it, but each number of button presses was prime, so the first time they would collide would be their product. This is the LCM, but it is equal to the product for prime numbers.
Surprised at no sample input for a problem that seemed to require looking at your input.
from helpers.datagetter import aocd_data_in
from collections import defaultdict
din, aocd_submit = aocd_data_in(split=True, numbers=False)
modules = defaultdict(lambda: ("", []))
states = defaultdict(lambda: False)
for line in din:
if line[0].isalpha():
type = ""
else:
type = line[0]
line = line[1:]
name, out = line.split(" -> ")
out = out.split(", ")
modules[name] = (type, out)
if type == "&":
cons = {}
for i in range(len(din)):
if name in din[i].split(" -> ")[1].split(", "):
cons[din[i].split(" -> ")[0] if din[i][0].isalpha() else din[i].split(" -> ")[0][1:]] = False
states[name] = cons
lh = [0, 0]
periods = []
prereqs = {"vd", "ns", "bh", "dl"}
button_presses = 1
while True:
queue = [("broadcaster", False)]
while queue:
name, pulse = queue.pop(0)
output = None
if modules[name][0] == "":
output = pulse
elif modules[name][0] == "%":
states[name] = not states[name]
output = states[name]
elif modules[name][0] == "&":
output = not all(states[name].values())
if output:
if name in prereqs:
periods.append(button_presses)
prereqs.remove(name)
if len(prereqs) == 0:
ans = 1
for period in periods:
ans *= period
aocd_submit(ans)
exit()
for out in modules[name][1]:
if modules[out][0] == "%":
if not output:
queue.append((out, pulse))
elif modules[out][0] == "&":
states[out][name] = output
queue.append((out, None))
button_presses += 1