Day 20: Pulse Propagation

I used dot to visualize the input, so I could recognize that they were LFSR-like counters. I wasn't sure if they would have a simple cycle, so I output some of the sequences to CSV to grub through manually. Once I figured out the cycles part, the rest was pretty straightforward.

# Advent of Code 2023
# Day 20: Pulse Propagation

from math import lcm

class FlipFlop:
    def __init__(self, destinations):
        self.destinations = destinations
        self.on = False

    def recieve(self, name, pulse):
        if pulse == "low":
            self.on = not self.on

            if self.on:
                return [(name, "high") for name in self.destinations]
            else:
                return [(name, "low") for name in self.destinations]
        else:
            return []

class Conjunction:
    def __init__(self, destinations):
        self.destinations = destinations
    
    def init_memory(self, connected_modules):
        self.memory = {name: "low" for name in connected_modules}

    def recieve(self, name, pulse):
        self.memory[name] = pulse

        if all(pulse == "high" for pulse in self.memory.values()):
            return [(name, "low") for name in self.destinations]
        else:
            return [(name, "high") for name in self.destinations]

modules = {}
conjunctions = {}

with open("inputs/day_20.txt") as file:
    for line in file:
        if line.startswith("broadcaster"):
            starting_destinations = (
                line.split(" -> ")[1].rstrip("\n").split(", ")
            )
        else:
            halves = line.split(" -> ")
            kind = (FlipFlop, Conjunction)[halves[0][0] == "&"]
            name = halves[0][1:]
            destinations = halves[1].rstrip("\n").split(", ")

            modules[name] = kind(destinations)

            if kind == Conjunction:
                conjunctions[name] = modules[name]

            if "rx" in destinations:
                final_conjunction = modules[name]

for conjunction_name, conjunction in conjunctions.items():
    connected_modules = []

    if conjunction_name in starting_destinations:
        connected_modules.append("broadcaster")

    for name, module in modules.items():
        if conjunction_name in module.destinations:
            connected_modules.append(name)

    conjunction.init_memory(connected_modules)

low_pulses = 1000
high_pulses = 0

presses = 1
cycles = {name:None for name in final_conjunction.memory}

while presses <= 1000 or any(cycle is None for cycle in cycles.values()):
    pulses = [("broadcaster", name, "low") for name in starting_destinations]

    while pulses:
        next_pulses = []

        for pulse in pulses:
            if (
                pulse[0] in cycles and pulse[2] == "high"
                and cycles[pulse[0]] is None
            ):
                cycles[pulse[0]] = presses

            if pulse[1] in modules:
                for next_pulse in modules[pulse[1]].recieve(
                    pulse[0], pulse[2]
                ):
                    next_pulses.append((pulse[1],) + next_pulse)

            if presses <= 1000:
                if pulse[2] == "low":
                    low_pulses += 1
                else:
                    high_pulses += 1

        pulses = next_pulses

    presses += 1

print(f"Part 1: {low_pulses * high_pulses}")
print(f"Part 2: {lcm(*cycles.values())}")

Part 1 was fun, but I have no idea how to solve part 2. Made a visualization of my graph, which shows several nasty cycles, and noticed that every second button press seems to repeat the same sequence for my input, but none of my attempts to suss out any regularity besides that came to fruition. Tried to see if there are any cycles for sub-graphs, but that didn't work, and I made all kinds of crazy guesses -- up to and including importing a SAT solver library to try and work backwards from the output before taking a step back and realizing that that can't possibly be required....

pub fn part1(input: PuzzleInput) -> isize {
    let mut sim = CircuitSim::new(input);
    let mut low_pulses = 0;
    let mut high_pulses = 0;

    for i in 0..1000 {
        sim.button();

        while sim.tick() {
            // Nothing to do here
        }

        let pulses = sim
            .pulse_sequence
            .iter()
            .map(|(_, pulse, _)| pulse)
            .collect::<Vec<_>>();

        low_pulses += pulses.iter().filter(|&pulse| **pulse == Pulse::Low).count();
        high_pulses += pulses
            .iter()
            .filter(|&pulse| **pulse == Pulse::High)
            .count();
    }

    (low_pulses * high_pulses) as isize
}

#[derive(Clone, Debug)]
pub struct CircuitSim {
    pub modules: HashMap<String, Module>,
    pub queue: VecDeque<(String, Pulse, String)>,
    pub pulse_sequence: Vec<(String, Pulse, String)>,
    pub button_presses: usize,
}

    pub fn tick(&mut self) -> bool {
        if self.queue.is_empty() {
            return false;
        }

        let (from, pulse, name) = self.queue.pop_front().unwrap();

        self.pulse_sequence
            .push((from.clone(), pulse.clone(), name.clone()));

        if let Some(module) = self.modules.get_mut(&name) {
            for output in &module.outputs {
                match module.state {
                    ModuleState::Broadcaster => {
                        self.queue.push_back((
                            "broadcaster".to_string(),
                            pulse.clone(),
                            output.clone(),
                        ));
                    }

                    ModuleState::FlipFlop { ref mut on } => {
                        if pulse == Pulse::Low {
                            if *on {
                                self.queue
                                    .push_back((name.clone(), Pulse::Low, output.clone()));
                            } else {
                                self.queue
                                    .push_back((name.clone(), Pulse::High, output.clone()));
                            }
                        }
                    }

                    ModuleState::Conjunction {
                        memory: ref mut cur_memory,
                    } => {
                        cur_memory.insert(from.clone(), pulse.clone());

                        let pulse = if cur_memory.values().all(|pulse| pulse == &Pulse::High) {
                            Pulse::Low
                        } else {
                            Pulse::High
                        };

                        self.queue.push_back((name.clone(), pulse, output.clone()));
                    }
                }
            }

            match module.state {
                ModuleState::Broadcaster => {}

                ModuleState::FlipFlop { ref mut on } => {
                    if pulse == Pulse::Low {
                        *on = !*on;
                    }
                }

                ModuleState::Conjunction { memory: ref mut m } => {}
            }
        }

        true
    }
}