From 57f1a76ed02df19c199c8ddd1e7f932822ea9e17 Mon Sep 17 00:00:00 2001
From: Justin Wernick <justin@worthe-it.co.za>
Date: Sat, 23 Dec 2023 14:41:54 +0200
Subject: Day 23 optimized solution

---
 2023/src/bin/day_23.rs | 60 +++++++++++++++++++++++++++-----------------------
 1 file changed, 32 insertions(+), 28 deletions(-)

(limited to '2023/src/bin/day_23.rs')

diff --git a/2023/src/bin/day_23.rs b/2023/src/bin/day_23.rs
index 3ff8d7f..801b0b4 100644
--- a/2023/src/bin/day_23.rs
+++ b/2023/src/bin/day_23.rs
@@ -44,7 +44,7 @@ impl ForestMap {
         )(input)
     }
 
-    fn find_end_paths(&self, slippery: bool) -> Vec<DecisionNode> {
+    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);
 
@@ -53,45 +53,49 @@ impl ForestMap {
             current: start_point,
         }];
         active_nodes[0].explored.insert(start_point);
-        let mut end_nodes = Vec::new();
+        let mut longest_end_path_length: Option<usize> = None;
 
-        while let Some(node) = active_nodes.pop() {
-            let all_adjacent = self.adjacent(&node.current, &node.explored, slippery);
-            if all_adjacent.len() == 1 {
+        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];
-                let mut new_node = node;
+                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 {
-                    end_nodes.push(new_node);
+                    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);
                 }
-            } 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()
+        longest_end_path_length.unwrap()
     }
 
     fn adjacent(
-- 
cgit v1.2.3