Do the whole day 20 with less pointer indirection to heap allocated stuff

2 files changed, 127 insertions, 64 deletions

diff --git a/2023/inputs/day_20.txt b/2023/inputs/day_20.txt
index 98713c2..4fc0eab 100644
--- a/2023/inputs/day_20.txt
+++ b/2023/inputs/day_20.txt
@@ -1,3 +1,4 @@
+broadcaster -> sr, ch, hd, bx
 %cv -> xz
 %kt -> qx, rz
 %cb -> kt
@@ -24,7 +25,6 @@
 %sb -> ks, vc
 %ln -> gf, qq
 %bx -> qx, qp
-broadcaster -> sr, ch, hd, bx
 %ch -> db, mc
 %ds -> cc
 &qx -> cb, cv, bx, xz, vm, zl
diff --git a/2023/src/bin/day_20.rs b/2023/src/bin/day_20.rs
index bbfead8..0829365 100644
--- a/2023/src/bin/day_20.rs
+++ b/2023/src/bin/day_20.rs
@@ -4,19 +4,16 @@ use nom::{
     character::complete::{alpha1, line_ending},
     combinator::{map, map_res, value},
     multi::separated_list1,
-    sequence::{delimited, pair, preceded, separated_pair, tuple},
+    sequence::{delimited, pair, separated_pair},
     IResult,
 };
