day 20 part 1HEADmaster

4 files changed, 255 insertions, 0 deletions

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<String, bool>),
+}
+
+pub struct Module {
+    name: String,
+    ty: ModuleType,
+    destinations: Vec<String>,
+    low_pulses: i64,
+    high_pulses: i64,
+}
+
+impl std::str::FromStr for Module {
+    type Err = anyhow::Error;
+
+    fn from_str(s: &str) -> std::result::Result<Self, Self::Err> {
+        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<String, Module>,
+}
+
+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<Self, Self::Err> {
+        let mut modules: HashMap<_, _> = s
+            .trim()
+            .split('\n')
+            .map(|s| {
+                let module: Module = s.parse()?;
+                Ok::<_, Self::Err>((module.name.clone(), module))
+            })
+            .collect::<Result<_, _>>()?;
+        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<String> = 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<Network> {
+    let mut s = String::new();
+    fh.read_to_string(&mut s)?;
+    s.parse()
+}
+
+pub fn part1(mut network: Network) -> Result<i64> {
+    for _ in 0..1000 {
+        network.pulse();
+    }
+    Ok(network
+        .modules
+        .values()
+        .map(|module| module.low_pulses)
+        .sum::<i64>()
+        * network
+            .modules
+            .values()
+            .map(|module| module.high_pulses)
+            .sum::<i64>())
+}
+
+pub fn part2(_: Network) -> Result<i64> {
+    // 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),
     }