From 078d5e8665968fdb30406e05b4832096ca1eedbb Mon Sep 17 00:00:00 2001
From: Justin Wernick <justin@worthe-it.co.za>
Date: Fri, 8 Dec 2023 13:02:44 +0200
Subject: Day 8 part 2

---
 2023/src/bin/day_8.rs | 75 ++++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 57 insertions(+), 18 deletions(-)

diff --git a/2023/src/bin/day_8.rs b/2023/src/bin/day_8.rs
index b96b43a..2da3cf5 100644
--- a/2023/src/bin/day_8.rs
+++ b/2023/src/bin/day_8.rs
@@ -11,7 +11,7 @@ use std::{collections::BTreeMap, fs, ops::Range};
 
 fn main() -> Result<(), Box<dyn std::error::Error>> {
     let input = fs::read_to_string("inputs/day_8.txt")?;
-    let directions = Directions::parser(&input).unwrap().1;
+    let mut directions = Directions::parser(&input).unwrap().1;
     dbg!(directions.steps_from_a_to_z());
     dbg!(directions.ghost_steps_from_a_to_z());
 
@@ -24,6 +24,7 @@ struct Directions {
     packed_map: Vec<PackedFork>,
     packed_ghost_starts: Range<u16>,
     packed_ghost_destinations: Range<u16>,
+    distance_to_ghost_dest_cache: BTreeMap<(u16, usize), (u16, usize)>,
 }
 
 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
@@ -86,6 +87,7 @@ impl Directions {
                     packed_ghost_destinations: locations.iter().position(|l| l.ghost_end()).unwrap()
                         as u16
                         ..locations.len() as u16,
+                    distance_to_ghost_dest_cache: BTreeMap::new(),
                 }
             },
         )(input)
@@ -110,28 +112,65 @@ impl Directions {
         unreachable!()
     }
 
-    fn ghost_steps_from_a_to_z(&self) -> usize {
-        let mut step_count = 0;
-        let mut current_locations: Vec<u16> = self.packed_ghost_starts.clone().collect();
+    fn ghost_steps_from_a_to_z(&mut self) -> usize {
+        let mut current_locations: Vec<(u16, usize)> = self
+            .packed_ghost_starts
+            .clone()
+            .map(|start| self.ghost_step_to_next_end(start, 0))
+            .collect();
 
-        for dir in self.turns.iter().cycle() {
-            for current_location in &mut current_locations {
-                let current_fork: &PackedFork = &self.packed_map[*current_location as usize];
-                *current_location = match dir {
-                    Turn::Left => current_fork.left,
-                    Turn::Right => current_fork.right,
-                };
-            }
-            step_count += 1;
+        let mut any_stepped = true;
+        while any_stepped {
+            any_stepped = false;
 
-            if current_locations
+            let current_max = current_locations
                 .iter()
-                .all(|l| self.packed_ghost_destinations.contains(l))
-            {
-                return step_count;
+                .map(|(_, steps)| steps.clone())
+                .max()
+                .unwrap();
+
+            for current_location in &mut current_locations {
+                if current_location.1 < current_max {
+                    any_stepped = true;
+                    let (new_location, extra_steps) =
+                        self.ghost_step_to_next_end(current_location.0, current_location.1);
+                    current_location.0 = new_location;
+                    current_location.1 += extra_steps;
+                }
             }
         }
-        unreachable!()
+
+        current_locations[0].1
+    }
+
+    fn ghost_step_to_next_end(&mut self, start: u16, current_step_count: usize) -> (u16, usize) {
+        self.distance_to_ghost_dest_cache
+            .entry((start, current_step_count % self.turns.len()))
+            .or_insert_with(|| {
+                let mut step_count = 0;
+                let mut current_location: u16 = start;
+
+                for dir in self
+                    .turns
+                    .iter()
+                    .skip(current_step_count % self.turns.len())
+                    .cycle()
+                {
+                    let current_fork: &PackedFork = &self.packed_map[current_location as usize];
+                    current_location = match dir {
+                        Turn::Left => current_fork.left,
+                        Turn::Right => current_fork.right,
+                    };
+                    step_count += 1;
+
+                    if self.packed_ghost_destinations.contains(&current_location) {
+                        break;
+                    }
+                }
+
+                (current_location, step_count)
+            })
+            .clone()
     }
 }
 
-- 
cgit v1.2.3