[Day 20] Pulse Propagation // Advent of Code 2023 (Python)

Pulse Propagation (via DALL-E 3)

Advent of Code
With your help, the Elves manage to find the right parts and fix all of the machines. Now, they just need to send the…adventofcode.com

---

Part One

With your help, the Elves manage to find the right parts and fix all of the machines. Now, they just need to send the command to boot up the machines and get the sand flowing again.

The machines are far apart and wired together with long cables. The cables don’t connect to the machines directly, but rather to communication modules attached to the machines that perform various initialization tasks and also act as communication relays.

Modules communicate using pulses. Each pulse is either a high pulse or a low pulse. When a module sends a pulse, it sends that type of pulse to each module in its list of destination modules.

There are several different types of modules:

Flip-flop modules (prefix %) are either on or off; they are initially off. If a flip-flop module receives a high pulse, it is ignored and nothing happens. However, if a flip-flop module receives a low pulse, it flips between on and off. If it was off, it turns on and sends a high pulse. If it was on, it turns off and sends a low pulse.

Conjunction modules (prefix &) remember the type of the most recent pulse received from each of their connected input modules; they initially default to remembering a low pulse for each input. When a pulse is received, the conjunction module first updates its 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 a single broadcast module (named broadcaster). When it receives a pulse, it sends the same pulse to all of its destination modules.

Here at Desert Machine Headquarters, there is a module with a single button on it called, aptly, the button module. When you push the button, a single low pulse is sent directly to the broadcaster module.

After pushing the button, you must wait until all pulses have been delivered and fully handled before pushing it again. Never push the button if modules are still processing pulses.

Pulses are always processed in the order they are sent. So, if a pulse is sent to modules a, b, and c, and then module a processes its pulse and sends more pulses, the pulses sent to modules b and c would have to be handled first.

The module configuration (your puzzle input) lists each module. The name of the module is preceded by a symbol identifying its type, if any. The name is then followed by an arrow and a list of its destination modules. For example:

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

In this module configuration, the broadcaster has three destination modules named a, b, and c. Each of these modules is a flip-flop module (as indicated by the % prefix). a outputs to b which outputs to c which outputs to another module named inv. inv is a conjunction module (as indicated by the & prefix) which, because it has only one input, acts like an inverter(it sends the opposite of the pulse type it receives); it outputs to a.

By pushing the button once, the following pulses are sent:

button -low-> broadcaster
broadcaster -low-> a
broadcaster -low-> b
broadcaster -low-> c
a -high-> b
b -high-> c
c -high-> inv
inv -low-> a
a -low-> b
b -low-> c
c -low-> inv
inv -high-> a

After this sequence, the flip-flop modules all end up off, so pushing the button again repeats the same sequence.

Here’s a more interesting example:

broadcaster -> a
%a -> inv, con
&inv -> b
%b -> con
&con -> output

This module configuration includes the broadcaster, two flip-flops (named aand b), a single-input conjunction module (inv), a multi-input conjunction module (con), and an untyped module named output (for testing purposes). The multi-input conjunction module con watches the two flip-flop modules and, if they’re both on, sends a low pulse to the output module.

Here’s what happens if you push the button once:

button -low-> broadcaster
broadcaster -low-> a
a -high-> inv
a -high-> con
inv -low-> b
con -high-> output
b -high-> con
con -low-> output

Both flip-flops turn on and a low pulse is sent to output! However, now that both flip-flops are on and con remembers a high pulse from each of its two inputs, pushing the button a second time does something different:

button -low-> broadcaster
broadcaster -low-> a
a -low-> inv
a -low-> con
inv -high-> b
con -high-> output

Flip-flop a turns off! Now, con remembers a low pulse from module a, and so it sends only a high pulse to output.

Push the button a third time:

button -low-> broadcaster
broadcaster -low-> a
a -high-> inv
a -high-> con
inv -low-> b
con -low-> output
b -low-> con
con -high-> output

This time, flip-flop a turns on, then flip-flop b turns off. However, before b can turn off, the pulse sent to con is handled first, so it briefly remembers all high pulses for its inputs and sends a low pulse to output. After that, flip-flop b turns off, which causes con to update its state and send a high pulse to output.

Finally, with a on and b off, push the button a fourth time:

button -low-> broadcaster
broadcaster -low-> a
a -low-> inv
a -low-> con
inv -high-> b
con -high-> output

