From c916e90600d66a344c68d9ac54fb852edfd85d32 Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Wed, 20 Dec 2023 23:15:33 +0200 Subject: Day 20 part 1 --- 2023/src/bin/day_20.rs | 246 +++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 237 insertions(+), 9 deletions(-) (limited to '2023/src/bin') diff --git a/2023/src/bin/day_20.rs b/2023/src/bin/day_20.rs index b3a610b..bbfead8 100644 --- a/2023/src/bin/day_20.rs +++ b/2023/src/bin/day_20.rs @@ -1,19 +1,247 @@ -use nom::IResult; -use std::fs; +use nom::{ + branch::alt, + bytes::complete::tag, + character::complete::{alpha1, line_ending}, + combinator::{map, map_res, value}, + multi::separated_list1, + sequence::{delimited, pair, preceded, separated_pair, tuple}, + IResult, +}; +use std::{ + collections::{BTreeMap, VecDeque}, + fs, + num::ParseIntError, +}; fn main() -> Result<(), Box> { - let input = fs::read_to_string("inputs/day_2.txt")?; - let parsed = Example::parser(&input).unwrap().1; - dbg!(&parsed); + let input = fs::read_to_string("inputs/day_20.txt")?; + let circuit = Circuit::parser(&input).unwrap().1; + + { + let mut circuit = circuit.clone(); + let mut pulse_tracker = PulseCounter::default(); + + for _ in 0..1000 { + circuit.push_the_button(&mut pulse_tracker); + } + dbg!(pulse_tracker.low_pulse_count * pulse_tracker.high_pulse_count); + } + + { + let mut circuit = circuit.clone(); + let mut pulse_tracker = RxWatcher::default(); + + let mut i = 0; + while !pulse_tracker.rx_got_a_low_pulse { + circuit.push_the_button(&mut pulse_tracker); + i += 1; + } + dbg!(i, pulse_tracker); + } Ok(()) } +#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] +struct ModuleId(u32); + +#[derive(Debug, Clone)] +struct Circuit { + broadcaster: Vec, + modules: BTreeMap, +} + +#[derive(Debug, Clone)] +struct Module { + id: ModuleId, + outs: Vec, + state: ModuleState, +} + +#[derive(Debug, Clone)] +enum ModuleState { + FlipFlop(bool), + Conjunction(BTreeMap), +} + +#[derive(Debug, Default)] +struct PulseCounter { + pulses: VecDeque, + low_pulse_count: u64, + high_pulse_count: u64, +} + #[derive(Debug)] -struct Example; +struct RxWatcher { + pulses: VecDeque, + rx_module_id: ModuleId, + rx_got_a_low_pulse: bool, +} + +impl Default for RxWatcher { + fn default() -> Self { + RxWatcher { + pulses: VecDeque::default(), + rx_module_id: ModuleId::from_short_alphanumeric("rx").unwrap(), + rx_got_a_low_pulse: false, + } + } +} + +#[derive(Debug)] +struct Pulse { + state: bool, + input: ModuleId, + output: ModuleId, +} + +impl Circuit { + fn parser(input: &str) -> IResult<&str, Self> { + map( + tuple(( + separated_list1(line_ending, Module::parser), + delimited( + line_ending, + preceded(tag("broadcaster -> "), Module::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(); + 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(); + } + } + + Circuit { + broadcaster, + modules: modules.into_iter().map(|m| (m.id, m)).collect(), + } + }, + )(input) + } + + fn push_the_button(&mut self, pulse_tracker: &mut impl PulseTracker) { + pulse_tracker.button_pulse(); + for b in &self.broadcaster { + pulse_tracker.push(Pulse { + state: false, + input: ModuleId::broadcaster(), + 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 + } + } + 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, + }); + } + } + } + } + } +} + +trait PulseTracker { + fn button_pulse(&mut self); + fn push(&mut self, pulse: Pulse); + fn pop(&mut self) -> Option; +} + +impl PulseTracker for PulseCounter { + fn button_pulse(&mut self) { + self.low_pulse_count += 1; + } + + fn push(&mut self, pulse: Pulse) { + if pulse.state { + self.high_pulse_count += 1; + } else { + self.low_pulse_count += 1; + } + self.pulses.push_back(pulse); + } + + fn pop(&mut self) -> Option { + self.pulses.pop_front() + } +} + +impl PulseTracker for RxWatcher { + fn button_pulse(&mut self) {} + + fn push(&mut self, pulse: Pulse) { + if !pulse.state && pulse.output == self.rx_module_id { + self.rx_got_a_low_pulse = true; + } + self.pulses.push_back(pulse); + } + + fn pop(&mut self) -> Option { + self.pulses.pop_front() + } +} + +impl Module { + fn parser(input: &str) -> IResult<&str, Self> { + map( + separated_pair( + pair( + alt(( + value(ModuleState::FlipFlop(false), tag("%")), + value(ModuleState::Conjunction(BTreeMap::new()), tag("&")), + )), + map_res(alpha1, |id: &str| ModuleId::from_short_alphanumeric(id)), + ), + tag(" -> "), + Module::outs_parser, + ), + |((state, id), outs)| Module { id, state, outs }, + )(input) + } + + fn outs_parser(input: &str) -> IResult<&str, Vec> { + separated_list1( + tag(", "), + map_res(alpha1, |s: &str| ModuleId::from_short_alphanumeric(s)), + )(input) + } +} + +impl ModuleId { + fn broadcaster() -> ModuleId { + ModuleId(0) + } -impl Example { - fn parser(_input: &str) -> IResult<&str, Self> { - todo!() + fn from_short_alphanumeric(s: &str) -> Result { + u32::from_str_radix(s, 36).map(ModuleId) } } -- cgit v1.2.3