From c4b11ceebec4a74e6c7a76bda6c70c17cd1edcfd Mon Sep 17 00:00:00 2001 From: Greg Burri Date: Sat, 7 Dec 2024 15:33:17 +0100 Subject: [PATCH] Day 06 --- Cargo.toml | 1 + src/day05.rs | 4 +- src/day06.rs | 212 +++++++++++++++++++++++++++++++++++++++++++++++++++ src/days.rs | 10 +++ src/main.rs | 4 +- 5 files changed, 227 insertions(+), 4 deletions(-) create mode 100644 src/day06.rs diff --git a/Cargo.toml b/Cargo.toml index 34640d9..97ed99c 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -11,6 +11,7 @@ itertools = "0.10" regex = "1" clap = { version = "4", features = ["derive"] } rayon = "1.10" +nalgebra = "0.33" [profile.release] opt-level = 3 diff --git a/src/day05.rs b/src/day05.rs index 983ceff..1d7b51c 100644 --- a/src/day05.rs +++ b/src/day05.rs @@ -1,4 +1,4 @@ -use std::{io::BufRead, mem::swap}; +use std::io::BufRead; use itertools::{self, Itertools}; @@ -46,7 +46,7 @@ where page_ordering.add_page_order(pages[0], pages[1]); } - let mut updates: Vec> = vec![]; + let mut updates: Updates = vec![]; while let Some(l) = lines_iter.next() { updates.push(utils::split_to_vec(&l, ",")); } diff --git a/src/day06.rs b/src/day06.rs new file mode 100644 index 0000000..579dcc6 --- /dev/null +++ b/src/day06.rs @@ -0,0 +1,212 @@ +use std::io::BufRead; + +use nalgebra::{DMatrix, Matrix2, Point2, Vector2}; + +type Map = DMatrix; +type Pos = Point2; +type Dir = Vector2; + +pub fn read_map(reader: R) -> (Map, Pos) +where + R: BufRead, +{ + let mut map = DMatrix::default(); + let mut guard_position = Pos::default(); + + for (i, l) in reader.lines().enumerate() { + if map.nrows() < i + 1 { + map = map.insert_row(i, false); + } + for (j, c) in l.unwrap().chars().enumerate() { + if map.ncols() < j + 1 { + map = map.insert_column(j, false); + } + if c == '#' { + map[(i, j)] = true; + } else if c == '^' { + guard_position = Pos::new(i as i32, j as i32); + } + } + } + + (map, guard_position) +} + +const ROT_MAT: Matrix2 = Matrix2::new(0, 1, -1, 0); + +fn inside(map: &Map, p: Pos) -> bool { + p.x >= 0 && p.x < map.nrows() as i32 && p.y >= 0 && p.y < map.ncols() as i32 +} + +struct PathIterator<'a> { + map: &'a Map, + pos: Pos, + dir: Dir, + obstacle: Option, +} + +impl<'a> PathIterator<'a> { + pub fn new(map: &'a Map, pos: Pos, dir: Dir, obstacle: Option) -> Self { + Self { + map, + pos, + dir, + obstacle, + } + } +} + +impl<'a> Iterator for PathIterator<'a> { + type Item = (Pos, Dir); + + fn next(&mut self) -> Option { + let next_pos = self.pos + self.dir; + + // Going outside the map -> end of sequence. + if !inside(self.map, next_pos) { + return None; + } + + if self.map[(next_pos.x as usize, next_pos.y as usize)] + || (self.obstacle.is_some() && self.obstacle.unwrap() == next_pos) + { + self.dir = ROT_MAT * self.dir; + } else { + self.pos = next_pos; + } + + Some((self.pos, self.dir)) + } +} + +pub fn nb_position_visited_by_guard(map: &Map, guard_pos: Pos) -> usize { + let mut nb_visited = 1; + let mut map_visited = Map::repeat(map.nrows(), map.ncols(), false); + + map_visited[(guard_pos.x as usize, guard_pos.y as usize)] = true; + + for (pos, _) in PathIterator::new(map, guard_pos, Dir::new(-1, 0), None) { + if !map_visited[(pos.x as usize, pos.y as usize)] { + map_visited[(pos.x as usize, pos.y as usize)] = true; + nb_visited += 1; + } + } + + nb_visited +} + +pub fn nb_possible_obstruction_position(map: &Map, initial_pos: Pos) -> usize { + let initial_dir = Dir::new(-1, 0); + let mut map_visited = DMatrix::>::repeat(map.nrows(), map.ncols(), None); + + let mut nb_loops = 0; + for (pos, dir) in vec![(initial_pos, initial_dir)] + .into_iter() + .chain(PathIterator::new(map, initial_pos, initial_dir, None)) + { + if map_visited[(pos.x as usize, pos.y as usize)].is_none() { + map_visited[(pos.x as usize, pos.y as usize)] = Some(dir); + } + let obstacle_pos = pos + dir; + if inside(map, obstacle_pos) + && !map[(obstacle_pos.x as usize, obstacle_pos.y as usize)] + && map_visited[(obstacle_pos.x as usize, obstacle_pos.y as usize)].is_none() + { + if does_it_loop( + PathIterator::new(map, pos, dir, Some(obstacle_pos)), + &map_visited, + ) { + nb_loops += 1; + } + } + } + nb_loops +} + +fn does_it_loop(path: PathIterator, map_visited: &DMatrix>) -> bool { + let mut map_visited = map_visited.clone(); + for (pos, dir) in path { + let visited = map_visited[(pos.x as usize, pos.y as usize)]; + if visited.is_none() { + map_visited[(pos.x as usize, pos.y as usize)] = Some(dir); + } else if visited.unwrap() == dir { + return true; + } + } + return false; +} + +#[cfg(test)] +mod tests { + use super::*; + + static MAP: &str = "....#..... +.........# +.......... +..#....... +.......#.. +.......... +.#..^..... +........#. +#......... +......#..."; + + #[test] + fn test_part1() { + let (map, guard_pos) = read_map(MAP.as_bytes()); + let n = nb_position_visited_by_guard(&map, guard_pos); + println!("n: {}", n); + assert_eq!(n, 41); + } + + #[test] + fn test_part2() { + let (map, guard_pos) = read_map(MAP.as_bytes()); + let n = nb_possible_obstruction_position(&map, guard_pos); + println!("n: {}", n); + assert_eq!(n, 6); + } + + static MAP2: &str = ".#.. +.^.# +.... +..#."; + + static MAP3: &str = ".... +.^.# +#... +..#."; + + static MAP4: &str = ".#.. +...# +#... +.^.."; + + static MAP5: &str = ".#.. +...# +#... +.^.."; + + static MAP6: &str = "... +#.# +#^# +.#."; + + #[test] + fn test_part2_tiny_maps() { + let (map, guard_pos) = read_map(MAP2.as_bytes()); + assert_eq!(nb_possible_obstruction_position(&map, guard_pos), 1); + + let (map, guard_pos) = read_map(MAP3.as_bytes()); + assert_eq!(nb_possible_obstruction_position(&map, guard_pos), 1); + + let (map, guard_pos) = read_map(MAP4.as_bytes()); + assert_eq!(nb_possible_obstruction_position(&map, guard_pos), 1); + + let (map, guard_pos) = read_map(MAP5.as_bytes()); + assert_eq!(nb_possible_obstruction_position(&map, guard_pos), 1); + + let (map, guard_pos) = read_map(MAP6.as_bytes()); + assert_eq!(nb_possible_obstruction_position(&map, guard_pos), 2); + } +} diff --git a/src/days.rs b/src/days.rs index 2bc4038..b977381 100644 --- a/src/days.rs +++ b/src/days.rs @@ -51,3 +51,13 @@ pub fn day05() -> String { day05::sum_of_mid_page_from_corrected_updates(&ordering, &updates) ) } + +pub fn day06() -> String { + let f = fs::File::open("data/day06.input").unwrap(); + let (map, guard_pos) = day06::read_map(BufReader::new(f)); + format!( + "part1: {}, part2: {}", + day06::nb_position_visited_by_guard(&map, guard_pos), + day06::nb_possible_obstruction_position(&map, guard_pos), + ) +} diff --git a/src/main.rs b/src/main.rs index c15ed2e..85f283c 100644 --- a/src/main.rs +++ b/src/main.rs @@ -8,7 +8,7 @@ mod day02; mod day03; mod day04; mod day05; -// mod day06; +mod day06; // mod day07; // mod day08; // mod day09; @@ -49,7 +49,7 @@ fn main() { days::day03, days::day04, days::day05, - // days::day06, + days::day06, // days::day07, // days::day08, // days::day09, -- 2.45.2