Day 23 part 2

1 files changed, 122 insertions, 57 deletions

diff --git a/2023/src/bin/day_23.rs b/2023/src/bin/day_23.rs
index 801b0b4..40d0b70 100644
--- a/2023/src/bin/day_23.rs
+++ b/2023/src/bin/day_23.rs
@@ -6,13 +6,19 @@ use nom::{
     multi::{many1, separated_list1},
     IResult,
 };
-use std::{collections::HashSet, fs};
+use std::{
+    collections::{HashMap, HashSet},
+    fs,
+};
 
 fn main() -> Result<(), Box<dyn std::error::Error>> {
     let input = fs::read_to_string("inputs/day_23.txt")?;
     let forest_map = ForestMap::parser(&input).unwrap().1;
-    dbg!(forest_map.longest_end_path_length(true));
-    dbg!(forest_map.longest_end_path_length(false));
+    let slippery_forked_forest_map = forest_map.build_forked_map(true);
+    let dry_forked_forest_map = forest_map.build_forked_map(false);
+
+    dbg!(&slippery_forked_forest_map.longest_end_path_length());
+    dbg!(&dry_forked_forest_map.longest_end_path_length());
 
     Ok(())
 }
@@ -36,6 +42,26 @@ struct DecisionNode {
     current: Point2<usize>,
 }
 
+#[derive(Debug)]
+struct ForkedForestMap {
+    start: Point2<usize>,
+    end: Point2<usize>,
+    connections: HashMap<Point2<usize>, Vec<ForkConnection>>,
+}
+
+#[derive(Debug)]
+struct ForkConnection {
+    to: Point2<usize>,
+    distance: usize,
+}
+
+#[derive(Debug, Clone)]
+struct ForkedDecisionNode {
+    explored_forks: HashSet<Point2<usize>>,
+    current: Point2<usize>,
+    current_len: usize,
+}
+
 impl ForestMap {
     fn parser(input: &str) -> IResult<&str, Self> {
         map(
@@ -44,60 +70,6 @@ impl ForestMap {
         )(input)
     }
 
-    fn longest_end_path_length(&self, slippery: bool) -> usize {
-        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 longest_end_path_length: Option<usize> = None;
-
-        while let Some(mut node) = active_nodes.pop() {
-            let mut all_adjacent = self.adjacent(&node.current, &node.explored, slippery);
-            while all_adjacent.len() == 1 {
-                let adjacent = all_adjacent[0];
-                node.explored.insert(adjacent);
-                node.current = adjacent;
-
-                if node.current == end_point {
-                    let end_path_length = node.path_length();
-                    longest_end_path_length = if let Some(current_longest) = longest_end_path_length
-                    {
-                        Some(current_longest.max(end_path_length))
-                    } else {
-                        Some(end_path_length)
-                    };
-                    all_adjacent = vec![];
-                } else {
-                    all_adjacent = self.adjacent(&node.current, &node.explored, slippery);
-                }
-            }
-
-            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 {
-                    let end_path_length = new_node.path_length();
-                    longest_end_path_length = if let Some(current_longest) = longest_end_path_length
-                    {
-                        Some(current_longest.max(end_path_length))
-                    } else {
-                        Some(end_path_length)
-                    };
-                } else {
-                    active_nodes.push(new_node);
-                }
-            }
-        }
-
-        longest_end_path_length.unwrap()
-    }
-
     fn adjacent(
         &self,
         p: &Point2<usize>,
@@ -131,6 +103,63 @@ impl ForestMap {
     fn at(&self, p: &Point2<usize>) -> ForestTile {
         self.0[p.y][p.x]
     }
+
+    fn build_forked_map(&self, slippery: bool) -> ForkedForestMap {
+        let start = Point2::new(1, 0);
+        let end = Point2::new(self.0[0].len() - 2, self.0.len() - 1);
+        let mut forks = Vec::new();
+        forks.push(start);
+        forks.push(end);
+
+        for y in 1..self.0.len() - 1 {
+            for x in 1..self.0[y].len() - 1 {
+                let p = Point2::new(x, y);
+                if self.at(&p) != ForestTile::Wall {
+                    let adjacent_count = self.adjacent(&p, &HashSet::new(), false).len();
+                    if adjacent_count > 2 {
+                        forks.push(p);
+                    }
+                }
+            }
+        }
+
+        let mut connections = HashMap::new();
+
+        for start_point in &forks {
+            let mut active_nodes = vec![DecisionNode {
+                explored: HashSet::new(),
+                current: start_point.clone(),
+            }];
+            active_nodes[0].explored.insert(start_point.clone());
+
+            let mut fork_connections = Vec::new();
+
+            while let Some(node) = active_nodes.pop() {
+                for adjacent in self.adjacent(&node.current, &node.explored, slippery) {
+                    let mut new_node = node.clone();
+                    new_node.explored.insert(adjacent);
+                    new_node.current = adjacent;
+
+                    if forks.contains(&new_node.current) {
+                        fork_connections.push(ForkConnection {
+                            to: new_node.current,
+                            distance: new_node.path_length(),
+                        });
+                    } else {
+                        active_nodes.push(new_node);
+                    }
+                }
+            }
+
+            connections.insert(start_point.clone(), fork_connections);
+        }
+
+        ForkedForestMap {
+            start,
+            end,
+            connections,
+        }
+    }
 }
 
 impl ForestTile {
@@ -151,3 +180,39 @@ impl DecisionNode {
         self.explored.len() - 1
     }
 }
+
+impl ForkedForestMap {
+    fn longest_end_path_length(&self) -> usize {
+        let mut active_nodes = vec![ForkedDecisionNode {
+            explored_forks: HashSet::new(),
+            current: self.start,
+            current_len: 0,
+        }];
+        active_nodes[0].explored_forks.insert(self.start);
+        let mut longest_end_path_length: Option<usize> = None;
+
+        while let Some(node) = active_nodes.pop() {
+            for adjacent in self.connections.get(&node.current).unwrap() {
+                if !node.explored_forks.contains(&adjacent.to) {
+                    let mut new_node = node.clone();
+                    new_node.explored_forks.insert(adjacent.to);
+                    new_node.current = adjacent.to;
+                    new_node.current_len += adjacent.distance;
+
+                    if new_node.current == self.end {
+                        longest_end_path_length =
+                            if let Some(current_longest) = longest_end_path_length {
+                                Some(current_longest.max(new_node.current_len))
+                            } else {
+                                Some(new_node.current_len)
+                            };
+                    } else {
+                        active_nodes.push(new_node);
+                    }
+                }
+            }
+        }
+
+        longest_end_path_length.unwrap()
+    }
+}