Advent of Code 2023 Day 20

Day 20: Pulse Propagation

https://adventofcode.com/2023/day/20

The elves fixed the sand machines, but they need to be booted up.

The machines are connected with cables, and each machine has a communication module attached to it.

Those modules communicate using pulses, either a high pulse, of a low pulse.

A module sends its pulse to all of its destination modules.

Today’s input describes to grid of modules.

An example input looks like this:

input.txt

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

Each line describes a module:

To the left of the arrow is the source module.
To the right of the arrow are its destination modules

A module can have several types:

A flipflop module, its name is prefixed with a %
A conjugation module, its name is prefixed with a &
The broadcaster module, each grid has one of these

Module behaviour

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.

The button module. When you push the button, a single low pulse is sent directly to the broadcaster module.

Pulses are processed in the order they are sent. In other words, every time a pulse is sent, push onto the back of queue. The next pulse to be processed is the next pulse you pop off the front of the queue.

Parsing

I parsed the input into 2 maps.

From a name to a list of destinations
From a name to a module

A module:

enum Module<'a> {
    FlipFlop {
        on: bool,
    },
    Conjunction {
        memory: HashMap<&'a str, PulseStrength>,
    },
    Broadcaster,
}

A flipflop module has an internal boolean to determine if it’s on.

The memory of a conjugation module keeps track of the previous strength each of its input modules sent previously.

enum PulseStrength {
    Low,
    High,
}

fn parse_line(s: &str) -> (&str, Module, Vec<&str>) {
    let (lhs, rhs) = s.split_once(" -> ").unwrap();
    let outputs: Vec<&str> = rhs.split(", ").collect();
    let module = match &lhs[0..1] {
        "b" => Module::Broadcaster,
        // Flipflop modules are initially off.
        "%" => Module::FlipFlop { on: false },
        "&" => Module::Conjunction {
            memory: HashMap::new(),
        },
        _ => panic!(),
    };
    let name = if module == Module::Broadcaster {
        lhs
    } else {
        &lhs[1..]
    };

    (name, module, outputs)
}

fn parse(input: &str) -> (HashMap<&str, Vec<&str>>, HashMap<&str, Module>) {
    let mut destmap = HashMap::new();
    let mut modulemap = HashMap::new();

    for (name, module, destinations) in input.lines().map(|line| parse_line(line)) {
        modulemap.insert(name, module);
        destmap.insert(name, destinations);
    }

    // set the initial remembered pulses to a low pulse for every module that's connected to a conjuction module
    for (source, destinations) in &destmap {
        for destination in destinations {
            if let Some(Module::Conjunction { memory }) = modulemap.get_mut(destination) {
                memory.insert(source, PulseStrength::Low);
            }
        }
    }

    (destmap, modulemap)
}

Part 1

Press the button 1000 times. The question asks what you get if you multiply the total number of low pulses sent by the total number of high pulses sent?

Helpers

The queue holds a Pulses:

struct Pulse<'a> {
    from: &'a str,
    to: &'a str,
    strength: PulseStrength,
}

A method on Pulse that allows it to be sent. It figures out which pulse strength it would send (if any), and then sends that pulse to all of its destinations (by pushing a new Pulse onto the queue).

impl<'a> Pulse<'a> {
    fn send(
        self,
        modulemap: &mut HashMap<&'a str, Module>,
        destmap: &HashMap<&'a str, Vec<&'a str>>,
        q: &mut VecDeque<Pulse<'a>>,
    ) {
        let Some(module) = modulemap.get_mut(self.to) else {
            // hit the rx module, it doesn't send anything
            return;
        };

        // figure out which pulse to send, if any
        let send = match module {
            Module::FlipFlop { on } => match self.strength {
                // If a flip-flop module receives a high pulse, it is ignored and nothing happens.
                PulseStrength::High => None,
                // 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.
                PulseStrength::Low => {
                    *on = !*on;
                    let strength = if *on {
                        PulseStrength::High
                    } else {
                        PulseStrength::Low
                    };
                    Some(strength)
                }
            },
            Module::Conjunction { memory } => {
                // When a pulse is received, the conjunction module first updates its memory for that input.
                *memory.get_mut(self.from).unwrap() = self.strength;
                // then, if it remembers high pulses for all inputs, it sends a low pulse; otherwise, it sends a high pulse.
                let strength = if memory
                    .values()
                    .all(|&strength| strength == PulseStrength::High)
                {
                    PulseStrength::Low
                } else {
                    PulseStrength::High
                };
                Some(strength)
            }
            // There is a single broadcast module (named broadcaster).
            // When it receives a pulse, it sends the same pulse to all of its destination modules.
            Module::Broadcaster => Some(self.strength),
        };

        // send pulses to all destinations
        if let Some(strength) = send {
            for &to in destmap.get(self.to).unwrap() {
                let pulse = Pulse {
                    from: self.to,
                    to,
                    strength,
                };
                q.push_back(pulse);
            }
        };
    }
}

Code

day_20.rs

