day 24

5 files changed, 333 insertions, 0 deletions

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><vv.>v^v><><^<<.<..^^.<v>.^>v>><>^>><vv^^<><v>>vv><v>v.<^v>v<^v^>.^<^^<<><<<v<<><>^vv^>.^>#
+#<>><>^^<.<v^v^.<<>^<v^^<><><v.^>^^>^^><^><^>v>v>v>>>^><<<>>v<>v>^v>>^v>v<<<.>^<<<<<>>v<<>^v^>.<v>>>v<<<vv<<v.^v^^^^^..>>#
+#>.^>.><vv>v<><^^>..^....v>^^>>^v><<v.^><<<<^<^v><.v<.>..<>.>^v^^^.>^<v>^><^<v<><vv<vv^>v^^v<<....>^>v><<>v>^<v>>^>v^^v><#
+#<^<v^v<<>>^>v>.<^<.v<<<>^>vv^<<v^>vvv<v><^vv^v^<>vv<vv..^>^<><<<vv^.>>v<>v.vvv.>>v^><v>><<<>^^v><^^v^^v^^v>>v><<.>^vv.^<#
+#>>^<v>><>.>>><><.<>v><<><>vvvv>^><>vv^>^<>^<>^^>><^^>.vvv<v>^<<vv^<^v<.^.v.<vvv<<v.>^><v^^v><^.>vvvv>^.vv<^><^.^<v>vvv<<#
+#<v^<v^><>^<v^<<^^>.v.<^.v<>^^^^^>><^<..v<^v<>>.>>^><^v<^^v^>v^<v^v><.<^<.><^^<vv^><>^v^><.<>..^>v^.v>.^<><>^.^v><>>>>^.<#
+#><^><v.>^<^.^<^.v<v^<>v>.>v^<.>.<>.v<>>v^><><<<v^.<><<^<v<<.>vv<<.v^<>><.^<^..^^><v>.v^<<<>^.<v^..<v<<<>v^<>^<v><.^<<>><#
+#<>vvv.v.<^<>^v.v<vv>><^^.>^>^<^v.v>>v<^^^<^<^^v.^.><<<>.<<>>^>>^<>.^>v<^.v.vv^v^^^..><v^v<^>.<v.^<>v<v><.vv<>.>>>>.^><><#
+#<>v<v^<v<v>.^><vv><<<<>>.<<^v>.>v^<>^v>^>>.v.>>^.v^<v^vv^^.^v>^^><^<<<^^.^v<v..v<vv>^^>^vv<<>>>.><.^^<<^^<<.<<><^<^^.v><#
+#>>><<v^^v<^<^.<<.>v><v^^><v^<>^v<^^v^vv><^.v..v.v.>vv><<^...><^v>><v^v<<v^^<v>^<><<vv>>^>>^><v>^^<>>>.<^^>.v^^^.><>v<>.<#
+#><^^^v<><<<^v>^^><vv<vv>^<<>>.<^^vvv<<>^v^<.<><v<<>^v^..v>v<.<^^v><^<<v^v<><<^<v>v.><>v<v.>v><^vvv>^v^<v>.^<.>vvvvv<>><>#
+#>^<>^v^^v<^vvvvv^<v>v.<<>v>>>^<^^<..>^<^<^.>v<vvvv^^><>^>^>><>v.vvv.^^v.^^>^<>>^^v<>v<<<^^.>>^>>^><v^^.<<v<>.>>><><><v.<#
+#>^^^>>^>><<^<v>^^>>v<>>>>^v<v<.vvv<<><^^>.><vv<^.><<^>^<vv..^><v<..<>^^<.<>v<^><><>>>v>.>.>vv>.v<.<^^<v^>>>vv^<v^>v>>vv>#
+#>>.<v>>.vv>^>><vvv<><^>^.^v>^v<>..<>^^.><v>..vv<^v>>^.vvv>>^^<vvvvvvv>^vv^^v>^<^.<v<>><<<vv^<>v^<<>><^v>>^>^^.v^<^^<>><>#
+#<^>^>v<^<v^<^.<v^^<v.>.v^vv^^v>^^v>v^^vv^v^vv>^.><.v<.<><>v<v<>^<v...<><><<<<>.v^v^<<>^<<>>>>>><.^^^<><<><v^>^v^^<v<^v<>#
+#.<^^>>v<v<><^^<vv<<v><^>>>>.vvv^>^^<v<<>><<v^>^><.<><vv.v<vv^<><v>v^^<v^<.>v<vv>v^v<^>>^<vv^><.<v>>^<v>>><^<^<v^>><<..v>#
+#<.>>^.v^.^.v^v<>v>v>v^vv^^<^<<>^^><<><.v<>><v<<<vv^<<..v<v.<>^>vv^^>>v<><v^^><^^<>^v<<vv<v>vv.vvv>v<.^v^.^><><v.>v>>vvv>#
+#<>^.v<^v>>>v>v<>^>v^<vv<<^v<<^^>vv<^<.^v.<v<vvv>vv^>.v..>>.>vv>>>v^.^^>>^>>><><><>v>>..<^.>^v<^^v^<>>><v>.^^<^<.v>^>vvv>#
+#<^.v^<><<..^^v<v^>v>>>^vv.><v>^<>v^v^v^.>^<v><^<.>>^v><^^v>>^<<<..v<^>v>^vv>^vv^>^v.>>^<<^^>.><v<vv><v^.^<>>^>^>^^v<vvv<#
+#>v.<^v^>>>.>>><^>>v^^^.vv.<<^v^.>v>><^>v.v><^<vvvv><<>v>v^<v^^v.<>vv.v<.><><>.^v>.>>>^<>.^>^>v.<v>^v^>v^<><.<<<^<^><^^^<#
+#>^<>v>v>.>><>.><..vvvv<>vv<<^^v<>v<v^^vv.^<<v<v<<<<v<>><^<><<^v>^v<<<v<^v^<..vv<<<<<^.^v^>.<v^><<^^<.v>.<<<v<><>vvv.v<v<#
+#<^^<<^<<.^>><v<v.^<^^<>>v^v.>^<>>.<<^v.^^v<^^v.^<.v<<>...<<<<^^^v^.<.>^^<>>^>v^^<v<vv^>^^<^v^<><^<<^^.^^<^vv^v<<^^<^<.^>#
+#<^.^^.<.<<^v^<..><.^v<<>v.<^vv><<v<vv<vvv^<^^>v<v>>>v><<^.<.>^>v>>>.<><v<.vv<^^><.>^v>>v^v<.^^>.v^v>^><^^v^v>>vv>^.v<>^>#
+#.>^.v<.>>^<><^>v><.<>>^^vv^.<.>.v>>v.>^><<..v<>v>v>>v><>v^^<^>^<<>^.<<<v^>^>v<v.>.>v^<vv^vv<^^<<<<.v^.<v.^v>>v<v^^.>v<>>#
+#<><.^^^^<>>.<^v.>^<<>v>.<v>>>vv^^<>v^v<^.<.v^v>>>>^><^vvv.>>>v<<<.^^.v<vv^>.^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<Self> {
+        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<Map> {
+    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<Vec<Map>>,
+}
+
+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<State, Pos> for Pathfinder {
+    type Edges = Vec<Pos>;
+
+    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<u64> {
+    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<u64> {
+    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<Col> for usize {
     }
 }
 
+impl std::ops::Rem<usize> for Row {
+    type Output = Self;
+    fn rem(self, other: usize) -> Self::Output {
+        Self(self.0 % other)
+    }
+}
+
+impl std::ops::Rem<Row> for usize {
+    type Output = Row;
+    fn rem(self, other: Row) -> Self::Output {
+        Row(self % other.0)
+    }
+}
+
+impl std::ops::Rem<usize> for Col {
+    type Output = Self;
+    fn rem(self, other: usize) -> Self::Output {
+        Self(self.0 % other)
+    }
+}
+
+impl std::ops::Rem<Col> 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,
 )]