Day 24

2 files changed, 217 insertions, 0 deletions

diff --git a/2022/inputs/day_24.txt b/2022/inputs/day_24.txt
new file mode 100644
index 0000000..e867e27
--- /dev/null
+++ b/2022/inputs/day_24.txt
@@ -0,0 +1,22 @@
+#.######################################################################################################################################################
+#.v><><<>^^^<><<>.^v<>v^>v^v^^<..^v>^>^vv.>v^<<>^.v<vvv<.>><v>><^>><>^<><v<>>>><v>v<^<>^.v..v^vv<v<<vv.v>>v<>v.<..^<vv<^v^v.v>>v>><^v>^<.vv^^<<><<>v>><#
+#.vv<vv<>.v<<<<<>>vv<>^v^^<^<>><.<^>^<^>^<v<<<<v>v>><.><.^><>vv<^^><<<<>^<.<v^.vv^vv>v>^.<<<><v<.v.<><<v^^v>^^<^>>^.<v^v.v><<v^vv<<v>^v>><^^<^<v>^>><v<#
+#<v^>v^vv<><v><<^<>^<^vv>v>>^^><<<vv><v.v.^><<^><>v>^<^v<<^>v<vv><v<<^.vv^>>>.^v>v.><v>v<^<^^<><<>><<^^^>v<^>>^v>>vv.<>^<><<^v>><^.>v^v><<^^^^<v<>^v<v.#
+#<<^<vv^<^><>^><>^vv.v^v>><^^<>^<>>^><^.^^<.v...>^^.^<<v<vvv>>>v^..^v.v<^><>.>v^.vv<^^vv>vv^.^.vv<v>>^>v.^^^<v<>><vv^>>^^.v>.v^^<^>vvv^<<v^<v<^><^>v<>>#
+#<.<^>>^<v><^>^^.>>v^<v^vvv>>vv.v^<>^^>v<<vv^<>^v.<<<^>>>.^>vvv.^^^<^><<^><v>><^.^>vv^^vv.><<v<^<v^^^.>v>^>v.^^<<^^^>^><><<vv<.<>v>vv>><^^v>>vvv^<...<<#
+#><v.v>vv>^^^>>><v>^^v>^>>><vv^<^<^<<<>.<<.<.<..><><v.v^^.v..v^>>>^v><.^^><<>v^<^<>^>>.v^v.v.>v>^>>>v>>^>><^<.v.v<^<<<<<^^>^^^^>^^<v^>>v><>.<>v><>.>><>#
+#<><<.>^<>^^v<v>^><^>v^.>><vv^vv^<v<<>.>.>>.vv.v<.^<^<>>^><><^.v>>v^^v><>><<<vv<<>v><>^.>>^>v^^><^<v<<><vv^>>.<^<.^<^>vvv>^<.v<^<>.><.>>v<^>^v<<.^<v>^<#
+#<>.<v^>.^<<^v^.<<^>v^^vv<^><^<^>><v^^vvv<<vvvv>>^v><<>^>vvvvv^<<v^.>^<.<^>.^>^><v^<>>.<<^^vv>>>^>vv><vvv^v.>^vv><<<<>^v^^^.>.^>>^^v^v>v>vv^<<^vv^<>v<>#
+#<<>v>v>>v^^v><^<.vv<^>^^>.v^<.^^vv>.<>^<>v>^>vvv<vv^>v^><<<v>vv<..^v^v>v.v><^.<^>.v<v><v>v^>^<<<<<>^.v<^.<v.<<^>v^^^<^<<>v.<<^<<<<.<^><<<^<v<v>>v>.><>#
+#>>.>vvv<<..>^^vv^>.<.v..v^^>^v<<>>>vv.<v>vv^<vv^v><v^^.<<.><..><^><<>^<<><v<.<v.<^<^.^<^<<><><<^v^>.<<v^^>.^<...v.^<^^<><><>v^<><^>^>^v^.>^^>^.vv.<v^>#
+#>.<><v>v<v>v>^v^^v>.v^.v>v>.<>>>^vv<<v>>^>^.^<^vv.vvvv<<>v<^^.>v<^v<<^><^.^^v<>.v<vv><v<v>vvv>^^>v>..<<<v..>v..<^^^<v>^^<<vv<>>^^v^.vv<><^>>.^<<^>>v.>#
+#><v..vv^<v^<>>v<>..<^>v^^><.>vv^vv^<^^v<>vv<.vv^^<>^>>^v<^^<<>^vv>v><>v<^vvv^<>><>^^^v^<v.v^<<^^>>>>><^^>><^v>>vv^v><^>^<<^.v>vv>^.v^<vv^v>>>vv>v^v<^>#
+#...>><v.<v<>^.v.v..^>^<><vv^><<<vv^<vv.><^.vv>>><v^v^>^v>>v<.^<^^<v^<>v<^<><<<.^<<vv.<>>^v^^.v>.<v>^.^>v^.v><^<<>>>^.<<<^v<<<><^>.^.^v><>^>><vv<v.<.^>#
+#<^vv>>v>v<^><^^^<^>vv<>vv>^^^.><><^>v>><v.<>vv^^<^<<<v^<><v>v^v>^<><><><><>^^>><>..^^>v<...vv<^>><.vv<^<v><v<vv^.><>v^<>v.^>>>v<<^<<^vv.>^<.^<>^<v^^^>#
+#>>^vv^.<<.<.<>>vvv<<<..<v><^<>^><<>^.<<^^^<v^<<v.<vv<^<>>vv^>.v^v<^<>>vv<<^>>.v>.v>^^^vvv^v<^><v^><>><^<.>v^^^<vv^>^v<v^<vv><>..^><.>^^<^>>..^.v^<^<v>#
+#<<><^^><v^v<^^<vv>><v..>>>^><>>>v>v>v>v><>>^vv><>>v>>vvvv<<^><>v^>vv>^.>>v.^<v<^.>>>^^v>>><vvv>><.<v<^<v<^v<v<<vvv..^^<<^<.<><<<<^<>v<<<^^>.^v>^^v<^^<#
+#>v^^^<v>^^<v<<<vv><^v.v<v^^^vvv<<><><^^><^^>>>>>><^>^^.>vv>^><<<v<<<^vv.^^^<v>v<^^^^>.^^vv<^<.<v^<vv^^^>><..><^>v><<v>v>^v^>>^^>vv.v^^^>^^vv.<<v.^><<.#
+#<^v<<^^vvv.>v>v>.v><v<^^>^>^>^^v>v^vv^<.^.>>>>>v<>.<<.<^<<vvv..<^>^><^>^<^<<>><^>v<v^v>^v^^^>>>>v>^>>^<v..><.>>^^><^<^.<v^>^.v>^^vv^v.<>>>>.v.<<>^^vv>#
+#<v^v.>.>^v>^<v.<^<^>v^>^^.>.>v<>>>^>vv<>v<>^>v^<<^<.<<^>v^<><>><^^<^^v<>>vv<<.<>v>.>^^^>><^^<^vv.><v<.<<^^>^>><>v><^vv.>v^v^v..<vvv..<<v<v^<<v>^<^>><<#
+#<^v<v^^v^>^<>v^<^<>>..>><>v<.^<.>v.>^v.>>^^<^v>>v^.v>^><>>vv.<<<>v>^.>v>..<<<v.<v^<>^>^<>v<^<v<><^>^v><.<<^^^<^.<<<^.^v^^.>^.<<vv>^v><<>^<^v^^>^v><<^>#
+######################################################################################################################################################.#
diff --git a/2022/src/bin/day_24.rs b/2022/src/bin/day_24.rs
new file mode 100644
index 0000000..71edc71
--- /dev/null
+++ b/2022/src/bin/day_24.rs
@@ -0,0 +1,195 @@
+use nom::{
+    branch::alt,
+    bytes::complete::tag,
+    character::complete::line_ending,
+    combinator::{map, value},
+    multi::{many1, separated_list1},
+    sequence::{delimited, tuple},
+    IResult,
+};
+use std::{collections::BTreeSet, fs};
+
+fn main() -> Result<(), Box<dyn std::error::Error>> {
+    let input = fs::read_to_string("inputs/day_24.txt")?;
+    let blizzard_map = BlizzardMap::parser(&input).unwrap().1;
+    let start = Point { x: 0, y: 0 };
+    let end = Point {
+        x: blizzard_map.width - 1,
+        y: blizzard_map.height - 1,
+    };
+    let there_the_first_time =
+        dbg!(blizzard_map.find_shortest_path_through(start.clone(), end.clone(), 1));
+    let back_again = dbg!(blizzard_map.find_shortest_path_through(
+        end.clone(),
+        start.clone(),
+        there_the_first_time + 1
+    ));
+    dbg!(blizzard_map.find_shortest_path_through(start, end, back_again + 1));
+
+    Ok(())
+}
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+struct BlizzardMap {
+    width: usize,
+    height: usize,
+    blizzards: Vec<Blizzard>,
+}
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+struct Blizzard {
+    start: Point,
+    direction: Direction,
+}
+
+#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord)]
+struct Point {
+    y: usize,
+    x: usize,
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
+enum Direction {
+    North,
+    South,
+    West,
+    East,
+}
+
+impl BlizzardMap {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        map(
+            delimited(
+                tuple((many1(tag("#")), tag("."), many1(tag("#")), line_ending)),
+                separated_list1(
+                    line_ending,
+                    delimited(tag("#"), many1(Direction::parser), tag("#")),
+                ),
+                tuple((line_ending, many1(tag("#")), tag("."), many1(tag("#")))),
+            ),
+            |blizzard_directions| BlizzardMap {
+                width: blizzard_directions[0].len(),
+                height: blizzard_directions.len(),
+                blizzards: blizzard_directions
+                    .into_iter()
+                    .enumerate()
+                    .flat_map(|(y, row)| {
+                        row.into_iter()
+                            .enumerate()
+                            .filter_map(move |(x, direction)| {
+                                direction.map(|direction| Blizzard {
+                                    start: Point { x, y },
+                                    direction,
+                                })
+                            })
+                    })
+                    .collect(),
+            },
+        )(input)
+    }
+
+    fn find_shortest_path_through(
+        &self,
+        start: Point,
+        end: Point,
+        mut current_round: usize,
+    ) -> usize {
+        // Not sure if "visited" makes sense here because of the time
+        // delay. Same position at different times is different. Maybe
+        // makes sense if I keep time in too.
+        let mut frontier = BTreeSet::new();
+        frontier.insert(start);
+        while !frontier.contains(&end) {
+            current_round += 1;
+            let last_frontier = std::mem::take(&mut frontier);
+
+            let blizzards = self.blizzards_at_time(current_round);
+
+            for frontier_state in last_frontier {
+                let mut possible_moves = vec![frontier_state.clone()];
+                if frontier_state.x > 0 {
+                    possible_moves.push(Point {
+                        x: frontier_state.x - 1,
+                        y: frontier_state.y,
+                    });
+                }
+                if frontier_state.x < self.width - 1 {
+                    possible_moves.push(Point {
+                        x: frontier_state.x + 1,
+                        y: frontier_state.y,
+                    });
+                }
+                if frontier_state.y > 0 {
+                    possible_moves.push(Point {
+                        x: frontier_state.x,
+                        y: frontier_state.y - 1,
+                    });
+                }
+                if frontier_state.y < self.height - 1 {
+                    possible_moves.push(Point {
+                        x: frontier_state.x,
+                        y: frontier_state.y + 1,
+                    });
+                }
+
+                for next in possible_moves {
+                    if !blizzards.contains(&next) {
+                        frontier.insert(next);
+                    }
+                }
+            }
+        }
+
+        current_round + 1 // extra minute to leave
+    }
+
+    fn blizzards_at_time(&self, t: usize) -> BTreeSet<Point> {
+        self.blizzards
+            .iter()
+            .map(|blizzard| match blizzard.direction {
+                Direction::North => {
+                    let t = t % self.height;
+                    Point {
+                        y: if blizzard.start.y > t {
+                            blizzard.start.y - t
+                        } else {
+                            blizzard.start.y + self.height - t
+                        },
+                        ..blizzard.start
+                    }
+                }
+                Direction::South => Point {
+                    y: (blizzard.start.y + t) % self.height,
+                    ..blizzard.start
+                },
+                Direction::West => {
+                    let t = t % self.width;
+                    Point {
+                        x: if blizzard.start.x > t {
+                            blizzard.start.x - t
+                        } else {
+                            blizzard.start.x + self.width - t
+                        },
+                        ..blizzard.start
+                    }
+                }
+                Direction::East => Point {
+                    x: (blizzard.start.x + t) % self.width,
+                    ..blizzard.start
+                },
+            })
+            .collect()
+    }
+}
+
+impl Direction {
+    fn parser(input: &str) -> IResult<&str, Option<Self>> {
+        alt((
+            value(None, tag(".")),
+            value(Some(Direction::South), tag("v")),
+            value(Some(Direction::West), tag("<")),
+            value(Some(Direction::East), tag(">")),
+            value(Some(Direction::North), tag("^")),
+        ))(input)
+    }
+}