pub fn part_1(input: &str) -> u64 {
    let (destmap, mut modulemap) = parse(input);

    let mut low_count = 0;
    let mut high_count = 0;

    for _ in 0..1_000 {
        let mut q = VecDeque::new();
        q.push_back(Pulse {
            from: "button",
            to: "broadcaster",
            strength: PulseStrength::Low,
        });
        while let Some(pulse) = q.pop_front() {
            match pulse.strength {
                PulseStrength::Low => low_count += 1,
                PulseStrength::High => high_count += 1,
            }
            pulse.send(&mut modulemap, &destmap, &mut q)
        }
    }

    low_count * high_count
}

Part 2

The final module is named "rx". The machine turns on when a single low pulse is sent to "rx".

The question asks what the fewest number of button presses required to deliver a single low pulse to the module named rx is.

This part required some investigation of the input file.

The singular module before "rx" is always a conjugation module.

So if all modules connected to that module have previously sent a high strength signal, it will send a low strength signal.

That’s the condition to look for, after how many button presses does that happen?

I kept track of how many button presses it takes for each module connected to that final conjugation module to send a high signal.

If I’ve seen all those modules sent a high signal, I determine when they would have all sent one previously.

Like previous days, this is the least common multiple of all individual button presses.

Helpers

A way to calculate the least common multiple of 2 numbers:

fn gcd(mut a: u64, mut b: u64) -> u64 {
    while b != 0 {
        let tmp = a;
        a = b;
        b = tmp % b;
    }
    a
}

fn lcm(a: u64, b: u64) -> u64 {
    a * b / gcd(a, b)
}

Code

day_20.rs

pub fn part_2(input: &str) -> u64 {
    let (destmap, mut modulemap) = parse(input);
    let (before_rx, _) = destmap
        .iter()
        .find(|(_, destinations)| destinations.contains(&"rx"))
        .unwrap();
    let Module::Conjunction { memory } = modulemap.get(before_rx).unwrap() else {
        panic!("module before rx should be a conjunction")
    };

    // since the module before rx is a conjunction, is needs all its inputs to have sent a high signal in order to send a low signal
    // remember after how many presses an input to before_rx sent a high signal
    let mut tracker: HashMap<&str, Option<u64>> = memory.keys().map(|&name| (name, None)).collect();

    for presses in 1.. {
        let mut q = VecDeque::new();
        q.push_back(Pulse {
            from: "button",
            to: "broadcaster",
            strength: PulseStrength::Low,
        });

        while let Some(pulse) = q.pop_front() {
            if pulse.to == *before_rx && pulse.strength == PulseStrength::High {
                *tracker.get_mut(pulse.from).unwrap() = Some(presses);
                // if all inputs to before_rx have a known presscount, figure out when they all send a high signal at the same time
                if tracker.values().all(|presses| presses.is_some()) {
                    return tracker
                        .values()
                        .map(|presses| presses.unwrap())
                        .fold(1, |acc, curr| lcm(acc, curr));
                }
            }

            pulse.send(&mut modulemap, &destmap, &mut q)
        }
    }

    panic!("No solution")
}

Final code

day_20.rs

