Day 23 part 1

2 files changed, 125 insertions, 4 deletions

diff --git a/2023/inputs/day_23_test.txt b/2023/inputs/day_23_test.txt
new file mode 100644
index 0000000..ea945a4
--- /dev/null
+++ b/2023/inputs/day_23_test.txt
@@ -0,0 +1,23 @@
+#.#####################
+#.......#########...###
+#######.#########.#.###
+###.....#.>.>.###.#.###
+###v#####.#v#.###.#.###
+###.>...#.#.#.....#...#
+###v###.#.#.#########.#
+###...#.#.#.......#...#
+#####.#.#.#######.#.###
+#.....#.#.#.......#...#
+#.#####.#.#.#########v#
+#.#...#...#...###...>.#
+#.#.#v#######v###.###v#
+#...#.>.#...>.>.#.###.#
+#####v#.#.###v#.#.###.#
+#.....#...#...#.#.#...#
+#.#########.###.#.#.###
+#...###...#...#...#.###
+###.###.#.###v#####v###
+#...#...#.#.>.>.#.>.###
+#.###.###.#.###.#.#v###
+#.....###...###...#...#
+#####################.#
diff --git a/2023/src/bin/day_23.rs b/2023/src/bin/day_23.rs
index 3a2bd48..3ff8d7f 100644
--- a/2023/src/bin/day_23.rs
+++ b/2023/src/bin/day_23.rs
@@ -1,3 +1,4 @@
+use nalgebra::Point2;
 use nom::{
     branch::alt,
     character::complete::{char, line_ending},
@@ -5,12 +6,13 @@ use nom::{
     multi::{many1, separated_list1},
     IResult,
 };
-use std::fs;
+use std::{collections::HashSet, fs};
 
 fn main() -> Result<(), Box<dyn std::error::Error>> {
     let input = fs::read_to_string("inputs/day_23.txt")?;
-    let parsed = ForestMap::parser(&input).unwrap().1;
-    dbg!(&parsed);
+    let forest_map = ForestMap::parser(&input).unwrap().1;
+    dbg!(forest_map.longest_end_path_length(true));
+    dbg!(forest_map.longest_end_path_length(false));
 
     Ok(())
 }
@@ -18,7 +20,7 @@ fn main() -> Result<(), Box<dyn std::error::Error>> {
 #[derive(Debug)]
 struct ForestMap(Vec<Vec<ForestTile>>);
 
-#[derive(Debug, Clone)]
+#[derive(Debug, Clone, Copy, PartialEq, Eq)]
 enum ForestTile {
     Wall,
     Open,
@@ -28,6 +30,12 @@ enum ForestTile {
     SlopeRight,
 }
 
+#[derive(Debug, Clone)]
+struct DecisionNode {
+    explored: HashSet<Point2<usize>>,
+    current: Point2<usize>,
+}
+
 impl ForestMap {
     fn parser(input: &str) -> IResult<&str, Self> {
         map(
@@ -35,6 +43,90 @@ impl ForestMap {
             ForestMap,
         )(input)
     }
+
+    fn find_end_paths(&self, slippery: bool) -> Vec<DecisionNode> {
+        let start_point = Point2::new(1, 0);
+        let end_point = Point2::new(self.0[0].len() - 2, self.0.len() - 1);
+
+        let mut active_nodes = vec![DecisionNode {
+            explored: HashSet::new(),
+            current: start_point,
+        }];
+        active_nodes[0].explored.insert(start_point);
+        let mut end_nodes = Vec::new();
+
+        while let Some(node) = active_nodes.pop() {
+            let all_adjacent = self.adjacent(&node.current, &node.explored, slippery);
+            if all_adjacent.len() == 1 {
+                let adjacent = all_adjacent[0];
+                let mut new_node = node;
+                new_node.explored.insert(adjacent);
+                new_node.current = adjacent;
+
+                if new_node.current == end_point {
+                    end_nodes.push(new_node);
+                } else {
+                    active_nodes.push(new_node);
+                }
+            } else {
+                for adjacent in all_adjacent {
+                    let mut new_node = node.clone();
+                    new_node.explored.insert(adjacent);
+                    new_node.current = adjacent;
+
+                    if new_node.current == end_point {
+                        end_nodes.push(new_node);
+                    } else {
+                        active_nodes.push(new_node);
+                    }
+                }
+            }
+        }
+
+        end_nodes
+    }
+
+    fn longest_end_path_length(&self, slippery: bool) -> usize {
+        self.find_end_paths(slippery)
+            .into_iter()
+            .map(|path| path.path_length())
+            .max()
+            .unwrap()
+    }
+
+    fn adjacent(
+        &self,
+        p: &Point2<usize>,
+        not_these: &HashSet<Point2<usize>>,
+        slippery: bool,
+    ) -> Vec<Point2<usize>> {
+        let mut adjacent = Vec::with_capacity(4);
+        let tile = self.at(p);
+
+        if p.x > 0 && (!slippery || matches!(tile, ForestTile::Open | ForestTile::SlopeLeft)) {
+            adjacent.push(Point2::new(p.x - 1, p.y));
+        }
+        if p.y > 0 && (!slippery || matches!(tile, ForestTile::Open | ForestTile::SlopeUp)) {
+            adjacent.push(Point2::new(p.x, p.y - 1));
+        }
+        if p.x < self.0[p.y].len() - 1
+            && (!slippery || matches!(tile, ForestTile::Open | ForestTile::SlopeRight))
+        {
+            adjacent.push(Point2::new(p.x + 1, p.y));
+        }
+        if p.y < self.0.len() - 1
+            && (!slippery || matches!(tile, ForestTile::Open | ForestTile::SlopeDown))
+        {
+            adjacent.push(Point2::new(p.x, p.y + 1));
+        }
+
+        adjacent.retain(|adj_p| self.at(adj_p) != ForestTile::Wall && !not_these.contains(adj_p));
+        adjacent
+    }
+
+    fn at(&self, p: &Point2<usize>) -> ForestTile {
+        self.0[p.y][p.x]
+    }
 }
 
 impl ForestTile {
@@ -49,3 +141,9 @@ impl ForestTile {
         ))(input)
     }
 }
+
+impl DecisionNode {
+    fn path_length(&self) -> usize {
+        self.explored.len() - 1
+    }
+}