This completes the cycle: a turns off, causing con to remember only low pulses and restoring all modules to their original states.

To get the cables warmed up, the Elves have pushed the button 1000 times. How many pulses got sent as a result (including the pulses sent by the button itself)?

In the first example, the same thing happens every time the button is pushed: 8 low pulses and 4 high pulses are sent. So, after pushing the button 1000 times, 8000 low pulses and 4000 high pulses are sent. Multiplying these together gives 32000000.

In the second example, after pushing the button 1000 times, 4250 low pulses and 2750 high pulses are sent. Multiplying these together gives 11687500.

Consult your module configuration; determine the number of low pulses and high pulses that would be sent after pushing the button 1000 times, waiting for all pulses to be fully handled after each push of the button. What do you get if you multiply the total number of low pulses sent by the total number of high pulses sent?

---

So, let’s begin with a simple visualization of a case with just 2 machines connected:

CM aka Communication modules are attached to machines that perform various initialization tasks and also act as communication relays.

Types:

• Flip-flop (%) — ON | OFF (Default)
  * High Pulse: Ignore
  * Low Pulse: Flips state
  — if Off: flips to ON + returns High Pulse
  — if ON: flips to OFF + returns Low Pulse
• Conjunction (&) — Low pulse (Default)
  * Remembers the most recent pulse for each input module
  * for input pulse: updates memory, return High or Low
• Broadcast (broadcaster)
  * input pulse -> sends the same pulse to all destination modules

Now, at Desert Machine Headquarters, there is a module with a single button on it called, aptly, the button module. When you push the button, a single low pulse is sent directly to the broadcaster module.

Once we push aptly we must wait until all pulses have been processed for all modules in our network.

Pulses are always processed in the order they are sent.

So, if a pulse is sent to modules a, b, and c, and then module a processes its pulse and sends more pulses, the pulses sent to modules b and c would have to be handled first.

So, we can see that the system in a way is “queueing” the requests!

Now, we are given a module configuration (input) which is something like this:

where, the broadcaster has three destination modules named a, b, and c. Each of these modules is a flip-flop module (as indicated by the % prefix).

• a outputs to b which outputs to c which outputs to another module named inv.

• inv is a conjunction module (as indicated by the & prefix) which, because it has only one input, acts like an inverter(it sends the opposite of the pulse type it receives); it outputs to a.

By pushing the aptly button once, the following pulses are sent:

button -low-> broadcaster
broadcaster -low-> a
broadcaster -low-> b
broadcaster -low-> c
a -high-> b
b -high-> c
c -high-> inv
inv -low-> a
a -low-> b
b -low-> c
c -low-> inv
inv -high-> a

Let’s understand this with a visualization:

Starting from 1 → 12

After this sequence, the flip-flop modules all end up OFF, so pushing the button again repeats the same sequence.

We are given another example:

broadcaster -> a
%a -> inv, con
&inv -> b
%b -> con
&con -> output

Here’s what happens if you push the button once:

button -low-> broadcaster
broadcaster -low-> a
a -high-> inv
a -high-> con
inv -low-> b
con -high-> output
b -high-> con
con -low-> output

Both flip-flops turn on and a low pulse is sent to output! However, now that both flip-flops are on and con remembers a high pulse from each of its two inputs

Pushing the button second time?

button -low-> broadcaster
broadcaster -low-> a
a -low-> inv
a -low-> con
inv -high-> b
con -high-> output

Flip-flop a turns off! Now, con remembers a low pulse from module a, and so it sends only a high pulse to output.

And third time?

button -low-> broadcaster
broadcaster -low-> a
a -high-> inv
a -high-> con
inv -low-> b
con -low-> output
b -low-> con
con -high-> output

This time, flip-flop a turns on, then flip-flop b turns off. However, before b can turn off, the pulse sent to con is handled first, so it briefly remembers all high pulses for its inputs and sends a low pulse to output. After that, flip-flop b turns off, which causes con to update its state and send a high pulse to output.

Finally, with a on and b off, push the button a fourth time:

button -low-> broadcaster
broadcaster -low-> a
a -low-> inv
a -low-> con
inv -high-> b
con -high-> output

This completes the cycle: a turns off, causing con to remember only low pulses and restoring all modules to their original states.

Now, the problem states that:

