Im gonna briefly describe the problem here, but if you want to see the real thing go check it out https://adventofcode.com/2023/day/20.

I like it because it involves some simple electronic devices that are wired together and send pulses/signals to each other. In this problem you have to make sure to correctly propagate the signals and simulate the behaviour of the devices.

There are two devices that have a very distinct behaviour:

In this problem, Flip flops are initially off and whenever they reiceve a low pulse they toggle between on/off. Each time it toggles state it sends a pulse as an output. When turned off sends a low pulse, when turned on sends a high pulse.

Conjunction modules remember the most recent pulse on each input. By default it remembers a low pulse for all inputs. When a pulse is received it updates the memory for that input. Then, if it remembers high pulses for all inputs, it sends a low pulse; otherwise, it sends a high pulse.

There is also some "dummy" modules:

One important thing to have in mind is that modules only send output pulses when they receive a pulse as input.

broadcaster -> a, b, c
%a -> b
%b -> c
%c -> inv
&inv -> a

There will always be just one Broadcaster module called "broadcaster" that has the Button connected as input. In this case it has module's "a", "b" and "c" connected to its output.

The arrow -> indicates what modules are connected to the output of the module to the left.

Lines that start with % means the module is a Flip flop, for example: %a -> b indicates that there's a flip flop called "a" whose output is connected to module's "b" input.

Lines that start with & means the module is a Conjunction, for example: &inv -> a indicates that there's a conjunction called "inv" whose output is connected to module's "a" input.

button -0-> broadcaster
broadcaster -0-> a
broadcaster -0-> b
broadcaster -0-> c
a -1-> b
b -1-> c
c -1-> inv
inv -0-> a
a -0-> b
b -0-> c
c -0-> inv
inv -1-> a

To solve the first part we need to calculate the multiplication between high and low pulses sent between devices.

In the previous example that would be 8*4=32.

But this time we don't push the button only once, but we push it a 1000 times. Each time we push the button we wait until all signals propagate and the circuit settles into a state before pushing the button again.

from abc import ABC
measure_pulses = {0: 0, 1: 0}
class Module(ABC):
    def __init__(self, name: str):
        self.name = name
        self.outputs = []

    def receive_pulse(self, mod: "Module", pulse: int) -> list[tuple["Module", int]]:
        measure_pulses[pulse] += 1
        print(f"{mod and mod.name} -{pulse}-> {self.name}")
        return self.process_pulse(mod, pulse)

    def connect_output(self, mod: "Module"):
        self.outputs.append(mod)

    def propagate_pulse(self, pulse: int):
        mods = []
        for m in self.outputs:
            mods.append((m, pulse))
        return mods

    def process_pulse(self, mod: "Module", pulse: int):
        raise NotImplementedError()

    def __str__(self) -> str:
        return f"{self.__class__.__name__}(name={self.name})"

    def __repr__(self) -> str:
        return str(self)

What we see here is that we expect all modules to have a name and outputs. See __init__(), __str__(), __repr__() and connect_output().

Each module can receive a pulse 0 or 1 from another module. See receive_pulse(). Each time we process a pulse we record it in a global dict called measure_pulses.

Also we leave process_pulse() to be defined by each particular module type.

We have a method that returns a list of all modules to which signals should be propagated. See propagate_pulse().

class TestModule(Module):
    def process_pulse(self, mod: "Module", pulse: int):
        return []

class Broadcaster(Module):
    def process_pulse(self, mod: "Module", pulse: int):
        return super().propagate_pulse(pulse)

class FlipFlop(Module):
    def __init__(self, name: str):
        super().__init__(name)
        self.state = 0

    def process_pulse(self, mod: "Module", pulse: int):
        if pulse == 0:
            self.state = (self.state + 1) % 2
            return super().propagate_pulse(self.state)
        return []

The flip flop start initially turned off. See self.state = 0 in __init__().

In process_pulse() we implement the behaviour:

class Conjunction(Module):
    def __init__(self, name: str):
        super().__init__(name)
        self.memory = {}

    def remember_input(self, mod: Module):
        self.memory[mod.name] = 0

    def process_pulse(self, mod: Module, pulse: int):
        self.memory[mod.name] = pulse
        if all(self.memory.values()):
            return self.propagate_pulse(0)
        return self.propagate_pulse(1)

The conjunction initializes its memory as empty. See __init__().

