From 4cae21c7b20f0e4480fc8f0d113d89e2bd2b8de5 Mon Sep 17 00:00:00 2001 From: Jesse Luehrs Date: Sat, 24 Dec 2022 12:08:13 -0500 Subject: day 24 --- benches/2022.rs | 5 + data/2022/24.txt | 27 +++++ src/bin/2022/day24.rs | 271 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/bin/2022/main.rs | 2 + src/grid.rs | 28 ++++++ 5 files changed, 333 insertions(+) create mode 100644 data/2022/24.txt create mode 100644 src/bin/2022/day24.rs diff --git a/benches/2022.rs b/benches/2022.rs index 6eb6c5e..6b7363d 100644 --- a/benches/2022.rs +++ b/benches/2022.rs @@ -45,6 +45,8 @@ mod day20; mod day21; #[path = "../src/bin/2022/day23.rs"] mod day23; +#[path = "../src/bin/2022/day24.rs"] +mod day24; // NEXT MOD day!(2022, 1, day1); @@ -69,6 +71,7 @@ day!(2022, 19, day19); day!(2022, 20, day20); day!(2022, 21, day21); day!(2022, 23, day23); +day!(2022, 24, day24); // NEXT DAY fn bench_2022(c: &mut criterion::Criterion) { @@ -96,6 +99,7 @@ fn bench_2022(c: &mut criterion::Criterion) { day_combined!(2022, 20, day20); day_combined!(2022, 21, day21); day_combined!(2022, 23, day23); + day_combined!(2022, 24, day24); // NEXT DAY COMBINED }) }); @@ -126,5 +130,6 @@ criterion::criterion_main!( bench_2022day20, bench_2022day21, bench_2022day23, + bench_2022day24, // NEXT GROUP ); diff --git a/data/2022/24.txt b/data/2022/24.txt new file mode 100644 index 0000000..825f663 --- /dev/null +++ b/data/2022/24.txt @@ -0,0 +1,27 @@ +#.######################################################################################################################## +#<..<^>vv^.>>>^.>v.^v<.^<>><^v>v^v><><^<<.<..^^..^>v>><>^>>>vv>v.<^v>v<^v^>.^<^^<<><<<>^vv^>.^># +#<>><>^^<.^<>^^>^^><^><^>v>v>v>>>^><<<>>v<>v>^v>>^v>v<<<.>^<<<<<>>v<<>^v^>.>>v<<># +#>.^>.>v<><^^>..^....v>^^>>^v><<<<<^<^v><.v<.>..<>.>^v^^^.>^^><^v^^v<<....>^>v><<>v>^>^>v^^v><# +#<^>^>v>.<^<.v<<<>^>vv^<vvv<^vv^v^<>vv^<><<>v<>v.vvv.>>v^>><<<>^^v><^^v^^v^^v>>v><<.>^vv.^<# +#>>^><>.>>><><.<>v><<><>vvvv>^><>vv^>^<>^<>^^>><^^>.vvv^<^><^.>vvvv>^.vv<^><^.^vvv<<# +#<>^.v.<^.v<>^^^^^>><^<..v<^v<>>.>>^><^v<^^v^>v^<.<^<.><^^<>^v^><.<>..^>v^.v>.^<><>^.^v><>>>>^.<# +#><^>^<^.^<^.vv>.>v^<.>.<>.v<>>v^><><<<<^vv<<.v^<>><.^<^..^^>.v^<<<>^.v^<>^<.^<<>><# +#<>vvv.v.<^<>^v.v><^^.>^>^<^v.v>>v<^^^<^<^^v.^.><<<>.<<>>^>>^<>.^>v<^.v.vv^v^^^..>.v<.vv<>.>>>>.^><><# +#<>v.^><<<<>>.<<^v>.>v^<>^v>^>>.v.>>^.v^^^><^<<<^^.^v^^>^vv<<>>>.><.^^<<^^<<.<<><^<^^.v><# +#>>><v>^v<^^v^vv><^.v..v.v.>vv><<^...><^v>>^<><>^>>^>^^<>>>.<^^>.v^^^.><>v<>.<# +#><^^^v<><<<^v>^^>^<<>>.<^^vvv<<>^v^<.<>^v^..v>v<.<^^v><^<<<^v.><>vv><^vvv>^v^.^<.>vvvvv<>><># +#>^<>^v^^v<^vvvvv^v.<<>v>>>^<^^<..>^<^<^.>v<>^>^>><>v.vvv.^^v.^^>^<>>^^v<>v<<<^^.>>^>>^>.>>><><>^^^>>^>><<^^^>>v<>>>>^v<^^>.><<^>^^^<.<>v<^><><>>>v>.>.>vv>.v<.<^^>>vv^v>>vv># +#>>.>.vv>^>><^>^.^v>^v<>..<>^^.>..vv<^v>>^.vvv>>^^^vv^^v>^<^.><<v^<<>><^v>>^>^^.v^<^^<>><># +#<^>^>v<^.v^vv^^v>^^v>v^^vv^v^vv>^.><.v<.<><>v^<><<<<>.v^v^<<>^<<>>>>>><.^^^<><<>^v^^# +#.<^^>>v<^^<^>>>>.vvv^>^^><^><.<>v^^vv^v<^>>^<.>^>><^<^><<..v># +#<.>>^.v^.^.v^v<>v>v>v^vv^^<^<<>^^><<><.v<>>^>vv^^>>v<><^^<>^v<vv.vvv>v<.^v^.^><>v>>vvv># +#<>^.v<^v>>>v>v<>^>v^vv<^<.^v.vv^>.v..>>.>vv>>>v^.^^>>^>>><><><>v>>..<^.>^v<^^v^<>>>.^^<^<.v>^>vvv># +#<^.v^<><<..^^vv>>>^vv.>^<>v^v^v^.>^<^<.>>^v><^^v>>^<<<..v<^>v>^vv>^vv^>^v.>>^<<^^>.>>^>^>^^vv.<^v^>>>.>>><^>>v^^^.vv.<<^v^.>v>><^>v.v><^<<>v>v^vv.v<.><><>.^v>.>>>^<>.^>^>v.^v^>v^<><.<<<^<^><^^^<# +#>^<>v>v>.>><>.><..vvvv<>vv<<^^v<>v><^<><<^v>^v<<.<<^^<.v>.<<<>vvv.v>>v^v.>^<>>.<<^v.^^v<^^v.^<.v<<>...<<<<^^^v^.<.>^^<>>^>v^^^^<^v^<><^<<^^.^^<^vv^v<<^^<^<.^># +#<^.^^.<.<<^v^<..><.^v<<>v.<^vv><v>>v><<^.<.>^>v>>>.<><.>^v>>v^v<.^^>.v^v>^><^^v^v>>vv>^.v<>^># +#.>^.v<.>>^<><^>v><.<>>^^vv^.<.>.v>>v.>^><<..v<>v>v>>v><>v^^<^>^<<>^.<<^>v.>v^>vv<>># +#<><.^^^^<>>.<^v.>^<<>v>.>>vv^^<>v^v<^.<.v^v>>>>^><^vvv.>>>v<<<.^^.v.^v.><<.v<>>>^.^v>^vvv.<>v^<^v^<^v<^<><^^^v^<# +########################################################################################################################.# diff --git a/src/bin/2022/day24.rs b/src/bin/2022/day24.rs new file mode 100644 index 0000000..4c977d3 --- /dev/null +++ b/src/bin/2022/day24.rs @@ -0,0 +1,271 @@ +#![allow(dead_code)] +#![allow(unused_variables)] + +use advent_of_code::prelude::*; + +#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)] +enum Direction { + Up, + Down, + Left, + Right, +} + +impl std::fmt::Display for Direction { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + match self { + Self::Up => write!(f, "^"), + Self::Down => write!(f, "v"), + Self::Left => write!(f, "<"), + Self::Right => write!(f, ">"), + } + } +} + +impl Direction { + fn apply(self, pos: (Row, Col), size: (Row, Col)) -> (Row, Col) { + match self { + Self::Up => ((size.0 .0 + pos.0 - 1) % size.0 .0, pos.1), + Self::Down => ((pos.0 + 1) % size.0 .0, pos.1), + Self::Left => (pos.0, (size.1 .0 + pos.1 - 1) % size.1 .0), + Self::Right => (pos.0, (pos.1 + 1) % size.1 .0), + } + } + + fn parse(c: u8) -> Option { + match c { + b'^' => Some(Self::Up), + b'v' => Some(Self::Down), + b'<' => Some(Self::Left), + b'>' => Some(Self::Right), + _ => None, + } + } +} + +#[derive(Debug, Clone)] +pub struct Map { + blizzards: HashSet<((Row, Col), Direction)>, + size: (Row, Col), +} + +impl std::fmt::Display for Map { + fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { + for row in (0..self.size.0 .0).map(Row) { + for col in (0..self.size.1 .0).map(Col) { + let blizzards: Vec<_> = self + .blizzards + .iter() + .filter(|(pos, dir)| *pos == (row, col)) + .collect(); + match blizzards.len() { + 0 => write!(f, ".")?, + 1 => write!(f, "{}", blizzards[0].1)?, + _ => write!(f, "{}", blizzards.len())?, + } + } + writeln!(f)?; + } + Ok(()) + } +} + +impl Map { + fn new( + blizzards: HashSet<((Row, Col), Direction)>, + size: (Row, Col), + ) -> Self { + Self { blizzards, size } + } + + #[must_use] + fn step(&self) -> Self { + Self { + blizzards: self + .blizzards + .iter() + .map(|(pos, direction)| { + (direction.apply(*pos, self.size), *direction) + }) + .collect(), + size: self.size, + } + } + + fn blizzard(&self, pos: (Row, Col)) -> bool { + self.blizzards.contains(&(pos, Direction::Up)) + || self.blizzards.contains(&(pos, Direction::Down)) + || self.blizzards.contains(&(pos, Direction::Left)) + || self.blizzards.contains(&(pos, Direction::Right)) + } +} + +#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)] +enum Pos { + Start, + End, + Pos((Row, Col)), +} + +#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)] +pub struct State { + time: usize, + pos: Pos, +} + +impl State { + fn new(start: bool) -> Self { + Self { + time: 0, + pos: if start { Pos::Start } else { Pos::End }, + } + } +} + +pub fn parse(fh: File) -> Result { + let mut lines = parse::raw_lines(fh); + lines.next().unwrap(); + let mut blizzards = HashSet::new(); + let mut size = (Row(0), Col(0)); + for (row, line) in lines.enumerate() { + let row = Row(row); + if line.starts_with("##") { + size = (row, Col(line.len() - 2)); + break; + } + for (col, c) in line.as_bytes().iter().enumerate() { + let col = Col(col); + if let Some(direction) = Direction::parse(*c) { + blizzards.insert(((row, col - 1), direction)); + } + } + } + Ok(Map::new(blizzards, size)) +} + +struct Pathfinder { + maps_at_time: std::cell::RefCell>, +} + +impl Pathfinder { + fn new(map: Map) -> Self { + Self { + maps_at_time: std::cell::RefCell::new(vec![map]), + } + } + + fn size(&self) -> (Row, Col) { + self.maps_at_time.borrow().get(0).unwrap().size + } + + fn map_at_time(&self, time: usize) -> std::cell::Ref<'_, Map> { + { + let mut maps_at_time = self.maps_at_time.borrow_mut(); + while time >= maps_at_time.len() { + let next = maps_at_time.iter().last().unwrap().step(); + maps_at_time.push(next); + } + } + std::cell::Ref::map(self.maps_at_time.borrow(), |maps| { + maps.get(time).unwrap() + }) + } +} + +impl advent_of_code::graph::Graph for Pathfinder { + type Edges = Vec; + + fn edges(&self, state: State) -> Self::Edges { + let size = self.size(); + let next = self.map_at_time(state.time + 1); + let mut v = vec![]; + match state.pos { + Pos::Start => { + v.push(Pos::Start); + if !next.blizzard((Row(0), Col(0))) { + v.push(Pos::Pos((Row(0), Col(0)))); + } + } + Pos::End => { + v.push(Pos::End); + if !next.blizzard((size.0 - 1, size.1 - 1)) { + v.push(Pos::Pos((size.0 - 1, size.1 - 1))); + } + } + Pos::Pos(pos) => { + if pos.0 < size.0 - 1 && !next.blizzard((pos.0 + 1, pos.1)) { + v.push(Pos::Pos((pos.0 + 1, pos.1))); + } + if pos.1 < size.1 - 1 && !next.blizzard((pos.0, pos.1 + 1)) { + v.push(Pos::Pos((pos.0, pos.1 + 1))); + } + if pos.0 > Row(0) && !next.blizzard((pos.0 - 1, pos.1)) { + v.push(Pos::Pos((pos.0 - 1, pos.1))); + } + if pos.1 > Col(0) && !next.blizzard((pos.0, pos.1 - 1)) { + v.push(Pos::Pos((pos.0, pos.1 - 1))); + } + if !next.blizzard(pos) { + v.push(Pos::Pos(pos)); + } + if pos == (Row(0), Col(0)) { + v.push(Pos::Start); + } + if pos == (size.0 - 1, size.1 - 1) { + v.push(Pos::End); + } + } + } + v + } + + fn edge(&self, state: State, pos: Pos) -> (State, u64) { + ( + State { + pos, + time: state.time + 1, + }, + 1, + ) + } +} + +pub fn part1(map: Map) -> Result { + let state = State::new(true); + let pathfinder = Pathfinder::new(map); + let (dist, _) = pathfinder.dijkstra(state, |state| state.pos == Pos::End); + Ok(dist) +} + +pub fn part2(map: Map) -> Result { + let state = State::new(true); + let pathfinder = Pathfinder::new(map); + let (dist1, _) = + pathfinder.dijkstra(state, |state| state.pos == Pos::End); + + let map = pathfinder.map_at_time(dist1 as usize).clone(); + let state = State::new(false); + let pathfinder = Pathfinder::new(map); + let (dist2, _) = + pathfinder.dijkstra(state, |state| state.pos == Pos::Start); + + let map = pathfinder.map_at_time(dist2 as usize).clone(); + let state = State::new(true); + let pathfinder = Pathfinder::new(map); + let (dist3, _) = + pathfinder.dijkstra(state, |state| state.pos == Pos::End); + + Ok(dist1 + dist2 + dist3) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2022, 24).unwrap()).unwrap()).unwrap(), + 245 + ); + assert_eq!( + part2(parse(parse::data(2022, 24).unwrap()).unwrap()).unwrap(), + 798 + ); +} diff --git a/src/bin/2022/main.rs b/src/bin/2022/main.rs index 14aac9b..10b06fe 100644 --- a/src/bin/2022/main.rs +++ b/src/bin/2022/main.rs @@ -33,6 +33,7 @@ mod day19; mod day20; mod day21; mod day23; +mod day24; // NEXT MOD #[paw::main] @@ -61,6 +62,7 @@ fn main(opt: Opt) -> Result<()> { 20 => advent_of_code::day!(2022, opt.day, opt.puzzle, day20), 21 => advent_of_code::day!(2022, opt.day, opt.puzzle, day21), 23 => advent_of_code::day!(2022, opt.day, opt.puzzle, day23), + 24 => advent_of_code::day!(2022, opt.day, opt.puzzle, day24), // NEXT PART _ => panic!("unknown day {}", opt.day), } diff --git a/src/grid.rs b/src/grid.rs index 347c902..d988ec6 100644 --- a/src/grid.rs +++ b/src/grid.rs @@ -76,6 +76,34 @@ impl std::ops::Sub for usize { } } +impl std::ops::Rem for Row { + type Output = Self; + fn rem(self, other: usize) -> Self::Output { + Self(self.0 % other) + } +} + +impl std::ops::Rem for usize { + type Output = Row; + fn rem(self, other: Row) -> Self::Output { + Row(self % other.0) + } +} + +impl std::ops::Rem for Col { + type Output = Self; + fn rem(self, other: usize) -> Self::Output { + Self(self.0 % other) + } +} + +impl std::ops::Rem for usize { + type Output = Col; + fn rem(self, other: Col) -> Self::Output { + Col(self % other.0) + } +} + #[derive( Copy, Clone, Hash, Eq, PartialEq, Ord, PartialOrd, Debug, Default, )] -- cgit v1.2.3-54-g00ecf