From 23de27a26fa3c36d823bb56d1a9718a9233b6b92 Mon Sep 17 00:00:00 2001 From: alex Date: Thu, 21 Dec 2023 00:07:32 +0100 Subject: [PATCH] Day20 - part 1 --- src/day20.rs | 328 +++++++++++++++++++++++++++++++++++++++++++++++++++ src/main.rs | 2 + 2 files changed, 330 insertions(+) create mode 100644 src/day20.rs diff --git a/src/day20.rs b/src/day20.rs new file mode 100644 index 0000000..9765520 --- /dev/null +++ b/src/day20.rs @@ -0,0 +1,328 @@ +use std::io::Read; +use std::error::Error; +use std::fs::File; + +use std::collections::HashMap; +use std::collections::VecDeque; + +pub fn run(input_file: &str) -> Result<(), Box> { + let mut f = File::open(input_file)?; + let mut input = String::new(); + f.read_to_string(&mut input)?; + + let res = run_part1(&input)?; + println!("{res}"); + + let res = run_part2(&input)?; + println!("{res}"); + + Ok(()) +} + +#[derive(Debug, Copy, Clone)] +enum PulseType { + High, + Low, +} + +#[derive(Debug)] +enum ModuleType { + Broadcast(Module), + FlipFlop(ModuleFlipFlop), + Conjunction(ModuleConjunction), +} + +impl ModuleType { + pub fn dst(&self) -> &Vec { + match self { + ModuleType::Broadcast(m) => { + &m.dst + }, + ModuleType::FlipFlop(m) => { + &m.dst + }, + ModuleType::Conjunction(m) => { + &m.dst + }, + _ => unreachable!(), + } + } + + pub fn add_pulse(&mut self, module: String) { + match self { + ModuleType::Broadcast(m) => {}, + ModuleType::FlipFlop(m) => {}, + ModuleType::Conjunction(m) => { + m.pulse_type.insert(module.clone(), PulseType::Low); + }, + _ => unreachable!(), + }; + } + + pub fn is_back_to_start(&self) -> bool { + match self { + ModuleType::Broadcast(m) => true, + ModuleType::FlipFlop(m) => { + m.state == false + }, + ModuleType::Conjunction(m) => { + 0 == m.pulse_type.values().map(|v| { + match v { + PulseType::Low => 0, + PulseType::High => 1, + } + }).sum() + }, + _ => unreachable!(), + } + } +} + +#[derive(Debug)] +struct Module { + dst: Vec, +} + +#[derive(Debug)] +struct ModuleFlipFlop { + dst: Vec, + + // state: true = on + // state: false = off + state: bool, +} + +#[derive(Debug)] +struct ModuleConjunction { + dst: Vec, + pulse_type: HashMap, +} + +impl Module { + pub fn dst(&self) -> &Vec { + &self.dst + } +} + +impl ModuleFlipFlop { + pub fn dst(&self) -> &Vec { + &self.dst + } +} + +impl ModuleConjunction { + pub fn dst(&self) -> &Vec { + &self.dst + } + + pub fn update_pulse(&mut self, module: String, pulse: PulseType) { + //println!("update_pulse: {} {:?}", module, pulse); + self.pulse_type.entry(module).and_modify(|v| *v = pulse); + } +} + +#[derive(Debug)] +struct Puzzle { + config: HashMap, +} + +impl Puzzle { + pub fn new(input: &str) -> Self { + let mut config: HashMap = HashMap::new(); + + let mut conj: Vec = Vec::new(); + + input.lines() + .filter(|l| !l.is_empty()) + .for_each(|l| { + let (mut name, dst) = l.split_once(" -> ").unwrap(); + let dst: Vec = dst.split(", ").map(|s| s.to_string()).collect(); + let len = dst.len(); + let module: ModuleType = match &name[0..1].parse().unwrap() { + 'b' => { + ModuleType::Broadcast( Module { dst } ) + } + '%' => { + name = &name[1..]; + ModuleType::FlipFlop( ModuleFlipFlop { dst, state: false } ) + }, + '&' => { + name = &name[1..]; + conj.push(name.to_string()); + ModuleType::Conjunction( + ModuleConjunction { dst, pulse_type: HashMap::new() } + ) + }, + _ => unreachable!(), + }; + + config.insert(name.to_string(), module); + }); + + // remplissage des Conjunction avec les modules qui lui sont connectés + conj.iter() + .for_each(|c| { + let keys: Vec = config.keys().map(|k| k.to_string()).collect(); + for k in keys.iter() { + if config.get(k).unwrap().dst().contains(&c) { + config.get_mut(&c.clone()).unwrap().add_pulse(k.to_string()); + } + } + }); + + Self { + config, + } + } + + pub fn pulse_cycle(&mut self, name: &str, pulse: PulseType) -> (u64, u64) { + // (from, to, pulse) + let mut queue: VecDeque<(String, String, PulseType)> = VecDeque::new(); + queue.push_back(("bouton".to_string(), name.to_string(), pulse)); + + let (mut n_low, mut n_high) = (0, 0); + + let mut i = 0; + while let Some(q) = queue.pop_front() { + //if i > 10 { break; } + //dbg!(&q); + match q.2 { + PulseType::Low => n_low += 1, + PulseType::High => n_high += 1, + } + + let module = self.config.get_mut(&q.1); + if !module.is_some() { + continue; + } + let module = module.unwrap(); + + //dbg!(&module); + + match module { + ModuleType::Broadcast(m) => { + m.dst.iter().for_each(|n| { queue.push_back((q.1.clone(), n.clone(), q.2)); }); + }, + ModuleType::FlipFlop(m) => { + match q.2 { + PulseType::Low => { + m.state = !m.state; + let new_pulse = if m.state { + PulseType::High + } else { + PulseType::Low + }; + m.dst.iter().for_each(|n| { queue.push_back((q.1.clone(), n.clone(), new_pulse)); }); + }, + PulseType::High => {}, + }; + }, + ModuleType::Conjunction(m) => { + m.update_pulse(q.0, q.2); + let mut new_pulse = PulseType::Low; + if m.pulse_type.values().filter_map(|v| { + match v { + PulseType::Low => Some(1), + PulseType::High => None, + } + }).count() > 0 { + new_pulse = PulseType::High; + } + m.dst.iter().for_each(|n| { queue.push_back((q.1.clone(), n.clone(), new_pulse)); }); + }, + _ => {}, + } + + i += 1; + //println!("i: {}", i); + //dbg!(&queue); + } + //dbg!(&self.config); + //println!("i: {}", i); + println!("n_low: {} n_high: {}", n_low, n_high); + (n_low, n_high) + } + + pub fn is_back_to_start(&self) -> bool { + for k in self.config.keys() { + if !self.config.get(k).unwrap().is_back_to_start() { + return false; + } + } + true + } +} + +fn run_part1(input: &str) -> Result> { + println!("Running day20 - part 1"); + + let mut puzzle = Puzzle::new(input); + + let (mut n_low, mut n_high) = (0, 0); + let n = puzzle.pulse_cycle("broadcaster", PulseType::Low); + n_low += n.0; + n_high += n.1; + + let mut n_cycle = 1; + while !puzzle.is_back_to_start() && n_cycle < 1000 { + println!("cycle: {}", n_cycle); + let n = puzzle.pulse_cycle("broadcaster", PulseType::Low); + n_low += n.0; + n_high += n.1; + n_cycle += 1; + } + + if n_cycle == 1000 { + return Ok(n_low * n_high); + } + println!("cycle: {}", n_cycle); + println!("n_low: {} n_high: {}", n_low, n_high); + + let res = 0; + Ok(res) +} + +fn run_part2(input: &str) -> Result> { + println!("Running day20 - part 2"); + let res = 0; + Ok(res) +} + +#[cfg(test)] +mod tests { + use super::*; + + static TEXT_INPUT: &str = ""; + + #[test] + fn day20_part1_example1() { + let input = " +broadcaster -> a, b, c +%a -> b +%b -> c +%c -> inv +&inv -> a"; + + let res = run_part1(input); + assert_eq!(32000000, res.unwrap()); + } + + #[test] + fn day20_part1_example2() { + let input = " +broadcaster -> a +%a -> inv, con +&inv -> b +%b -> con +&con -> output"; + + let res = run_part1(input); + assert_eq!(11687500, res.unwrap()); + } + + #[test] + fn day20_part2() { + let res = run_part2(TEXT_INPUT); + assert_eq!(0, res.unwrap()); + } +} diff --git a/src/main.rs b/src/main.rs index 36bd08f..e15fe5b 100644 --- a/src/main.rs +++ b/src/main.rs @@ -19,6 +19,7 @@ pub mod day15; pub mod day16; pub mod day18; pub mod day19; +pub mod day20; fn main() { let args: Vec = env::args().collect(); @@ -53,6 +54,7 @@ fn run(day: &str, input_file: &str) -> Result<(), Box> { "day16" => day16::run(input_file)?, "day18" => day18::run(input_file)?, "day19" => day19::run(input_file)?, + "day20" => day20::run(input_file)?, _ => return Err(format!("unknown day \"{day}\"").into()), } Ok(()) -- 2.39.5