-use std::{
-    collections::{BTreeMap, VecDeque},
-    fs,
-    num::ParseIntError,
-};
+use std::{collections::VecDeque, fs, num::ParseIntError};
 
 fn main() -> Result<(), Box<dyn std::error::Error>> {
     let input = fs::read_to_string("inputs/day_20.txt")?;
     let circuit = Circuit::parser(&input).unwrap().1;
 
+    dbg!(&circuit);
     {
         let mut circuit = circuit.clone();
         let mut pulse_tracker = PulseCounter::default();
@@ -29,7 +26,14 @@ fn main() -> Result<(), Box<dyn std::error::Error>> {
 
     {
         let mut circuit = circuit.clone();
-        let mut pulse_tracker = RxWatcher::default();
+        let mut pulse_tracker = RxWatcher::new(
+            circuit
+                .modules
+                .iter()
+                .find(|m| m.id == ModuleId::from_short_alphanumeric("rx").unwrap())
+                .unwrap()
+                .index,
+        );
 
         let mut i = 0;
         while !pulse_tracker.rx_got_a_low_pulse {
@@ -47,21 +51,29 @@ struct ModuleId(u32);
 
 #[derive(Debug, Clone)]
 struct Circuit {
-    broadcaster: Vec<ModuleId>,
-    modules: BTreeMap<ModuleId, Module>,
+    modules: Vec<Module>,
 }
 
 #[derive(Debug, Clone)]
-struct Module {
+struct ParsedModule {
     id: ModuleId,
     outs: Vec<ModuleId>,
     state: ModuleState,
 }
 
 #[derive(Debug, Clone)]
+struct Module {
+    id: ModuleId,
+    index: usize,
+    outs: Vec<usize>,
+    state: ModuleState,
+}
+
+#[derive(Debug, Clone)]
 enum ModuleState {
     FlipFlop(bool),
-    Conjunction(BTreeMap<ModuleId, bool>),
+    Conjunction(u64),
+    Sink,
 }
 
 #[derive(Debug, Default)]
@@ -74,15 +86,15 @@ struct PulseCounter {
 #[derive(Debug)]
 struct RxWatcher {
     pulses: VecDeque<Pulse>,
-    rx_module_id: ModuleId,
+    rx_module_index: usize,
     rx_got_a_low_pulse: bool,
 }
 
-impl Default for RxWatcher {
-    fn default() -> Self {
+impl RxWatcher {
+    fn new(rx_module_index: usize) -> Self {
         RxWatcher {
             pulses: VecDeque::default(),
-            rx_module_id: ModuleId::from_short_alphanumeric("rx").unwrap(),
+            rx_module_index,
             rx_got_a_low_pulse: false,
         }
     }
@@ -91,79 +103,126 @@ impl Default for RxWatcher {
 #[derive(Debug)]
 struct Pulse {
     state: bool,
-    input: ModuleId,
-    output: ModuleId,
+    input: usize,
+    output: usize,
 }
 
 impl Circuit {
     fn parser(input: &str) -> IResult<&str, Self> {
         map(
-            tuple((
-                separated_list1(line_ending, Module::parser),
+            pair(
                 delimited(
-                    line_ending,
-                    preceded(tag("broadcaster -> "), Module::outs_parser),
+                    tag("broadcaster -> "),
+                    ParsedModule::outs_parser,
                     line_ending,
                 ),
-                separated_list1(line_ending, Module::parser),
-            )),
-            |(modules1, broadcaster, modules2)| {
-                let mut modules: Vec<Module> =
-                    modules1.into_iter().chain(modules2.into_iter()).collect();
+                separated_list1(line_ending, ParsedModule::parser),
+            ),
+            |(broadcaster, parsed_modules)| {
+                let sink_index = parsed_modules.len() + 1;
+                let rx_sink_index = parsed_modules.len() + 2;
+                let mut modules: Vec<Module> = parsed_modules
+                    .iter()
+                    .enumerate()
+                    .map(|(index, module)| Module {
+                        id: module.id,
+                        index: index + 1,
+                        outs: module
+                            .outs
+                            .iter()
+                            .map(|out_id| {
+                                parsed_modules
+                                    .iter()
+                                    .enumerate()
+                                    .find(|(_, out)| &out.id == out_id)
+                                    .map_or(sink_index, |(index, _)| index + 1)
+                            })
+                            .collect(),
+                        state: module.state.clone(),
+                    })
+                    .collect();
+                modules.push(Module {
+                    id: ModuleId::sink(),
+                    index: sink_index,
+                    outs: Vec::new(),
+                    state: ModuleState::Sink,
+                });
+                modules.push(Module {
+                    id: ModuleId::from_short_alphanumeric("rx").unwrap(),
+                    index: rx_sink_index,
+                    outs: Vec::new(),
+                    state: ModuleState::Sink,
+                });
+                modules.insert(
+                    0,
+                    Module {
+                        id: ModuleId::broadcaster(),
+                        index: 0,
+                        outs: broadcaster
+                            .iter()
+                            .map(|mid| modules.iter().find(|m| &m.id == mid).unwrap().index)
+                            .collect(),
+                        state: ModuleState::Sink,
+                    },
+                );
+
                 let modules_snapshot = modules.clone();
 
                 for module in &mut modules {
                     if let ModuleState::Conjunction(ref mut conjunction_state) = module.state {
-                        *conjunction_state = modules_snapshot
-                            .iter()
-                            .filter(|input| input.outs.contains(&module.id))
-                            .map(|input| (input.id, false))
-                            .collect();
+                        for input in &modules_snapshot {
+                            if input.outs.contains(&module.index) {
+                                let mask = !(1 << input.index);
+                                *conjunction_state &= mask;
+                            }
+                        }
                     }
                 }
 
-                Circuit {
-                    broadcaster,
-                    modules: modules.into_iter().map(|m| (m.id, m)).collect(),
-                }
+                Circuit { modules }
             },
         )(input)
     }
 
     fn push_the_button(&mut self, pulse_tracker: &mut impl PulseTracker) {
         pulse_tracker.button_pulse();
-        for b in &self.broadcaster {
+        for b in &self.modules[0].outs {
             pulse_tracker.push(Pulse {
                 state: false,
-                input: ModuleId::broadcaster(),
+                input: 0,
                 output: *b,
             });
         }
 
         while let Some(pulse) = pulse_tracker.pop() {
-            if let Some(module) = self.modules.get_mut(&pulse.output) {
-                let new_pulse_state: Option<bool> = match module.state {
-                    ModuleState::FlipFlop(ref mut current) => {
-                        if !pulse.state {
-                            *current = !*current;
-                            Some(*current)
-                        } else {
-                            None
-                        }
+            let module = &mut self.modules[pulse.output];
+            let new_pulse_state: Option<bool> = match module.state {
+                ModuleState::FlipFlop(ref mut current) => {
+                    if !pulse.state {
+                        *current = !*current;
+                        Some(*current)
+                    } else {
+                        None
                     }
-                    ModuleState::Conjunction(ref mut current) => {
-                        current.insert(pulse.input, pulse.state);
-                        Some(current.values().any(|s| *s == false))
-                    }
-                };
-                if let Some(new_pulse_state) = new_pulse_state {
-                    for out in &module.outs {
-                        pulse_tracker.push(Pulse {
-                            state: new_pulse_state,
-                            input: module.id,
-                            output: *out,
-                        });
+                }
+                ModuleState::Conjunction(ref mut current) => {
+                    let mask = 1 << pulse.input;
+                    if pulse.state {
+                        *current |= mask;
+                    } else {
+                        *current &= !mask;
                     }
+                    Some(*current != u64::MAX)
+                }
+                ModuleState::Sink => None,
+            };
+            if let Some(new_pulse_state) = new_pulse_state {
+                for out in &module.outs {
+                    pulse_tracker.push(Pulse {
+                        state: new_pulse_state,
+                        input: module.index,
+                        output: *out,
+                    });
                 }
             }
         }
@@ -199,7 +258,7 @@ impl PulseTracker for RxWatcher {
     fn button_pulse(&mut self) {}
 
     fn push(&mut self, pulse: Pulse) {
-        if !pulse.state && pulse.output == self.rx_module_id {
+        if !pulse.state && pulse.output == self.rx_module_index {
             self.rx_got_a_low_pulse = true;
         }
         self.pulses.push_back(pulse);
@@ -210,21 +269,21 @@ impl PulseTracker for RxWatcher {
     }
 }
 
-impl Module {
+impl ParsedModule {
     fn parser(input: &str) -> IResult<&str, Self> {
         map(
             separated_pair(
                 pair(
                     alt((
                         value(ModuleState::FlipFlop(false), tag("%")),
-                        value(ModuleState::Conjunction(BTreeMap::new()), tag("&")),
+                        value(ModuleState::Conjunction(u64::MAX), tag("&")),
                     )),
                     map_res(alpha1, |id: &str| ModuleId::from_short_alphanumeric(id)),
                 ),
                 tag(" -> "),
-                Module::outs_parser,
+                ParsedModule::outs_parser,
             ),
-            |((state, id), outs)| Module { id, state, outs },
+            |((state, id), outs)| ParsedModule { id, state, outs },
         )(input)
     }
 
@@ -241,6 +300,10 @@ impl ModuleId {
         ModuleId(0)
     }
 
+    fn sink() -> ModuleId {
+        ModuleId(u32::MAX)
+    }
+
     fn from_short_alphanumeric(s: &str) -> Result<ModuleId, ParseIntError> {
         u32::from_str_radix(s, 36).map(ModuleId)
     }