Day 21 - start approach that seems like it will actually work

Just need to fill in the middle

1 files changed, 125 insertions, 149 deletions

diff --git a/2023/src/bin/day_21.rs b/2023/src/bin/day_21.rs
index e3e5df4..7cb510b 100644
--- a/2023/src/bin/day_21.rs
+++ b/2023/src/bin/day_21.rs
@@ -14,13 +14,6 @@ fn main() -> Result<(), Box<dyn std::error::Error>> {
     dbg!(garden.count_closed_walls_walkable_after_steps(garden.center(), 64));
     dbg!(garden.count_open_walls_walkable_after_steps(26501365));
 
-    // let mut open_garden = OpenGarden::parser(&input).unwrap().1;
-    // let open_iters = 26501365;
-    // for i in 0..open_iters {
-    //     open_garden.next_mut();
-    // }
-    // dbg!(&open_garden.count_walkable());
-
     Ok(())
 }
 
@@ -29,8 +22,6 @@ struct WalledGarden {
     rocks: Vec<Vec<bool>>,
     walkable_to: Vec<Vec<bool>>,
     walkable_to_back: Vec<Vec<bool>>,
-    odd_max_countable: usize,
-    even_max_countable: usize,
 }
 
 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
@@ -40,10 +31,21 @@ enum WalledGardenState {
     Rock,
 }
 
