From b7a724c865e2927e095253bb893687f0277821cd Mon Sep 17 00:00:00 2001 From: Jack Kinsey Date: Mon, 16 Dec 2024 22:18:16 -0500 Subject: [PATCH] Complete day 15 part 1 --- src/day15.rs | 386 +++++++++++++++++++++++++++++++++++++++++++++++++++ src/main.rs | 4 +- 2 files changed, 388 insertions(+), 2 deletions(-) create mode 100644 src/day15.rs diff --git a/src/day15.rs b/src/day15.rs new file mode 100644 index 0000000..8308212 --- /dev/null +++ b/src/day15.rs @@ -0,0 +1,386 @@ +use std::ops::{Add, Index, IndexMut, Sub}; + +#[derive(Debug, Hash, Eq, PartialEq, Copy, Clone)] +struct Point(i32, i32); + +impl Point { + fn in_bounds(&self, bound: usize) -> bool { + let bound: i32 = bound.try_into().unwrap(); + self.0 >= 0 && self.1 >= 0 && self.0 < bound && self.1 < bound + } + + fn move_in(&self, dir: Dir) -> Point { + match dir { + Dir::N => *self + Point(-1, 0), + Dir::E => *self + Point(0, 1), + Dir::S => *self + Point(1, 0), + Dir::W => *self + Point(0, -1), + } + } + + fn gps(&self) -> u64 { + (100 * self.0 + self.1).try_into().unwrap() + } +} + +impl Add for Point { + type Output = Point; + + fn add(self, rhs: Self) -> Self::Output { + Point(self.0 + rhs.0, self.1 + rhs.1) + } +} + +impl Sub for Point { + type Output = Point; + + fn sub(self, rhs: Self) -> Self::Output { + Point(self.0 - rhs.0, self.1 - rhs.1) + } +} + +#[derive(Debug, Hash, Eq, PartialEq, Copy, Clone)] +enum Tile { + Space, + Wall, + Box, + Robot, + BoxL, + BoxR, +} + +#[derive(Debug, Eq, PartialEq, Copy, Clone)] +enum Dir { + N, + E, + S, + W, +} + +#[derive(Debug, Eq, PartialEq, Clone)] +struct Map(Vec>); + +impl Index for Map { + type Output = T; + + fn index(&self, index: Point) -> &Self::Output { + let i: usize = index.0.try_into().unwrap(); + let j: usize = index.1.try_into().unwrap(); + &self.0[i][j] + } +} + +impl IndexMut for Map { + fn index_mut(&mut self, index: Point) -> &mut Self::Output { + let i: usize = index.0.try_into().unwrap(); + let j: usize = index.1.try_into().unwrap(); + &mut self.0[i][j] + } +} + +impl Map { + fn points(&self) -> impl Iterator + use<'_, T> { + self.0 + .iter() + .zip(0..) + .flat_map(move |(v, i)| v.iter().zip(0..).map(move |(_, j)| Point(i, j))) + } + + fn find(&self, val: T) -> impl Iterator + use<'_, T> { + self.points().filter(move |&p| self[p] == val) + } +} + +impl Map { + fn biggerify(&self) -> Map { + let (h, w) = (self.0.len(), self.0[0].len() * 2); + let mut big = Map(std::iter::repeat_with(|| vec![Tile::Space; w]) + .take(h) + .collect()); + for p in self.points() { + let Point(i, j) = p; + let b = Point(i, j * 2); + let b2 = b + Point(0, 1); + (big[b], big[b2]) = match self[p] { + Tile::Space => (Tile::Space, Tile::Space), + Tile::Wall => (Tile::Wall, Tile::Wall), + Tile::Box => (Tile::BoxL, Tile::BoxR), + Tile::Robot => (Tile::Robot, Tile::Space), + Tile::BoxL => unreachable!(), + Tile::BoxR => unreachable!(), + } + } + big + } +} + +fn parse(input: &str) -> (Map, Vec) { + let [map, inst] = input.split("\n\n").collect::>()[..] else { + panic!() + }; + ( + Map(map + .lines() + .map(|l| { + l.chars() + .map(|c| match c { + '.' => Tile::Space, + '#' => Tile::Wall, + 'O' => Tile::Box, + '@' => Tile::Robot, + _ => unreachable!(), + }) + .collect() + }) + .collect()), + inst.lines() + .flat_map(|l| l.chars()) + .map(|c| match c { + '^' => Dir::N, + '>' => Dir::E, + 'v' => Dir::S, + '<' => Dir::W, + _ => unreachable!(), + }) + .collect(), + ) +} + +struct RobotPrediction { + map: Map, + robot: Point, +} + +impl RobotPrediction { + fn new(map: Map) -> Self { + let robot = map.find(Tile::Robot).next().unwrap(); + RobotPrediction { map, robot } + } + + fn apply(&mut self, inst: Dir) { + let np = self.robot.move_in(inst); + match self.map[np] { + Tile::Space => { + self.map[self.robot] = Tile::Space; + self.map[np] = Tile::Robot; + self.robot = np; + } + Tile::Wall => (), + Tile::Box => { + let mut mp = np.move_in(inst); + loop { + mp = match self.map[mp] { + Tile::Space => { + self.map[self.robot] = Tile::Space; + self.map[np] = Tile::Robot; + self.map[mp] = Tile::Box; + self.robot = np; + break; + } + Tile::Wall => break, + Tile::Box => mp.move_in(inst), + Tile::Robot => unreachable!(), + Tile::BoxL => todo!(), + Tile::BoxR => todo!(), + } + } + } + Tile::Robot => unreachable!(), + Tile::BoxL => todo!(), + Tile::BoxR => todo!(), + } + } + // println!("{:?} -> {:?}\n{:#?}", self.robot, np, self.map); + + fn simulate(&mut self, inst: &[Dir]) -> Vec { + let mut path = vec![]; + for d in inst { + self.apply(*d); + path.push(self.robot); + } + path + } +} + +pub fn part1(input: &str) -> u64 { + let (map, inst) = parse(input); + let mut pred = RobotPrediction::new(map); + pred.simulate(&inst); + pred.map.find(Tile::Box).map(|p| p.gps()).sum() +} + +pub fn part2(input: &str) -> u64 { + 0 +} + +#[cfg(test)] +mod test { + use super::*; + + const INPUT_STR: &str = concat!( + "##########\n", + "#..O..O.O#\n", + "#......O.#\n", + "#.OO..O.O#\n", + "#..O@..O.#\n", + "#O#..O...#\n", + "#O..O..O.#\n", + "#.OO.O.OO#\n", + "#....O...#\n", + "##########\n", + "\n", + "^v>^vv^v>v<>v^v<<><>>v^v^>^<<<><^\n", + "vvv<<^>^v^^><<>>><>^<<><^vv^^<>vvv<>><^^v>^>vv<>v<<<^<^^>>>^<>vv>v^v^<>><>>>><^^>vv>v<^^^>>v^v^<^^>v^^>v^<^v>v<>>v^v^v^^<^^vv<\n", + "<>^^^^>>>v^<>vvv^>^^^vv^^>v<^^^^v<>^>vvvv><>>v^<<^^^^^\n", + "^><^><>>><>^^<<^^v>>><^^>v>>>^v><>^v><<<>vvvv>^<><<>^><\n", + "^>><>^v<><^vvv<^^<><^v<<<><<<^^<^>>^<<<^>>^v^>>^v>vv>^<<^v<>><<><<>v<^vv<<<>^^v^>^^>>><<^v>>v^v><^^>>^<>vv^\n", + "<><^^>^^^<>^vv<<^><<><<><<<^^<<<^<<>><<><^^^>^^<>^>v<>\n", + "^^>vv<^v^v^<>^^^>>>^^vvv^>vvv<>>>^<^>>>>>^<<^v>^vvv<>^<><\n", + "v^^>>><<^^<>>^v^v^<<>^<^v^v><^<<<><<^vv>>v>v^<<^\n", + ); + + #[test] + fn test_parse() { + use Dir::*; + use Tile::*; + assert_eq!( + parse(INPUT_STR), + ( + Map(vec![ + vec![Wall, Wall, Wall, Wall, Wall, Wall, Wall, Wall, Wall, Wall], + vec![Wall, Space, Space, Box, Space, Space, Box, Space, Box, Wall], + vec![Wall, Space, Space, Space, Space, Space, Space, Box, Space, Wall], + vec![Wall, Space, Box, Box, Space, Space, Box, Space, Box, Wall], + vec![Wall, Space, Space, Box, Robot, Space, Space, Box, Space, Wall], + vec![Wall, Box, Wall, Space, Space, Box, Space, Space, Space, Wall], + vec![Wall, Box, Space, Space, Box, Space, Space, Box, Space, Wall], + vec![Wall, Space, Box, Box, Space, Box, Space, Box, Box, Wall], + vec![Wall, Space, Space, Space, Space, Box, Space, Space, Space, Wall], + vec![Wall, Wall, Wall, Wall, Wall, Wall, Wall, Wall, Wall, Wall] + ]), + vec![ + W, S, S, E, N, W, S, N, E, S, E, N, S, S, N, S, E, S, W, E, S, N, S, W, S, W, + N, S, S, W, W, W, N, E, W, W, E, W, E, E, S, W, S, S, S, W, E, N, S, N, E, N, + W, W, W, E, W, W, S, W, W, W, S, N, S, S, N, S, E, N, S, S, S, W, W, N, E, N, + S, N, N, E, W, W, E, E, E, W, E, N, W, W, E, W, N, S, S, N, N, W, E, S, S, S, + W, E, E, W, N, N, S, E, N, E, S, S, W, E, S, W, W, W, W, S, W, N, S, E, N, W, + N, N, E, E, E, N, W, S, W, S, E, W, E, S, S, E, S, N, S, N, W, E, E, W, E, E, + E, E, W, N, N, E, S, S, E, S, W, N, N, N, E, E, S, N, S, N, W, N, N, E, S, N, + N, E, S, N, W, N, S, E, S, W, E, E, S, N, S, N, W, S, E, S, N, N, W, N, N, S, + S, W, W, W, S, W, N, E, E, N, N, N, N, E, E, E, S, N, W, E, S, S, S, N, E, W, + S, W, W, W, E, N, N, N, S, S, N, W, S, S, S, E, N, E, S, W, N, N, N, N, S, W, + E, N, E, S, S, S, S, E, W, E, E, S, N, W, W, N, N, N, N, N, N, E, W, N, E, W, + E, E, E, W, E, N, N, W, W, N, N, S, E, E, E, W, N, W, S, E, N, W, S, S, E, E, + S, E, E, E, N, S, E, W, E, N, S, E, W, W, W, W, S, E, E, S, W, S, W, S, E, S, + S, S, E, N, W, E, W, W, E, N, E, W, N, E, E, W, E, N, S, W, E, W, N, S, S, S, + W, N, N, W, E, W, S, W, W, W, W, W, E, W, N, S, W, W, W, E, W, W, W, N, N, W, + S, W, N, N, N, E, W, N, E, E, N, W, S, N, E, W, W, W, N, E, E, N, S, W, S, N, + S, W, S, N, E, N, E, E, N, S, E, S, S, E, N, W, W, N, S, W, E, E, W, W, E, W, + W, S, W, W, S, E, W, E, S, W, N, S, S, W, W, W, E, N, N, S, N, E, N, N, E, E, + E, W, W, N, S, E, E, S, N, S, E, W, N, N, E, E, N, W, E, S, S, N, W, E, W, N, + N, E, N, N, N, W, E, W, S, S, S, S, S, N, S, W, S, W, W, E, N, S, W, S, E, S, + W, W, N, E, W, W, E, W, W, E, W, W, W, N, N, W, W, W, N, W, W, E, E, W, W, E, + W, N, N, N, E, N, N, W, E, N, E, S, W, E, N, N, E, S, S, W, N, S, N, S, W, S, + S, E, N, W, E, W, S, W, N, S, E, N, N, N, E, E, E, N, N, S, S, S, N, E, S, S, + S, W, E, E, E, N, W, N, E, E, E, E, E, N, W, W, N, S, E, N, S, S, S, W, E, N, + W, E, W, W, S, E, S, N, N, E, E, E, W, W, N, N, W, E, E, N, S, N, W, S, N, S, + S, W, E, S, N, W, W, E, N, W, N, S, N, S, E, W, N, W, W, W, E, W, W, N, W, S, + E, W, S, W, E, S, S, E, E, S, E, W, S, N, W, S, S, W, E, S, N, W, W, N + ] + ) + ) + } + + #[test] + fn test_simulate() { + use Dir::*; + let (map, _) = parse(INPUT_STR); + let inst = [W, S, S, E, N, W, W, N, N, N]; + let mut pred = RobotPrediction::new(map); + assert_eq!( + pred.simulate(&inst[0..10]), + [ + Point(4, 3), + Point(5, 3), + Point(6, 3), + Point(6, 4), + Point(5, 4), + Point(5, 3), + Point(5, 3), + Point(4, 3), + Point(3, 3), + Point(3, 3), + ] + ); + } + + #[test] + fn test_gps_sum() { + assert_eq!(part1(INPUT_STR), 10092) + } + + #[rustfmt::skip] + #[test] + fn test_biggerify() { + use Tile::*; + let (map, _) = parse(INPUT_STR); + assert_eq!( + map.biggerify(), + Map(vec![ + vec![ + Wall, Wall, Wall, Wall, Wall, Wall, Wall, Wall, Wall, Wall, Wall, Wall, Wall, + Wall, Wall, Wall, Wall, Wall, Wall, Wall + ], + vec![ + Wall, Wall, Space, Space, Space, Space, BoxL, BoxR, Space, Space, Space, Space, + BoxL, BoxR, Space, Space, BoxL, BoxR, Wall, Wall + ], + vec![ + Wall, Wall, Space, Space, Space, Space, Space, Space, Space, Space, Space, + Space, Space, Space, BoxL, BoxR, Space, Space, Wall, Wall + ], + vec![ + Wall, Wall, Space, Space, BoxL, BoxR, BoxL, BoxR, Space, Space, Space, Space, + BoxL, BoxR, Space, Space, BoxL, BoxR, Wall, Wall + ], + vec![ + Wall, Wall, Space, Space, Space, Space, BoxL, BoxR, Robot, Space, Space, Space, + Space, Space, BoxL, BoxR, Space, Space, Wall, Wall + ], + vec![ + Wall, Wall, BoxL, BoxR, Wall, Wall, Space, Space, Space, Space, BoxL, BoxR, + Space, Space, Space, Space, Space, Space, Wall, Wall + ], + vec![ + Wall, Wall, BoxL, BoxR, Space, Space, Space, Space, BoxL, BoxR, Space, Space, + Space, Space, BoxL, BoxR, Space, Space, Wall, Wall + ], + vec![ + Wall, Wall, Space, Space, BoxL, BoxR, BoxL, BoxR, Space, Space, BoxL, BoxR, + Space, Space, BoxL, BoxR, BoxL, BoxR, Wall, Wall + ], + vec![ + Wall, Wall, Space, Space, Space, Space, Space, Space, Space, Space, BoxL, BoxR, + Space, Space, Space, Space, Space, Space, Wall, Wall + ], + vec![ + Wall, Wall, Wall, Wall, Wall, Wall, Wall, Wall, Wall, Wall, Wall, Wall, Wall, + Wall, Wall, Wall, Wall, Wall, Wall, Wall + ] + ]), + ) + } + + #[test] + fn test_part1() { + assert_eq!(part1(&crate::input(15).unwrap()), 1516281) + } + + #[test] + #[ignore] + fn test_part2() { + assert_eq!(part2(&crate::input(0).unwrap()), 0) + } +} diff --git a/src/main.rs b/src/main.rs index 11b2835..119095a 100644 --- a/src/main.rs +++ b/src/main.rs @@ -11,8 +11,8 @@ pub mod day10; pub mod day11; pub mod day12; pub mod day13; -// pub mod day15; pub mod day14; +pub mod day15; // pub mod day16; // pub mod day17; // pub mod day18; @@ -40,8 +40,8 @@ const DAYS: &[(Part, Part)] = &[ (day11::part1, day11::part2), (day12::part1, day12::part2), (day13::part1, day13::part2), - // (day15::part1, day15::part2), (day14::part1, day14::part2), + (day15::part1, day15::part2), // (day16::part1, day16::part2), // (day17::part1, day17::part2), // (day18::part1, day18::part2), -- 2.38.5