Each time a module is plugged in as an input it remembers it as OFF (0). See remember_input().

The way it processes pulses is by first recording the pulse for the input in its memory. Then if all inputs are 1s it sends a 0 pulse to all its outputs.

Otherwise it sends a 1 pulse to all its outputs.

At this point we have all our building blocks for solving this problem. We only need to parse the input and something that pushes the button and makes sure signals are propagated to the end.

def parse_modules(modules: list) -> dict[str, Module]:
    modules_by_name = {}
    outputs_by_name = {}

    # Parse all modules into their correspondig class and store
    # them in a dict.
    for m in modules:
        module_type = m[0]
        module_outputs = [o.strip() for o in m[1].split(",") if o.strip()]
        if module_type.startswith("broadcaster"):
            modules_by_name[module_type] = Broadcaster(module_type)
            outputs_by_name[module_type] = module_outputs
        elif module_type.startswith("%"):
            modules_by_name[module_type[1:]] = FlipFlop(module_type[1:])
            outputs_by_name[module_type[1:]] = module_outputs
        elif module_type.startswith("&"):
            modules_by_name[module_type[1:]] = Conjunction(module_type[1:])
            outputs_by_name[module_type[1:]] = module_outputs
    # Once all the modules are parsed use connect their outputs.

    # If the module doesn't exist at this point is a TestModule.
    # If the module is a Conjunction, call remember_input().
    for name, outputs in outputs_by_name.items():
        for mod_name in outputs:
            mod = modules_by_name.get(mod_name, TestModule(mod_name))
            modules_by_name[name].connect_output(mod)
            if isinstance(mod, Conjunction):
                mod.remember_input(modules_by_name[name])

    return modules_by_name

If we parse our example using that function we will receive a dictionary as its output. Keys are module names and values are the objects representing the module.

If we parse the example we get something like this:

example = """broadcaster -> a, b, c
%a -> b
%b -> c
%c -> inv
&inv -> a"""
example_modules = [m.split(" -> ") for m in example.splitlines() if m.strip()]
print(parse_modules(example_modules))

# Output
{
    'broadcaster': Broadcaster(name=broadcaster),
    'a': FlipFlop(name=a),
    'b': FlipFlop(name=b),
    'c': FlipFlop(name=c),
    'inv': Conjunction(name=inv)
}

def push_button(modules_by_name: dict[str, Module]):
    broad = modules_by_name["broadcaster"]
    queue = [(broad, broad.receive_pulse(None, 0))]
    while queue:
        current, signals = queue.pop(0)
        for mod, pulse in signals:
            queue.append((mod, mod.receive_pulse(current, pulse)))