+#[derive(Debug)]
+struct MaxWalkable {
+    odd_steps_max: usize,
+    even_steps_max: usize,
+    min_steps: usize,
+}
+
+#[derive(Debug)]
+struct EntryPoint {
+    entry: (usize, usize),
+    max: MaxWalkable,
+}
+
 impl WalledGarden {
     fn new(tiles: Vec<Vec<WalledGardenState>>) -> WalledGarden {
-        let mut odd_max_countable = 0;
-        let mut even_max_countable = 0;
         let rocks: Vec<Vec<bool>> = tiles
             .iter()
             .map(|row| {
@@ -54,45 +56,10 @@ impl WalledGarden {
             .collect();
         let walkable_to: Vec<Vec<bool>> = vec![vec![false; rocks[0].len()]; rocks.len()];
 
-        let mut inner_figuring_out_max = WalledGarden {
-            rocks: rocks.clone(),
-            walkable_to_back: walkable_to.clone(),
-            walkable_to: walkable_to.clone(),
-            odd_max_countable: 0,
-            even_max_countable: 0,
-        };
-
-        let mut unchanged_count = 0;
-        for i in 1.. {
-            inner_figuring_out_max.closed_walls_next_mut();
-
-            if i % 2 == 0 {
-                let new_even_max_countable = inner_figuring_out_max.count_walkable();
-                if even_max_countable == new_even_max_countable {
-                    unchanged_count += 1;
-                } else {
-                    even_max_countable = new_even_max_countable;
-                }
-            } else {
-                let new_odd_max_countable = inner_figuring_out_max.count_walkable();
-                if odd_max_countable == new_odd_max_countable {
-                    unchanged_count += 1;
-                } else {
-                    odd_max_countable = new_odd_max_countable;
-                }
-            }
-
-            if unchanged_count > 1 {
-                break;
-            }
-        }
-
         WalledGarden {
             rocks,
             walkable_to_back: walkable_to.clone(),
             walkable_to: walkable_to.clone(),
-            odd_max_countable,
-            even_max_countable,
         }
     }
 
@@ -116,6 +83,44 @@ impl WalledGarden {
         garden.count_walkable()
     }
 
+    fn closed_walls_find_max_walkable(&self, start: (usize, usize)) -> MaxWalkable {
+        let mut odd_steps_max = 0;
+        let mut even_steps_max = 0;
+
+        let mut garden = self.clone();
+        garden.walkable_to[start.1][start.0] = true;
+
+        let mut unchanged_count = 0;
+        for i in 1.. {
+            garden.closed_walls_next_mut();
+
+            if i % 2 == 0 {
+                let new_even_max_countable = garden.count_walkable();
+                if even_steps_max == new_even_max_countable {
+                    unchanged_count += 1;
+                } else {
+                    even_steps_max = new_even_max_countable;
+                }
+            } else {
+                let new_odd_max_countable = garden.count_walkable();
+                if odd_steps_max == new_odd_max_countable {
+                    unchanged_count += 1;
+                } else {
+                    odd_steps_max = new_odd_max_countable;
+                }
+            }
+
+            if unchanged_count > 1 {
+                return MaxWalkable {
+                    odd_steps_max,
+                    even_steps_max,
+                    min_steps: i,
+                };
+            }
+        }
+        unreachable!()
+    }
+
     fn closed_walls_next_mut(&mut self) {
         for (y, row) in self.walkable_to_back.iter_mut().enumerate() {
             for (x, tile) in row.iter_mut().enumerate() {
@@ -128,7 +133,7 @@ impl WalledGarden {
             }
         }
 
-        std::mem::swap(&mut self.walkable_to, &mut self.walkable_to_back);
+        mem::swap(&mut self.walkable_to, &mut self.walkable_to_back);
     }
 
     fn count_walkable(&self) -> usize {
@@ -139,64 +144,84 @@ impl WalledGarden {
             .count()
     }
 
-    fn walkable_spots_when_full(&self, is_even: bool) -> usize {
-        if is_even {
-            self.even_max_countable
-        } else {
-            self.odd_max_countable
-        }
-    }
-
     fn count_open_walls_walkable_after_steps(&self, steps: usize) -> usize {
+        // assumptions:
+        // - this field is square
+        // - there is a direct path from the starting point up, down, left, and right
+        // - there is a direct path around the edges
+        // - the start is in the center
+
         let (size_x, size_y) = self.size();
         let (center_x, center_y) = self.center();
 
-        let max_y_deviance = ((steps - center_y) / size_y) as isize;
+        let max_chunks_deviance = (steps - center_y) / size_y;
 
         let mut total_walkable = 0;
 
-        // The paths straight up / down, and left / right from the middle and
-        // edges are clear, so it's possible to find the shortest path into
-        // another chunk trivially, and looking at only that chunk is
-        // equivalent.
-        for chunk_y in -max_y_deviance..=max_y_deviance {
-            dbg!(chunk_y);
-            let y_distance = if chunk_y == 0 {
-                0
-            } else {
-                center_y + 1 + (chunk_y.abs() as usize - 1) * size_y
-            };
-            let max_x_deviance = ((steps - y_distance - center_x) / size_x) as isize;
-            for chunk_x in -max_x_deviance..=max_x_deviance {
-                dbg!(chunk_x);
-                let x_distance = if chunk_x == 0 {
-                    0
-                } else {
-                    center_x + 1 + (chunk_x.abs() as usize - 1) * size_x
-                };
+        for quadrant in [
+            EntryPoint::new((0, 0), &self),
+            EntryPoint::new((size_x - 1, 0), &self),
+            EntryPoint::new((0, size_y - 1), &self),
+            EntryPoint::new((size_x - 1, size_y - 1), &self),
+        ] {
+            let mut distance_from_edge = 0;
+            loop {
+                let steps_in_chunk = steps
+                    - center_x
+                    - center_y
+                    - 2
+                    - (max_chunks_deviance - distance_from_edge - 1) * size_y;
+                if steps_in_chunk >= quadrant.max.min_steps
+                    || distance_from_edge == max_chunks_deviance
+                {
+                    break;
+                }
 
-                let steps_in_chunk = steps - y_distance - x_distance;
+                let walkable_per_chunk =
+                    self.count_closed_walls_walkable_after_steps(quadrant.entry, steps_in_chunk);
+                total_walkable +=
+                    walkable_per_chunk * (max_chunks_deviance - 1 - distance_from_edge);
+                distance_from_edge += 1;
+            }
 
-                // TODO: Identify fully walkable gardens to use the walkable_spots_when_full. Maybe for full rows at a time?
-                //
-                // if steps_in_chunk > 100 {
-                //     total_walkable += self.walkable_spots_when_full(steps_in_chunk % 2 == 0);
-                // }
+            // TODO: Checkerboard the remaining inside
+        }
 
-                let starting_x = match chunk_x.cmp(&0) {
-                    std::cmp::Ordering::Less => size_x - 1,
-                    std::cmp::Ordering::Equal => center_x,
-                    std::cmp::Ordering::Greater => 0,
-                };
-                let starting_y = match chunk_y.cmp(&0) {
-                    std::cmp::Ordering::Less => size_y - 1,
-                    std::cmp::Ordering::Equal => center_y,
-                    std::cmp::Ordering::Greater => 0,
-                };
-                let starting_point = (starting_x, starting_y);
-                total_walkable +=
-                    self.count_closed_walls_walkable_after_steps(starting_point, steps_in_chunk);
+        for cardinal in [
+            EntryPoint::new((0, center_y), &self),
+            EntryPoint::new((center_x, 0), &self),
+            EntryPoint::new((size_x - 1, center_y), &self),
+            EntryPoint::new((center_x, size_y - 1), &self),
+        ] {
+            let mut distance_from_edge = 0;
+            loop {
+                let steps_in_chunk =
+                    steps - center_y - 1 - (max_chunks_deviance - distance_from_edge - 1) * size_y;
+                if steps_in_chunk >= cardinal.max.min_steps
+                    || distance_from_edge == max_chunks_deviance
+                {
+                    break;
+                }
+
+                let walkable_per_chunk =
+                    self.count_closed_walls_walkable_after_steps(cardinal.entry, steps_in_chunk);
+                total_walkable += walkable_per_chunk;
+                distance_from_edge += 1;
             }
+
+            // TODO: Checkerboard the remaining inside
+        }
+
+        for center in [EntryPoint::new((center_x, center_y), &self)] {
+            total_walkable += if steps >= center.max.min_steps {
+                if steps % 2 == 0 {
+                    center.max.even_steps_max
+                } else {
+                    center.max.odd_steps_max
+                }
+            } else {
+                self.count_closed_walls_walkable_after_steps(center.entry, steps)
+            };
         }
 
         total_walkable
@@ -222,60 +247,11 @@ impl WalledGardenState {
     }
 }
 
-#[derive(Debug)]
-struct OpenGarden {
-    rockmap_size: (isize, isize),
-    rocks: BTreeSet<(isize, isize)>,
-    walkable: BTreeSet<(isize, isize)>,
-}
-
-impl OpenGarden {
-    fn parser(input: &str) -> IResult<&str, Self> {
-        map(
-            separated_list1(line_ending, many1(WalledGardenState::parser)),
-            |walled_garden_map| OpenGarden {
-                rockmap_size: (
-                    walled_garden_map.len() as isize,
-                    walled_garden_map[0].len() as isize,
-                ),
-                rocks: walled_garden_map
-                    .iter()
-                    .enumerate()
-                    .flat_map(|(y, row)| {
-                        row.iter().enumerate().filter_map(move |(x, s)| {
-                            (*s == WalledGardenState::Rock).then(|| (y as isize, x as isize))
-                        })
-                    })
-                    .collect(),
-                walkable: walled_garden_map
-                    .iter()
-                    .enumerate()
-                    .flat_map(|(y, row)| {
-                        row.iter().enumerate().filter_map(move |(x, s)| {
-                            (*s == WalledGardenState::Walkable).then(|| (y as isize, x as isize))
-                        })
-                    })
-                    .collect(),
-            },
-        )(input)
-    }
-
-    fn next_mut(&mut self) {
-        let walkable = mem::take(&mut self.walkable);
-        self.walkable = walkable
-            .iter()
-            .flat_map(|(y, x)| [(y - 1, *x), (y + 1, *x), (*y, x - 1), (*y, x + 1)])
-            .filter(|(y, x)| !self.is_rock(*y, *x))
-            .collect();
-    }
-
-    fn is_rock(&self, y: isize, x: isize) -> bool {
-        let y = y.rem_euclid(self.rockmap_size.0);
-        let x = x.rem_euclid(self.rockmap_size.1);
-        self.rocks.contains(&(y, x))
-    }
-
-    fn count_walkable(&self) -> usize {
-        self.walkable.len()
+impl EntryPoint {
+    fn new(entry: (usize, usize), garden: &WalledGarden) -> EntryPoint {
+        EntryPoint {
+            max: garden.closed_walls_find_max_walkable(entry),
+            entry,
+        }
     }
 }