From de87554bf2ddb5716806608705b549e0732f431d Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Thu, 21 Dec 2023 09:12:56 +0200 Subject: Do the whole day 20 with less pointer indirection to heap allocated stuff --- 2023/src/bin/day_20.rs | 189 ++++++++++++++++++++++++++++++++----------------- 1 file changed, 126 insertions(+), 63 deletions(-) (limited to '2023/src') 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> { 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> { { 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, - modules: BTreeMap, + modules: Vec, } #[derive(Debug, Clone)] -struct Module { +struct ParsedModule { id: ModuleId, outs: Vec, state: ModuleState, } +#[derive(Debug, Clone)] +struct Module { + id: ModuleId, + index: usize, + outs: Vec, + state: ModuleState, +} + #[derive(Debug, Clone)] enum ModuleState { FlipFlop(bool), - Conjunction(BTreeMap), + Conjunction(u64), + Sink, } #[derive(Debug, Default)] @@ -74,15 +86,15 @@ struct PulseCounter { #[derive(Debug)] struct RxWatcher { pulses: VecDeque, - 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 = - 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 = 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 = 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 = 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 { u32::from_str_radix(s, 36).map(ModuleId) } -- cgit v1.2.3