From 285378ed607932cb126b03cdc77a8682e37821e8 Mon Sep 17 00:00:00 2001 From: Federico Igne Date: Mon, 13 Dec 2021 14:34:33 +0000 Subject: Day 11 --- day11/Cargo.toml | 9 +++++ day11/resources/input.txt | 10 +++++ day11/src/main.rs | 94 +++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 113 insertions(+) create mode 100644 day11/Cargo.toml create mode 100644 day11/resources/input.txt create mode 100644 day11/src/main.rs diff --git a/day11/Cargo.toml b/day11/Cargo.toml new file mode 100644 index 0000000..350430f --- /dev/null +++ b/day11/Cargo.toml @@ -0,0 +1,9 @@ +[package] +name = "day11" +version = "0.1.0" +authors = ["Federico Igne "] +edition = "2018" + +# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html + +[dependencies] diff --git a/day11/resources/input.txt b/day11/resources/input.txt new file mode 100644 index 0000000..16ac3e9 --- /dev/null +++ b/day11/resources/input.txt @@ -0,0 +1,10 @@ +7222221271 +6463754232 +3373484684 +4674461265 +1187834788 +1175316351 +8211411846 +4657828333 +5286325337 +5771324832 diff --git a/day11/src/main.rs b/day11/src/main.rs new file mode 100644 index 0000000..960accf --- /dev/null +++ b/day11/src/main.rs @@ -0,0 +1,94 @@ +use std::fs; +use std::path::Path; +use std::collections::VecDeque; + +const WIDTH: usize = 10; +const HEIGHT: usize = 10; + +/* AOC21 Day 11: https://adventofcode.com/2021/day/11 */ +fn main() { + let input = Path::new("resources").join("input.txt"); + let content = fs::read_to_string(input).expect("Unable to read input file"); + ex1(&content, 100); + ex2(&content); +} + +fn ex1(content: &str, steps: u32) { + let mut energy: Vec = content.lines().flat_map(|l| l.bytes().map(|b| b-b'0')).collect(); + let mut queue: VecDeque = VecDeque::with_capacity(2*WIDTH*HEIGHT); + println!("Ex1: the result is {}", (0..steps).map(|_| step(&mut energy, &mut queue)).sum::()) +} + +fn ex2(content: &str) { + let mut energy: Vec = content.lines().flat_map(|l| l.bytes().map(|b| b-b'0')).collect(); + let mut queue: VecDeque = VecDeque::with_capacity(2*WIDTH*HEIGHT); + println!("Ex2: the result is {}", (1..).find(|_| step(&mut energy, &mut queue) == WIDTH*HEIGHT).unwrap()); +} + +fn step(energy: &mut [u8], queue: &mut VecDeque) -> usize { + queue.extend(0..energy.len()); + while let Some(i) = queue.pop_front() { + octopus(energy, queue, i); + } + energy.iter_mut().filter_map(|o| if *o > 9 { *o = 0; Some(o) } else { None }).count() +} + +fn octopus(energy: &mut [u8], queue: &mut VecDeque, i: usize) { + let len = energy.len(); + energy[i] += 1; + if energy[i] == 10 { + if i%WIDTH > 0 { + queue.push_back(i-1); + if i >= WIDTH+1 { queue.push_back(i-WIDTH-1) } + if i+WIDTH-1 < len { queue.push_back(i+WIDTH-1) } + } + if (i+1)%WIDTH > 0 { + queue.push_back(i+1); + if i >= WIDTH-1 { queue.push_back(i+1-WIDTH) } + if i+WIDTH+1 < len { queue.push_back(i+1+WIDTH) } + } + if i >= WIDTH { queue.push_back(i-WIDTH) } + if i+WIDTH < len { queue.push_back(i+WIDTH) } + } +} + +#[cfg(test)] +mod tests { + use super::*; + + const INPUT: [u8;100] = [ + 5,4,8,3,1,4,3,2,2,3, + 2,7,4,5,8,5,4,7,1,1, + 5,2,6,4,5,5,6,1,7,3, + 6,1,4,1,3,3,6,1,4,6, + 6,3,5,7,3,8,5,4,7,8, + 4,1,6,7,5,2,4,6,4,5, + 2,1,7,6,8,4,1,7,2,1, + 6,8,8,2,8,8,1,1,3,4, + 4,8,4,6,8,4,8,5,5,4, + 5,2,8,3,7,5,1,5,2,6 + ]; + + #[test] + fn step10() { + let mut input = INPUT.clone(); + let mut queue = VecDeque::with_capacity(200); + let flash = (0..10).map(|_| step(&mut input, &mut queue)).sum::(); + assert_eq!(204, flash); + } + + #[test] + fn step100() { + let mut input = INPUT.clone(); + let mut queue = VecDeque::with_capacity(200); + let flash = (0..100).map(|_| step(&mut input, &mut queue)).sum::(); + assert_eq!(1656, flash); + } + + #[test] + fn synchronised() { + let mut input = INPUT.clone(); + let mut queue: VecDeque = VecDeque::with_capacity(2*WIDTH*HEIGHT); + assert_eq!(195, (1..).find(|_| step(&mut input, &mut queue) == WIDTH*HEIGHT).unwrap()); + } +} -- cgit v1.2.3