From fe30a88b050ada70eb5922e4a036a45da5808dbc Mon Sep 17 00:00:00 2001 From: Jesse Luehrs Date: Wed, 20 Dec 2023 03:03:20 -0500 Subject: day 20 part 1 --- benches/2023.rs | 5 ++ data/2023/20.txt | 58 +++++++++++++++ src/bin/2023/day20.rs | 190 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/bin/2023/main.rs | 2 + 4 files changed, 255 insertions(+) create mode 100644 data/2023/20.txt create mode 100644 src/bin/2023/day20.rs diff --git a/benches/2023.rs b/benches/2023.rs index 2a3af58..4a64397 100644 --- a/benches/2023.rs +++ b/benches/2023.rs @@ -39,6 +39,8 @@ mod day17; mod day18; #[path = "../src/bin/2023/day19.rs"] mod day19; +#[path = "../src/bin/2023/day20.rs"] +mod day20; // NEXT MOD day!(2023, 1, day1); @@ -60,6 +62,7 @@ day!(2023, 16, day16); day!(2023, 17, day17); day!(2023, 18, day18); day!(2023, 19, day19); +day!(2023, 20, day20); // NEXT DAY fn bench_2023(c: &mut criterion::Criterion) { @@ -84,6 +87,7 @@ fn bench_2023(c: &mut criterion::Criterion) { day_combined!(2023, 17, day17); day_combined!(2023, 18, day18); day_combined!(2023, 19, day19); + day_combined!(2023, 20, day20); // NEXT DAY COMBINED }) }); @@ -111,5 +115,6 @@ criterion::criterion_main!( bench_2023day17, bench_2023day18, bench_2023day19, + bench_2023day20, // NEXT GROUP ); diff --git a/data/2023/20.txt b/data/2023/20.txt new file mode 100644 index 0000000..cc46c64 --- /dev/null +++ b/data/2023/20.txt @@ -0,0 +1,58 @@ +%nd -> fs +%ql -> qz +%gz -> vv +%lg -> zx, lx +%tr -> sd +%vn -> ql, qz +%kg -> xz +%sj -> gs +&bq -> rx +%hf -> xm +%vv -> mq, db +%gf -> fn, lx +%zt -> sk +%bm -> lx, cp +%cp -> lx, gb +%gs -> gq, qz +%sp -> db, jh +%bh -> kr, db +%xb -> qz, vn +%fx -> qf +%gq -> qz, xb +%xp -> zn, sd +%hl -> tr, sd +%sk -> nd +%mh -> xs, sd +&qz -> nd, sj, sk, gp, gc, vh, zt +&vg -> bq +%sh -> pz +%jh -> kg +&kp -> bq +%gp -> zt +&gc -> bq +%xf -> xp +%cv -> sd, hl +&db -> kg, sp, kp, fx, jh, gz +%kr -> db +%xz -> zs, db +%fs -> qz, sj +%xm -> kh, lx +%qf -> db, gz +%fn -> bm +%kh -> lx, gf +%vh -> qz, gp +%mq -> bh, db +%zn -> cv +%sv -> xf, sd +%lh -> lx +%dl -> lh, lx +%zx -> lx, hf +%pz -> sd, cn +%cn -> sd, sv +%xs -> sh +%gb -> lx, dl +&tx -> bq +&sd -> mh, tx, sh, xf, zn, xs +&lx -> fn, hf, vg, lg +%zs -> db, fx +broadcaster -> vh, sp, lg, mh diff --git a/src/bin/2023/day20.rs b/src/bin/2023/day20.rs new file mode 100644 index 0000000..045c07b --- /dev/null +++ b/src/bin/2023/day20.rs @@ -0,0 +1,190 @@ +#![allow(dead_code)] +#![allow(unused_variables)] + +use advent_of_code::prelude::*; + +pub enum ModuleType { + Broadcast, + FlipFlop(bool), + Conjunction(HashMap), +} + +pub struct Module { + name: String, + ty: ModuleType, + destinations: Vec, + low_pulses: i64, + high_pulses: i64, +} + +impl std::str::FromStr for Module { + type Err = anyhow::Error; + + fn from_str(s: &str) -> std::result::Result { + let mut parts = s.split(" -> "); + let module_name = parts.next().unwrap(); + let destinations = parts.next().unwrap(); + let destinations: Vec<_> = + destinations.split(", ").map(|s| s.to_string()).collect(); + let (ty, name) = match module_name.chars().next().unwrap() { + '&' => ( + ModuleType::Conjunction(HashMap::new()), + module_name.chars().skip(1).collect(), + ), + '%' => ( + ModuleType::FlipFlop(false), + module_name.chars().skip(1).collect(), + ), + _ => { + if module_name == "broadcaster" { + (ModuleType::Broadcast, module_name.to_string()) + } else { + bail!("failed to parse module {module_name}") + } + } + }; + + Ok(Self { + name, + ty, + destinations, + low_pulses: 0, + high_pulses: 0, + }) + } +} + +pub struct Network { + modules: HashMap, +} + +impl Network { + fn pulse(&mut self) { + let mut pulses = VecDeque::new(); + pulses.push_front(("".to_string(), "broadcaster".to_string(), false)); + while let Some((src, dest, high)) = pulses.pop_back() { + let module = self.modules.get_mut(&dest).unwrap(); + + if high { + module.high_pulses += 1; + } else { + module.low_pulses += 1; + } + + let mut pulse = None; + match module.ty { + ModuleType::Broadcast => { + pulse = Some(high); + } + ModuleType::FlipFlop(ref mut on) => { + if !high { + *on = !*on; + pulse = Some(*on); + } + } + ModuleType::Conjunction(ref mut inputs) => { + *inputs.get_mut(&src).unwrap() = high; + pulse = Some(!inputs.values().all(|high| *high)); + } + } + + if let Some(pulse) = pulse { + for new_dest in module.destinations.clone() { + pulses.push_back((dest.to_string(), new_dest, pulse)); + } + } + } + } +} + +impl std::str::FromStr for Network { + type Err = anyhow::Error; + + fn from_str(s: &str) -> std::result::Result { + let mut modules: HashMap<_, _> = s + .trim() + .split('\n') + .map(|s| { + let module: Module = s.parse()?; + Ok::<_, Self::Err>((module.name.clone(), module)) + }) + .collect::>()?; + let module_names: Vec<_> = modules.keys().cloned().collect(); + for name in module_names { + let destinations = modules[&name].destinations.clone(); + for dest in destinations { + if let Some(ModuleType::Conjunction(ref mut inputs)) = + modules.get_mut(&dest).map(|module| &mut module.ty) + { + inputs.insert(name.clone(), false); + } + } + } + let destinations: HashSet = modules + .values() + .flat_map(|module| module.destinations.iter()) + .cloned() + .collect(); + for destination in destinations { + if !modules.contains_key(&destination) { + modules.insert( + destination.clone(), + Module { + name: destination, + ty: ModuleType::Broadcast, + destinations: vec![], + low_pulses: 0, + high_pulses: 0, + }, + ); + } + } + Ok(Self { modules }) + } +} + +pub fn parse(mut fh: File) -> Result { + let mut s = String::new(); + fh.read_to_string(&mut s)?; + s.parse() +} + +pub fn part1(mut network: Network) -> Result { + for _ in 0..1000 { + network.pulse(); + } + Ok(network + .modules + .values() + .map(|module| module.low_pulses) + .sum::() + * network + .modules + .values() + .map(|module| module.high_pulses) + .sum::()) +} + +pub fn part2(_: Network) -> Result { + // let mut count = 0; + // loop { + // network.pulse(); + // count += 1; + // if network.modules.get("rx").unwrap().low_pulses > 0 { + // return Ok(count); + // } + // } + todo!() +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2023, 20).unwrap()).unwrap()).unwrap(), + 681194780 + ); + assert_eq!( + part2(parse(parse::data(2023, 20).unwrap()).unwrap()).unwrap(), + 0 + ); +} diff --git a/src/bin/2023/main.rs b/src/bin/2023/main.rs index 1afb78e..14dc028 100644 --- a/src/bin/2023/main.rs +++ b/src/bin/2023/main.rs @@ -30,6 +30,7 @@ mod day16; mod day17; mod day18; mod day19; +mod day20; // NEXT MOD #[paw::main] @@ -55,6 +56,7 @@ fn main(opt: Opt) -> Result<()> { 17 => advent_of_code::day!(2023, opt.day, opt.puzzle, day17), 18 => advent_of_code::day!(2023, opt.day, opt.puzzle, day18), 19 => advent_of_code::day!(2023, opt.day, opt.puzzle, day19), + 20 => advent_of_code::day!(2023, opt.day, opt.puzzle, day20), // NEXT PART _ => panic!("unknown day {}", opt.day), } -- cgit v1.2.3