Here, we lookup the broadcaster module by name. And send a pulse (note that we pass None as the module because we didn't implement a button class) to the broadcaster.

We store the current module (broadcaster) along with all the propagated signals (return value from receive_pulse()) in a queue to be processed.

While the signal queue to be processed is not empty we do the following:

This process will stop when all responses from receive_pulse() are empty and there are no more signals added to the queue.

If we run this for our example:

example_modules = parse_modules(example_modules)
push_button(example_modules)

# Output
None -0-> broadcaster
broadcaster -0-> a
broadcaster -0-> b
broadcaster -0-> c
a -1-> b
b -1-> c
c -1-> inv
inv -0-> a
a -0-> b
b -0-> c
c -0-> inv
inv -1-> a

It looks the same as when we analyzed the example above!!

We're ready for processing our problems input. (Remeber to comment out the print statement inside receive_pulse()).

modules = open("input.txt", "r").read().strip()
modules = [m.split(" -> ") for m in modules.splitlines() if m.strip()]
modules = parse_modules(modules)

for _ in range(1000):
    push_button(modules)

print("result:", measure_pulses[0] * measure_pulses[1])

# Output
result: x

This part as always is much trickier than the first part. It doesn't involve much code changes, just figuring out a way of avoiding large computations.

For this part, the problem tells us that there's a module called rx. And we need to find out the lowest amount of button pulses that will make the rx module receive a low pulse.

As I have learned troughout this entire challenge, just nahively letting it run and see when the rx module gets a low signal will get me nowhere. It will run forever.

So, taking a look at the input and see what the rx module is actually connected to might provide some guidance.

...
&lv -> rx
...

That means rx is a TestModule (a dummy module that has nothing connected to its output). And that has only one input: a Conjunction called lv.

...
&st -> lv
&tn -> lv
&hh -> lv
&dt -> lv
...

Other 4 Conjunctions are connected as inputs of lv. That's interesting. Because lv is a Conjuction it means that to send the low pulse required by rx it should receive all high pulses from its inputs.

The solution from here is kind of intuitive at this point. If we figure out how many button pulses does it take for each of the input devices to send a 1 signal we can multiply them together and get the result.

I'll explain better. Let's say st sends a 1 on every button push, tn sends a 1 every second button push (this means you have to press the button twice to get tn to send a 1 as an output), hh sends a 1 every fourth button push and dt sends a 1 every eighth button push.

module | pushes
---------------
  st   |   1
  tn   |   2
  hh   |   4
  dt   |   8

In this example, if we push the button 8 times. They are all gonna send a high pulse. Because 8 is divisible by 1, 2, 4 and 8.

module | pushes
---------------
  st   |   1
  tn   |   3
  hh   |   5
  dt   |   7

In this case there's no obvious number of times we should push the button. But if we multiply the numbers together we get a number that is divisible by every number in the table. Pushing the button 1 * 3 * 5 * 7 = 105 times will make all the outputs send a 1, and consequently rx will receive a 0.

from collections import defaultdict

# Store number of button presses in a global variable
ITERATIONS = 0
# Store high pulses for target modules
OUT_PULSES = defaultdict(list)

class Conjunction(Module):
    def __init__(self, name: str):
        super().__init__(name)
        self.memory = {}

    def remember_input(self, mod: Module):
        self.memory[mod.name] = 0

    def start_recording(self):
        self.recording = True

    def record(self):
        if hasattr(self, "recording"):
            OUT_PULSES[self.name].append(ITERATIONS)

    def process_pulse(self, mod: Module, pulse: int):
        self.memory[mod.name] = pulse
        if all(self.memory.values()):
            return self.propagate_pulse(0)
        self.record()
        return self.propagate_pulse(1)

We introduced 2 new methods to the conjunction module: start_recording() and record(). The first just initializes a bool attribute. And the second makes sure to only record high pulses for objects that have been initialized (method start_recording() called).

Also introduced 2 global variables: ITERATIONS to keep track of button pushes and OUT_SIGNALS to track each time one of the modules outputs a high pulse.

# Get the "lv" module by name
lv = modules["lv"]
lv_inputs = [modules[k] for k in lv.memory.keys()]
for m in lv_inputs:
    m.start_recording()

for i in range(100_000):
    ITERATIONS += 1
    push_button(modules)
print(OUT_PULSES)

# Output
{'hh': [3769, 7538, 11307, 15076, 18845, 22614, 26383, 30152, 33921, 37690, 41459, 45228, 48997, 52766, 56535, 60304, 64073, 67842, 71611, 75380, 79149, 82918, 86687, 90456, 94225, 97994], 'tn': [3863, 7726, 11589, 15452, 19315, 23178, 27041, 30904, 34767, 38630, 42493, 46356, 50219, 54082, 57945, 61808, 65671, 69534, 73397, 77260, 81123, 84986, 88849, 92712, 96575], 'st': [3929, 7858, 11787, 15716, 19645, 23574, 27503, 31432, 35361, 39290, 43219, 47148, 51077, 55006, 58935, 62864, 66793, 70722, 74651, 78580, 82509, 86438, 90367, 94296, 98225], 'dt': [4079, 8158, 12237, 16316, 20395, 24474, 28553, 32632, 36711, 40790, 44869, 48948, 53027, 57106, 61185, 65264, 69343, 73422, 77501, 81580, 85659, 89738, 93817, 97896]}

hh = n*3769
tn = n*3863
st = n*3929
dt = n*4079

This means we can just multiply the first element of each list for each module and we'll get our result.

accum = 1
for name, pulses in OUT_PULSES.items():
    accum *= pulses[0]
print("result:", accum)

# Output
result: 233338595643977

Edit: As some people have pointed out in the HN discussion, just multiplying the numbers together only works because the numbers are coprimes and the correct solution is to use LCM.

This problem is my favourite because it has a few characteristics that I personally enjoy:

In the end this is one of my favourites because to solve it you just have to understand the problem and understand the data.

Link to my github project with the solutions https://github.com/mliezun/aoc.