To get the cables warmed up, the Elves have pushed the button 1000 times. How many pulses got sent as a result (including the pulses sent by the button itself)?

— — —

Phew! This one is going to be intense! I can feel it. We need to simulate the circuit and remember the states. Seems like OOP might be the perfect way to solve this one! ;)

Let’s first write our base case?

Skelton code, a good point to start!

As mentioned, I am heavily leaning towards an object-oriented approach here as it will allow us to simulate the behavior of the different types of modules and their interactions when the button is pressed!

The key components on top of my mind are:

1. Module Classes: Representing different types of modules (Flip-flop, Conjunction, Broadcaster and Untyped
2. Pulse Management: Handling the sending and processing of pulses.
3. Simulation Logic: To simulate the process of pushing the button and propagating the pulses.

Let’s start by defining the classes and their methods:

Module Classes

• BaseModule: An abstract class for common module functionality.
• FlipFlopModule: Represents a flip-flop module.
• ConjunctionModule: Represents a conjunction module.
• BroadcasterModule: Represents the broadcaster module.
• Untyped: Represents the untyped module.

Also, to keep track of Pulse Type and Module State, we can just define enum classes to make the code cleaner?

Let’s see our base class for Module ?

We are leaving receive_pulse to be implemented by it’s derived classes

Now let’s implement:

FlipFlopModule

The FlipFlopModule class initialises the object with State.OFF. We implement the receive_pulse method that changes the state of the module based on the received pulse.

• If the received pulse is LOW, the state of the module is toggled.
• If the current state is OFF, it is changed to ON, and vice versa.

After changing the state, the module sends a pulse.

• If the new state is ON, it sends a HIGH pulse, otherwise it sends a LOW pulse.

ConjunctionModule

The ConjunctionModule class has a __init__ method that sets the name of the module and initializes a list of input states. The number of input states is determined by the inputs parameter, which is a list of input module names. Initially, all input states are set to LOW.

The receive_pulse method is used to receive a pulse at a specific input. The pulse can be either HIGH or LOW, and the corresponding input state is updated accordingly. After updating the input state, the method checks if all input states are HIGH. If they are, it sends a LOW pulse; otherwise, it sends a HIGH pulse. This behavior is the opposite of a typical AND gate, which would output HIGH when all inputs are HIGH.

BroadcasterModule

This represents a broadcaster module, which is a type of digital circuit that broadcasts the same pulse to all of its destination modules.

The BroadcasterModule class has a receive_pulse method that immediately sends the received pulse to all destination modules. The pulse can be either HIGH or LOW. This behavior is implemented by calling the send_pulse method with the received pulse as the argument.

UntypedModule

It represents a module that can receive pulses but does not have a specific type.

The receive_pulse method is used to receive a pulse and the name of the input module. The pulse can be either HIGH or LOW. The method appends the received pulse to the list of received pulses and then do nothing!

ModuleFactory

💭 I think this is a cookie-cutter case for Factory Pattern as we can create module instances based on their types as indicated by their names or prefixes.

We can define a**ModuleFactory** class responsible for creating module instances based on the input string.

This is pretty much self explanatory!

Simulation

Once all our pieces are set up! We are good to go to implement our simulation class that will orchestrate a pulse run for each button press and track everything we need!

Now to orchestrate all of this, one of the most important parts is to parse the config_lines and set up our modules correctly with the type, state and destination so when they receive a Pulse, they can send it forward correctly!

Here, we are setting up both modules and their respective connections in the destinations.

Let’s now run our first base test case:

And it failed! Let’s debug?

And after some debugging and back and forth, we can see it is counting LOW_PULSE_COUNT and HIGH_PULSE_COUNT correctly for the first run, now we just need to let it run 1000 times and return the product of both counts!

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_20/pulse_propagation.py"
✅ test_count_pulses_in_the_circuit() passed

[Done] exited with code=0 in 0.237 seconds

Perfect! Now, let’s test our code for thesecond example in the problem? This way we will be able to ensure we are covering all the edge cases!

broadcaster -> a
%a -> inv, con
&inv -> b
%b -> con
&con -> output

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_20/pulse_propagation.py"
✅ test_count_pulses_in_the_circuit() passed
Traceback (most recent call last):
  File "/Users/jmalik/github/advent-of-code-2023/day_20/pulse_propagation.py", line 195, in <module>
    test_count_pulses_in_the_circuit_b()
  File "/Users/jmalik/github/advent-of-code-2023/day_20/pulse_propagation.py", line 185, in test_count_pulses_in_the_circuit_b
    modules = setup_modules(input_str.splitlines())
  File "/Users/jmalik/github/advent-of-code-2023/day_20/pulse_propagation.py", line 158, in setup_modules
    modules[source_name].add_destination(modules[dest_name])
KeyError: 'output'

[Done] exited with code=1 in 0.244 seconds

Whoops! We got stuck in an error as we are not initiating Modules for destinations, which is leading to an error for Output which should be an UntypedModule.

We can update our setup_modules() code to handle that once we create all modules for the source part of the config:

Let’s run the test case again? And voila!

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_20/pulse_propagation.py"
✅ test_count_pulses_in_the_circuit_b() passed

[Done] exited with code=0 in 0.231 seconds

I feel pretty good about this code as it has a good runtime and has quite a clean code making it easy to debug.

Let’s load up our puzzle input and see if we get an answer?

And…executing the code…

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_20/pulse_propagation.py"
❗️ Product of total number of low pulses sent by the total number of high pulses sent: XXXXXXXXX

[Done] exited with code=0 in 0.248 seconds

We get an answer! Let’s input this in our answer box?

⭐️

Boom! Let me paste our well-structured object-oriented code till now:

# Day 20 - Pulse Propagation

from enum import Enum
from collections import deque

# Constants

# dict to hold the count of inputs for each module
INPUT_TRACKER = {}
# global queue to hold pulses
PULSE_QUEUE = deque()
# to hold the count of low and high pulses
LOW_PULSE_COUNT, HIGH_PULSE_COUNT = 0, 0

# Enums

class State(Enum):
    ON = 1
    OFF = 0

class Pulse(Enum):
    HIGH = 1
    LOW = 0

class ModuleType(Enum):
    FLIP_FLOP = "%"
    CONJUNCTION = "&"
    BROADCASTER = "broadcaster"

# Classes

class Module:
    def __init__(self, name):
        self.name = name
        self.destinations = []

    def add_destination(self, module):
        self.destinations.append(module)

    def send_pulse(self, pulse):
        for dest_module in self.destinations:
            PULSE_QUEUE.append((pulse, dest_module.name, self.name))
            update_pulse_count(pulse)

    def receive_pulse(self, pulse, input_name):
        raise NotImplementedError("Subclass must implement receive_pulse method")

class FlipFlopModule(Module):
    def __init__(self, name):
        super().__init__(name)
        self.state = State.OFF

    def receive_pulse(self, pulse, src_module):
        if pulse == Pulse.LOW:
            self.state = State.ON if self.state == State.OFF else State.OFF
            self.send_pulse(Pulse.HIGH if self.state == State.ON else Pulse.LOW)

class ConjunctionModule(Module):
    def __init__(self, name, inputs):
        super().__init__(name)
        self.inputs = inputs  # List of input module names
        self.input_states = {input_name: Pulse.LOW for input_name in inputs}

    def receive_pulse(self, pulse, src_module):
        self.input_states[src_module] = pulse

        if all(state == Pulse.HIGH for state in self.input_states.values()):
            self.send_pulse(Pulse.LOW)
        else:
            self.send_pulse(Pulse.HIGH)

class BroadcasterModule(Module):
    def receive_pulse(self, pulse, src_module):
        self.send_pulse(pulse)

class UntypedModule(Module):
    def __init__(self, name):
        super().__init__(name)
        self.received_pulses = []

    def receive_pulse(self, pulse, src_module):
        self.received_pulses.append(pulse)

class ModuleFactory:
    @staticmethod
    def create_module(module_identifier):
        if module_identifier.startswith(ModuleType.FLIP_FLOP.value):
            return FlipFlopModule(module_identifier[1:])
        elif module_identifier.startswith(ModuleType.CONJUNCTION.value):
            # Determine the number of inputs for the conjunction module
            name = module_identifier[1:]
            module_inputs = INPUT_TRACKER[name]
            return ConjunctionModule(name, module_inputs)
        elif module_identifier == ModuleType.BROADCASTER.value:
            return BroadcasterModule(module_identifier)
        else:
            return UntypedModule(module_identifier)

class Simulation:
    def __init__(self, modules):
        self.modules = modules

    def run_simulation(self, button_presses):
        for _ in range(button_presses):
            # Simulate button press - send a low pulse to broadcaster
            update_pulse_count(Pulse.LOW)
            self.modules["broadcaster"].receive_pulse(Pulse.LOW, "button")

            # Process pulses in the queue
            while PULSE_QUEUE:
                pulse, dest_module, src_module = PULSE_QUEUE.popleft()
                self.modules[dest_module].receive_pulse(pulse, src_module)

# Util functions

def update_pulse_count(pulse):
    global LOW_PULSE_COUNT, HIGH_PULSE_COUNT
    if pulse == Pulse.LOW:
        LOW_PULSE_COUNT += 1
    elif pulse == Pulse.HIGH:
        HIGH_PULSE_COUNT += 1

def process_input_count(config_lines):
    global INPUT_TRACKER
    for line in config_lines:
        parts = line.split("->")
        source = parts[0].strip()
        if len(parts) > 1:
            destinations = [dest.strip() for dest in parts[1].split(",")]

            for dest in destinations:
                # Remove any prefix from the destination name
                dest = dest.lstrip("%&")
                source = source.lstrip("%&")
                if dest not in INPUT_TRACKER:
                    INPUT_TRACKER[dest] = set()
                INPUT_TRACKER[dest].add(source)

def setup_modules(config_lines):
    modules = {}
    connections = {}

    for line in config_lines:
        parts = line.split("->")
        source_name = parts[0].strip()
        dest_names = parts[1].split(",") if len(parts) > 1 else []
        clean_source_name = source_name.lstrip("%& ")

        if clean_source_name not in modules:
            modules[clean_source_name] = ModuleFactory.create_module(source_name)

        for dest_name in dest_names:
            if clean_source_name not in connections:
                connections[clean_source_name] = []
            connections[clean_source_name].append(dest_name)

    # Set up connections
    for source_name, dest_names in connections.items():
        for dest_name in dest_names:
            dest_name = dest_name.strip()
            if dest_name not in modules:
                # Create module if it doesn't exist for destination
                modules[dest_name] = ModuleFactory.create_module(dest_name)
            modules[source_name].add_destination(modules[dest_name])

    return modules

# Tests

def test_count_pulses_in_the_circuit_a():
    input_str = """broadcaster -> a, b, c
%a -> b
%b -> c
%c -> inv
&inv -> a"""
    process_input_count(input_str.splitlines())
    modules = setup_modules(input_str.splitlines())
    simulation = Simulation(modules)
    button_presses = 1000
    simulation.run_simulation(button_presses)
    num_pulses = LOW_PULSE_COUNT * HIGH_PULSE_COUNT
    assert num_pulses == 32000000, f"Expected 32000000, got {num_pulses}"
    print("✅ test_count_pulses_in_the_circuit_a() passed")

def test_count_pulses_in_the_circuit_b():
    input_str = """broadcaster -> a
%a -> inv, con
&inv -> b
%b -> con
&con -> output"""
    process_input_count(input_str.splitlines())
    modules = setup_modules(input_str.splitlines())
    simulation = Simulation(modules)
    button_presses = 1000
    simulation.run_simulation(button_presses)
    num_pulses = LOW_PULSE_COUNT * HIGH_PULSE_COUNT
    assert num_pulses == 11687500, f"Expected 11687500, got {num_pulses}"
    print("✅ test_count_pulses_in_the_circuit_b() passed")

# Main

def part_one():
    with open("day_20/input.txt") as f:
        config_lines = f.readlines()
    process_input_count(config_lines)
    modules = setup_modules(config_lines)
    simulation = Simulation(modules)
    button_presses = 1000
    simulation.run_simulation(button_presses)
    num_pulses = LOW_PULSE_COUNT * HIGH_PULSE_COUNT
    print(
        f"❗️ Product of total number of low pulses sent by the \
total number of high pulses sent: {num_pulses}"
    )

if __name__ == "__main__":
    # test_count_pulses_in_the_circuit_a()
    # test_count_pulses_in_the_circuit_b()
    part_one()

❗️The one limitation of our code here is that, we can only run 1 simulation at a time as we are using global variables to keep pulse count and queue. We shall address this in part 2.

---

Part Two

The final machine responsible for moving the sand down to Island Island has a module attached named rx. The machine turns on when a single low pulse is sent to rx.

Reset all modules to their default states. Waiting for all pulses to be fully handled after each button press, what is the fewest number of button presses required to deliver a single low pulse to the module named rx?

---

Well, this seems simple?! All we need to do is track the min_num_of_button_press to send a Pulse.LOW to rx module!

We can define a new function run_simulation_until_rx() that will basically keep pressing the button to go through the circuit till we recieve a Pulse.LOW headed towards rx module:

.

.

.

.

.

Well, it may not be as simple as we thought first! ~6 mins later, we are at 521553 button presses with no sight of Pulse.LOW to rx.

I knew it was too good to be this simple! First things first, let’s add a __repr__ method to our base Module class so we don’t have to deal with this in our debugger:

Let’s make it human readable without having to click through each object to see it’s properties:

Much better!

Now, looking at our puzzle input, the only module that has rx as a destination is &dn (ConjunctionModule).

&dn -> rx

Let’s add that to our watch list to see how it changes the input_states as it can’t send a Pulse.LOW to rx until all its input_states are set to Pulse.HIGH!

We can see that &dn has 4 callers -> xp, fh, dd, fc and they all are initiated as Pulse.LOW :

dn state as of initialization!

After 1 cycle complete (i.e. button_presses == 1), here’s how&dn looks like:

We got 4 pulses to rx but all of them were HIGH.

We basically need to find a case where all 4 of xp, fh, dd, fc become Pulse.HIGH . I am inclined to think that all 4 of these states may have some cycles and we might need to find a common point where these cycles will co-incide?

Let’s create a breakpoint to see if we ever get a Pulse.HIGH for either of these 4?

conditional breakpoint

So, at 3917 we found our first call to fc with Pulse.HIGH :

which will then modify our dn input_states to:

And similarly, on 3919 button press, we get Pulse.HIGH for xp

changing our dn input_states to:

Then for 4003 time, we get one for dd

making our dn input_states:

Lastly, we get Pulse.HIGH for fh at 4027 button press:

making our dn to be:

❗️Now! Moving on! We can see that the next event comes at 7834th time for fc and if you scroll up, the last event came at 3917 i.e: 7834/2

This helps us establish that each of these input modules has its own cycle! And now this helps us deduce this down an LCM (Lowest common multiple) problem, where all we need to find is what will be the first time in our button press cycle when all 4 xp, fh, dd, fc will receive Pulse.HIGH that will emit a Pulse.LOW to rx !

This is now a simple mathematical problem!

We can find the LCM for 3917, 3919, 4003 and 4027 i.e:

We can whip up a quick python script to find that:

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/tempCodeRunnerFile.python"
XXXXXXXXXXXXXXX

[Done] exited with code=0 in 0.218 seconds

Let’s put this in our answer box and….yes! Our hunch was absolutely correct.

YESSS!!

Well, since it is not physically possible for us to keep running our code for 200 Trillions+ (answer in some ballpark) times, we need to just update our code to find the first occurence for each xp, fh, dd, fc and then just find the LCM and exit:

Some debugging steps later

Here’s our updated run_simulation_until_rx() that will iterate till:

all(idx > 0 for idx in rx_callers_high_pulse_idx.values())

Let’s run it and see if we are getting the correct answer as we calculated mathematically before?

[Running] python3 "/Users/jmalik/github/advent-of-code-2023/day_20/pulse_propagation.py"
❗️❗️ Number of button presses required to activate the Rx: XXXXXXXXXXXXXXX

[Done] exited with code=0 in 0.412 seconds

Yep! XXXXXXXXXXXXXXX == XXXXXXXXXXXXXXX 🤓

Here’s our full code for both Part 1 and 2:

# Day 20 - Pulse Propagation

from enum import Enum
from collections import deque
from math import gcd
from functools import reduce

# Constants

# dict to hold the count of inputs for each module
INPUT_TRACKER = {}
# global queue to hold pulses
PULSE_QUEUE = deque()
# to hold the count of low and high pulses
LOW_PULSE_COUNT, HIGH_PULSE_COUNT = 0, 0

# Enums

class State(Enum):
    ON = 1
    OFF = 0

class Pulse(Enum):
    HIGH = 1
    LOW = 0

class ModuleType(Enum):
    FLIP_FLOP = "%"
    CONJUNCTION = "&"
    BROADCASTER = "broadcaster"

# Classes

class Module:
    def __init__(self, name):
        self.name = name
        self.destinations = []

    def add_destination(self, module):
        self.destinations.append(module)

    def send_pulse(self, pulse):
        for dest_module in self.destinations:
            PULSE_QUEUE.append((pulse, dest_module.name, self.name))
            update_pulse_count(pulse)

    def receive_pulse(self, pulse, input_name):
        raise NotImplementedError("Subclass must implement receive_pulse method")

class FlipFlopModule(Module):
    def __init__(self, name):
        super().__init__(name)
        self.state = State.OFF

    def __repr__(self) -> str:
        return f"Module({self.name} - {self.state})"

    def receive_pulse(self, pulse, src_module):
        if pulse == Pulse.LOW:
            self.state = State.ON if self.state == State.OFF else State.OFF
            self.send_pulse(Pulse.HIGH if self.state == State.ON else Pulse.LOW)

class ConjunctionModule(Module):
    def __init__(self, name, inputs):
        super().__init__(name)
        self.inputs = inputs  # List of input module names
        self.input_states = {input_name: Pulse.LOW for input_name in inputs}

    def __repr__(self) -> str:
        return f"Module({self.name} - {self.input_states})"

    def receive_pulse(self, pulse, src_module):
        self.input_states[src_module] = pulse

        if all(state == Pulse.HIGH for state in self.input_states.values()):
            self.send_pulse(Pulse.LOW)
        else:
            self.send_pulse(Pulse.HIGH)

class BroadcasterModule(Module):
    def receive_pulse(self, pulse, src_module):
        self.send_pulse(pulse)

class UntypedModule(Module):
    def __init__(self, name):
        super().__init__(name)
        self.received_pulses = {Pulse.LOW: 0, Pulse.HIGH: 0}

    def __repr__(self) -> str:
        return f"Module({self.name} - {self.received_pulses})"

    def receive_pulse(self, pulse, src_module):
        self.received_pulses[pulse] += 1

class ModuleFactory:
    @staticmethod
    def create_module(module_identifier):
        if module_identifier.startswith(ModuleType.FLIP_FLOP.value):
            return FlipFlopModule(module_identifier[1:])
        elif module_identifier.startswith(ModuleType.CONJUNCTION.value):
            # Determine the number of inputs for the conjunction module
            name = module_identifier[1:]
            module_inputs = INPUT_TRACKER[name]
            return ConjunctionModule(name, module_inputs)
        elif module_identifier == ModuleType.BROADCASTER.value:
            return BroadcasterModule(module_identifier)
        else:
            return UntypedModule(module_identifier)

class Simulation:
    def __init__(self, modules):
        self.modules = modules

    def run_simulation(self, button_presses):
        for _ in range(button_presses):
            # Simulate button press - send a low pulse to broadcaster
            update_pulse_count(Pulse.LOW)
            self.modules["broadcaster"].receive_pulse(Pulse.LOW, "button")

            # Process pulses in the queue
            while PULSE_QUEUE:
                pulse, dest_module, src_module = PULSE_QUEUE.popleft()
                self.modules[dest_module].receive_pulse(pulse, src_module)

    def run_simulation_until_rx(self):
        button_presses = 0

         # rx_source is the only input for rx i.e. &dn
        rx_source = list(INPUT_TRACKER['rx'])[0]

        # dict to hold the index of the rx caller that received a Pulse.HIGH for the first time
        rx_callers_high_pulse_idx = {caller: 0 for caller in INPUT_TRACKER[rx_source]}

        # break when all the rx callers have received a high pulse for the first time
        while not all(idx > 0 for idx in rx_callers_high_pulse_idx.values()):
            button_presses += 1
            self.modules['broadcaster'].receive_pulse(Pulse.LOW, "button")
            update_pulse_count(Pulse.LOW)

            while PULSE_QUEUE:
                pulse, dest_module, src_module = PULSE_QUEUE.popleft()
                self.modules[dest_module].receive_pulse(pulse, src_module)

                # update the index of the rx caller that received a high pulse for the first time
                if src_module in rx_callers_high_pulse_idx.keys() and  pulse == Pulse.HIGH:
                    rx_callers_high_pulse_idx[src_module] = button_presses

        # lcm formula
        lcm = lambda x, y: x * y // gcd(x, y)
    
        # find LCM for all the values in rx_callers_high_pulse_idx
        return reduce(lcm, list(rx_callers_high_pulse_idx.values()))

# Util functions

def update_pulse_count(pulse):
    global LOW_PULSE_COUNT, HIGH_PULSE_COUNT
    if pulse == Pulse.LOW:
        LOW_PULSE_COUNT += 1
    elif pulse == Pulse.HIGH:
        HIGH_PULSE_COUNT += 1

def process_input_count(config_lines):
    global INPUT_TRACKER
    for line in config_lines:
        parts = line.split("->")
        source = parts[0].strip()
        if len(parts) > 1:
            destinations = [dest.strip() for dest in parts[1].split(",")]

            for dest in destinations:
                # Remove any prefix from the destination name
                dest = dest.lstrip("%&")
                source = source.lstrip("%&")
                if dest not in INPUT_TRACKER:
                    INPUT_TRACKER[dest] = set()
                INPUT_TRACKER[dest].add(source)

def setup_modules(config_lines):
    modules = {}
    connections = {}

    for line in config_lines:
        parts = line.split("->")
        source_name = parts[0].strip()
        dest_names = parts[1].split(",") if len(parts) > 1 else []
        clean_source_name = source_name.lstrip("%& ")

        if clean_source_name not in modules:
            modules[clean_source_name] = ModuleFactory.create_module(source_name)

        for dest_name in dest_names:
            if clean_source_name not in connections:
                connections[clean_source_name] = []
            connections[clean_source_name].append(dest_name)

    # Set up connections
    for source_name, dest_names in connections.items():
        for dest_name in dest_names:
            dest_name = dest_name.strip()
            if dest_name not in modules:
                # Create module if it doesn't exist for destination
                modules[dest_name] = ModuleFactory.create_module(dest_name)
            modules[source_name].add_destination(modules[dest_name])

    return modules

# Tests

def test_count_pulses_in_the_circuit_a():
    input_str = """broadcaster -> a, b, c
%a -> b
%b -> c
%c -> inv
&inv -> a"""
    process_input_count(input_str.splitlines())
    modules = setup_modules(input_str.splitlines())
    simulation = Simulation(modules)
    button_presses = 1000
    simulation.run_simulation(button_presses)
    num_pulses = LOW_PULSE_COUNT * HIGH_PULSE_COUNT
    assert num_pulses == 32000000, f"Expected 32000000, got {num_pulses}"
    print("✅ test_count_pulses_in_the_circuit_a() passed")

def test_count_pulses_in_the_circuit_b():
    input_str = """broadcaster -> a
%a -> inv, con
&inv -> b
%b -> con
&con -> output"""
    process_input_count(input_str.splitlines())
    modules = setup_modules(input_str.splitlines())
    simulation = Simulation(modules)
    button_presses = 1000
    simulation.run_simulation(button_presses)
    num_pulses = LOW_PULSE_COUNT * HIGH_PULSE_COUNT
    assert num_pulses == 11687500, f"Expected 11687500, got {num_pulses}"
    print("✅ test_count_pulses_in_the_circuit_b() passed")

# Main

def part_one():
    with open("day_20/input.txt") as f:
        config_lines = f.readlines()
    process_input_count(config_lines)
    modules = setup_modules(config_lines)
    simulation = Simulation(modules)
    button_presses = 1000
    simulation.run_simulation(button_presses)
    num_pulses = LOW_PULSE_COUNT * HIGH_PULSE_COUNT
    print(
        f"❗️ Product of total number of low pulses sent by the \
total number of high pulses sent: {num_pulses}"
    )

def part_two():
    with open("day_20/input.txt") as f:
        config_lines = f.readlines()
    process_input_count(config_lines)
    modules = setup_modules(config_lines)
    simulation = Simulation(modules)
    button_presses = simulation.run_simulation_until_rx()
    print(f"❗️❗️ Number of button presses required to activate the Rx: {button_presses}")

if __name__ == "__main__":
    # test_count_pulses_in_the_circuit_a()
    # test_count_pulses_in_the_circuit_b()
    # part_one()
    part_two()

---

p.s: I am deliberating not adding answers here so you can actually spend some time trying to understand how we solved the problem!

Feel free to checkout code on my Github repo and try to set it up and run on your machine 👇

GitHub - jatinkrmalik/advent-of-code-2023: Well, here’s my attempt to solve all 25 problems of…
Well, here’s my attempt to solve all 25 problems of Advent of Code 2023 with Python! 🎄 - GitHub …github.com