Day 24

1 files changed, 195 insertions, 0 deletions

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)
+    }
+}