From 6c0c37edfb68cfb334a8963b19e9123ac312e8bc Mon Sep 17 00:00:00 2001 From: Greg Burri Date: Mon, 16 Dec 2024 22:55:22 +0100 Subject: [PATCH] Day 15 --- src/day14.rs | 2 +- src/day15.rs | 216 +++++++++++++++++++++++++++++++++++++++++++++++++++ src/days.rs | 9 +++ src/main.rs | 4 +- 4 files changed, 228 insertions(+), 3 deletions(-) create mode 100644 src/day15.rs diff --git a/src/day14.rs b/src/day14.rs index 5d422ba..9f3296b 100644 --- a/src/day14.rs +++ b/src/day14.rs @@ -7,7 +7,7 @@ type Position = Point2; type Velocity = Vector2; pub fn read(reader: &mut dyn BufRead) -> Vec<(Position, Velocity)> { - let regex_line = { Regex::new(r#"([+-]?\d+),([+-]?\d+).*?([+-]?\d+),([+-]?\d+)"#).unwrap() }; + let regex_line = Regex::new(r#"([+-]?\d+),([+-]?\d+).*?([+-]?\d+),([+-]?\d+)"#).unwrap(); reader .lines() diff --git a/src/day15.rs b/src/day15.rs new file mode 100644 index 0000000..5e133fb --- /dev/null +++ b/src/day15.rs @@ -0,0 +1,216 @@ +use std::io::BufRead; + +use nalgebra::{DMatrix, Point2, Vector2}; + +type Map = DMatrix; +type Pos = Point2; +type Dir = Vector2; +type Movements = Vec; + +pub fn read(reader: &mut dyn BufRead) -> (Pos, Map, Movements) { + let mut robot_pos = Pos::default(); + let mut data: Vec = Vec::new(); + let mut nb_rows = 0; + + let mut lines_iter = reader.lines(); + + for (i, l) in lines_iter.by_ref().enumerate() { + let l = l.unwrap(); + if l.is_empty() { + break; + } + nb_rows += 1; + for (j, c) in l.chars().enumerate() { + if c == '@' { + robot_pos = Pos::new(i as i32, j as i32); + data.push('.'); + } else { + data.push(c); + } + } + } + + let mut movements = Movements::new(); + + for l in lines_iter { + for c in l.unwrap().chars() { + movements.push(match c { + '>' => Dir::new(0, 1), + '<' => Dir::new(0, -1), + 'v' => Dir::new(1, 0), + '^' => Dir::new(-1, 0), + _ => panic!("Uknown movement: {}", c), + }); + } + } + + ( + robot_pos, + Map::from_row_slice(nb_rows, data.len() / nb_rows, &data), + movements, + ) +} + +pub fn gps_coordinates_sum( + mut pos: Pos, + mut map: Map, + movements: &Movements, + enlarge_map: bool, +) -> usize { + fn can_push(map: &Map, pos: Pos, dir: Dir, other_side: bool) -> bool { + let c = map[(pos.x as usize, pos.y as usize)]; + if c == '.' { + return true; + } + if c != '#' { + let pos_next = pos + dir; + if if dir.x == 0 || c == 'O' { + can_push(map, pos_next, dir, false) + } else { + let nearby = if c == '[' { + pos + Dir::new(0, 1) + } else { + pos + Dir::new(0, -1) + }; + can_push(map, pos_next, dir, false) + && (other_side || can_push(map, nearby, dir, true)) + } { + return true; + } + } + false + } + + fn push(map: &mut Map, pos: Pos, dir: Dir, other_side: bool) { + let c = map[(pos.x as usize, pos.y as usize)]; + if c != '#' && c != '.' { + let pos_next = pos + dir; + if dir.x == 0 || c == 'O' { + push(map, pos_next, dir, false) + } else { + let nearby = if c == '[' { + pos + Dir::new(0, 1) + } else { + pos + Dir::new(0, -1) + }; + push(map, pos_next, dir, false); + if !other_side { + push(map, nearby, dir, true); + } + } + map[(pos_next.x as usize, pos_next.y as usize)] = map[(pos.x as usize, pos.y as usize)]; + map[(pos.x as usize, pos.y as usize)] = '.'; + } + } + + fn enlarge(map: Map) -> Map { + let mut new_map = Map::repeat(map.nrows(), 2 * map.ncols(), '.'); + for j in 0..map.ncols() { + for i in 0..map.nrows() { + if map[(i, j)] == 'O' { + new_map[(i, 2 * j)] = '['; + new_map[(i, 2 * j + 1)] = ']'; + } else { + new_map[(i, 2 * j)] = map[(i, j)]; + new_map[(i, 2 * j + 1)] = map[(i, j)]; + } + } + } + new_map + } + + if enlarge_map { + map = enlarge(map); + pos = Pos::new(pos.x, pos.y * 2); + } + + for m in movements { + if can_push(&map, pos + m, *m, false) { + push(&mut map, pos + m, *m, false); + pos += m; + } + } + + let mut gps_sum = 0; + for j in 0..map.ncols() { + for i in 0..map.nrows() { + let c = map[(i, j)]; + if c == '[' || c == 'O' { + gps_sum += 100 * i + j; + } + } + } + gps_sum +} + +#[cfg(test)] +mod tests { + use super::*; + + static MAP_AND_MOVEMENTS_A: &str = "######## +#..O.O.# +##@.O..# +#...O..# +#.#.O..# +#...O..# +#......# +######## + +<^^>>>vv>v<<"; + + static MAP_AND_MOVEMENTS_B: &str = "########## +#..O..O.O# +#......O.# +#.OO..O.O# +#..O@..O.# +#O#..O...# +#O..O..O.# +#.OO.O.OO# +#....O...# +########## + +^v>^vv^v>v<>v^v<<><>>v^v^>^<<<><^ +vvv<<^>^v^^><<>>><>^<<><^vv^^<>vvv<>><^^v>^>vv<>v<<<^<^^>>>^<>vv>v^v^<>><>>>><^^>vv>v<^^^>>v^v^<^^>v^^>v^<^v>v<>>v^v^v^^<^^vv< +<>^^^^>>>v^<>vvv^>^^^vv^^>v<^^^^v<>^>vvvv><>>v^<<^^^^^ +^><^><>>><>^^<<^^v>>><^^>v>>>^v><>^v><<<>vvvv>^<><<>^>< +^>><>^v<><^vvv<^^<><^v<<<><<<^^<^>>^<<<^>>^v^>>^v>vv>^<<^v<>><<><<>v<^vv<<<>^^v^>^^>>><<^v>>v^v><^^>>^<>vv^ +<><^^>^^^<>^vv<<^><<><<><<<^^<<<^<<>><<><^^^>^^<>^>v<> +^^>vv<^v^v^<>^^^>>>^^vvv^>vvv<>>>^<^>>>>>^<<^v>^vvv<>^<>< +v^^>>><<^^<>>^v^v^<<>^<^v^v><^<<<><<^vv>>v>v^<<^"; + + #[test] + fn part1_a() { + let (pos, map, movements) = read(&mut MAP_AND_MOVEMENTS_A.as_bytes()); + assert_eq!(gps_coordinates_sum(pos, map, &movements, false), 2028); + } + + #[test] + fn part1_b() { + let (pos, map, movements) = read(&mut MAP_AND_MOVEMENTS_B.as_bytes()); + assert_eq!(gps_coordinates_sum(pos, map, &movements, false), 10092); + } + + static MAP_AND_MOVEMENTS_C: &str = "####### +#...#.# +#.....# +#..OO@# +#..O..# +#.....# +####### + + String { day14::format_robots(&robots, (101, 103), 7520) ) } + +pub fn day15(reader: &mut dyn BufRead) -> String { + let (pos, map, movements) = day15::read(reader); + format!( + "part1: {}, part2: {}", + day15::gps_coordinates_sum(pos, map.clone(), &movements, false), + day15::gps_coordinates_sum(pos, map, &movements, true), + ) +} diff --git a/src/main.rs b/src/main.rs index e7d4c43..fefa9ec 100644 --- a/src/main.rs +++ b/src/main.rs @@ -16,7 +16,7 @@ mod day11; mod day12; mod day13; mod day14; -// mod day15; +mod day15; // mod day16; // mod day17; // mod day18; @@ -47,7 +47,7 @@ fn main() { days::day12, days::day13, days::day14, - // days::day15, + days::day15, // days::day16, // days::day17, // days::day18, -- 2.45.2