1use std::collections::{HashMap, VecDeque};
2
3#[derive(Debug, Clone, PartialEq, Eq)]
4enum Module<'a> {
5    FlipFlop {
6        on: bool,
7    },
8    Conjunction {
9        memory: HashMap<&'a str, PulseStrength>,
10    },
11    Broadcaster,
12}
13
14#[derive(Debug, Clone, Copy)]
15struct Pulse<'a> {
16    from: &'a str,
17    to: &'a str,
18    strength: PulseStrength,
19}
20
21impl<'a> Pulse<'a> {
22    fn send(
23        self,
24        modulemap: &mut HashMap<&'a str, Module>,
25        destmap: &HashMap<&'a str, Vec<&'a str>>,
26        q: &mut VecDeque<Pulse<'a>>,
27    ) {
28        let Some(module) = modulemap.get_mut(self.to) else {
29            // hit the rx module, it doesn't send anything
30            return;
31        };
32
33        // figure out which pulse to send, if any
34        let send = match module {
35            Module::FlipFlop { on } => match self.strength {
36                // If a flip-flop module receives a high pulse, it is ignored and nothing happens.
37                PulseStrength::High => None,
38                // However, if a flip-flop module receives a low pulse, it flips between on and off.
39                // If it was off, it turns on and sends a high pulse. If it was on, it turns off and sends a low pulse.
40                PulseStrength::Low => {
41                    *on = !*on;
42                    let strength = if *on {
43                        PulseStrength::High
44                    } else {
45                        PulseStrength::Low
46                    };
47                    Some(strength)
48                }
49            },
50            Module::Conjunction { memory } => {
51                // When a pulse is received, the conjunction module first updates its memory for that input.
52                *memory.get_mut(self.from).unwrap() = self.strength;
53                // then, if it remembers high pulses for all inputs, it sends a low pulse; otherwise, it sends a high pulse.
54                let strength = if memory
55                    .values()
56                    .all(|&strength| strength == PulseStrength::High)
57                {
58                    PulseStrength::Low
59                } else {
60                    PulseStrength::High
61                };
62                Some(strength)
63            }
64            // There is a single broadcast module (named broadcaster).
65            // When it receives a pulse, it sends the same pulse to all of its destination modules.
66            Module::Broadcaster => Some(self.strength),
67        };
68
69        // send pulses to all destinations
70        if let Some(strength) = send {
71            for &to in destmap.get(self.to).unwrap() {
72                let pulse = Pulse {
73                    from: self.to,
74                    to,
75                    strength,
76                };
77                q.push_back(pulse);
78            }
79        };
80    }
81}
82
83#[derive(Debug, Clone, Copy, PartialEq, Eq)]
84enum PulseStrength {
85    Low,
86    High,
87}
88
89fn parse_line(s: &str) -> (&str, Module, Vec<&str>) {
90    let (lhs, rhs) = s.split_once(" -> ").unwrap();
91    let outputs: Vec<&str> = rhs.split(", ").collect();
92    let module = match &lhs[0..1] {
93        "b" => Module::Broadcaster,
94        "%" => Module::FlipFlop { on: false },
95        "&" => Module::Conjunction {
96            memory: HashMap::new(),
97        },
98        _ => panic!(),
99    };
100    let name = if module == Module::Broadcaster {
101        lhs
102    } else {
103        &lhs[1..]
104    };
105
106    (name, module, outputs)
107}
108
109fn parse(input: &str) -> (HashMap<&str, Vec<&str>>, HashMap<&str, Module>) {
110    let mut destmap = HashMap::new();
111    let mut modulemap = HashMap::new();
112
113    for (name, module, destinations) in input.lines().map(|line| parse_line(line)) {
114        modulemap.insert(name, module);
115        destmap.insert(name, destinations);
116    }
117
118    // set the initial remembered pulses to a low pulse for every module that's connected to a conjuction module
119    for (source, destinations) in &destmap {
120        for destination in destinations {
121            if let Some(Module::Conjunction { memory }) = modulemap.get_mut(destination) {
122                memory.insert(source, PulseStrength::Low);
123            }
124        }
125    }
126
127    (destmap, modulemap)
128}
129
130fn gcd(mut a: u64, mut b: u64) -> u64 {
131    while b != 0 {
132        let tmp = a;
133        a = b;
134        b = tmp % b;
135    }
136    a
137}
138
139fn lcm(a: u64, b: u64) -> u64 {
140    a * b / gcd(a, b)
141}
142
143pub fn part_1(input: &str) -> u64 {
144    let (destmap, mut modulemap) = parse(input);
145
146    let mut low_count = 0;
147    let mut high_count = 0;
148
149    for _ in 0..1_000 {
150        let mut q = VecDeque::new();
151        q.push_back(Pulse {
152            from: "button",
153            to: "broadcaster",
154            strength: PulseStrength::Low,
155        });
156        while let Some(pulse) = q.pop_front() {
157            match pulse.strength {
158                PulseStrength::Low => low_count += 1,
159                PulseStrength::High => high_count += 1,
160            }
161            pulse.send(&mut modulemap, &destmap, &mut q)
162        }
163    }
164
165    low_count * high_count
166}
167
168pub fn part_2(input: &str) -> u64 {
169    let (destmap, mut modulemap) = parse(input);
170    let (before_rx, _) = destmap
171        .iter()
172        .find(|(_, destinations)| destinations.contains(&"rx"))
173        .unwrap();
174    let Module::Conjunction { memory } = modulemap.get(before_rx).unwrap() else {
175        panic!("module before rx should be a conjunction")
176    };
177
178    // since the module before rx is a conjunction, is needs all its inputs to have sent a high signal in order to send a low signal
179    // remember after how many presses an input to before_rx sent a high signal
180    let mut tracker: HashMap<&str, Option<u64>> = memory.keys().map(|&name| (name, None)).collect();
181
182    for presses in 1.. {
183        let mut q = VecDeque::new();
184        q.push_back(Pulse {
185            from: "button",
186            to: "broadcaster",
187            strength: PulseStrength::Low,
188        });
189
190        while let Some(pulse) = q.pop_front() {
191            if pulse.to == *before_rx && pulse.strength == PulseStrength::High {
192                *tracker.get_mut(pulse.from).unwrap() = Some(presses);
193                // if all inputs to before_rx have a known presscount, figure out when they all send a high signal at the same time
194                if tracker.values().all(|presses| presses.is_some()) {
195                    return tracker
196                        .values()
197                        .map(|presses| presses.unwrap())
198                        .fold(1, |acc, curr| lcm(acc, curr));
199                }
200            }
201
202            pulse.send(&mut modulemap, &destmap, &mut q)
203        }
204    }
205
206    panic!("No solution")
207}

Date

Last update

By

Tagged

Part of series

Older post

Newer post

Advent of Code 2023 Day 20

Day 20: Pulse Propagation

Module behaviour

Parsing

Part 1

Helpers

Code

Part 2

Helpers

Code

Final code