Day 21 - Work with smaller chunks at a time

1 files changed, 110 insertions, 58 deletions

diff --git a/2023/src/bin/day_21.rs b/2023/src/bin/day_21.rs
index f1bc29d..e3e5df4 100644
--- a/2023/src/bin/day_21.rs
+++ b/2023/src/bin/day_21.rs
@@ -9,22 +9,10 @@ use std::{collections::BTreeSet, fs, mem};
 
 fn main() -> Result<(), Box<dyn std::error::Error>> {
     let input = fs::read_to_string("inputs/day_21.txt")?;
-    let mut walled_garden = WalledGarden::parser(&input).unwrap().1;
+    let garden = WalledGarden::parser(&input).unwrap().1;
 
-    dbg!(walled_garden.walkable_spots_when_full(true));
-    dbg!(walled_garden.walkable_spots_when_full(false));
-
-    for _ in 0..64 {
-        walled_garden = walled_garden.next();
-    }
-    dbg!(&walled_garden.count_walkable());
-
-    // - the paths straight up / down, and left / right from the middle and edges are clear.
-    // - this would allow finding a "single tile" version (eg part 1) to see how much of a tile could be filled at the boundaries.
-    // - start at the top boundary I can get into, 26501365 / 131
-    // - when I find a fully explored garden, I can extrapolate that any closer gardens are also filled out
-    // - for filled out gardens, there will be an 'even' and an 'odd' answer (alternating checkerboard). choose the right one to add it.
-    // - this is still around 202300 pages in each direction, so multiplying the rows etc seems like a good idea. Eg do the two sides, then multiply out the fully explored middle.
+    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;
@@ -36,9 +24,11 @@ fn main() -> Result<(), Box<dyn std::error::Error>> {
     Ok(())
 }
 
-#[derive(Debug)]
+#[derive(Debug, Clone)]
 struct WalledGarden {
-    tiles: Vec<Vec<WalledGardenState>>,
+    rocks: Vec<Vec<bool>>,
+    walkable_to: Vec<Vec<bool>>,
+    walkable_to_back: Vec<Vec<bool>>,
     odd_max_countable: usize,
     even_max_countable: usize,
 }
@@ -54,16 +44,27 @@ 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| {
+                row.iter()
+                    .map(|t| *t == WalledGardenState::Rock)
+                    .collect::<Vec<bool>>()
+            })
+            .collect();
+        let walkable_to: Vec<Vec<bool>> = vec![vec![false; rocks[0].len()]; rocks.len()];
 
         let mut inner_figuring_out_max = WalledGarden {
-            tiles: tiles.clone(),
+            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 = inner_figuring_out_max.next();
+            inner_figuring_out_max.closed_walls_next_mut();
 
             if i % 2 == 0 {
                 let new_even_max_countable = inner_figuring_out_max.count_walkable();
@@ -87,7 +88,9 @@ impl WalledGarden {
         }
 
         WalledGarden {
-            tiles,
+            rocks,
+            walkable_to_back: walkable_to.clone(),
+            walkable_to: walkable_to.clone(),
             odd_max_countable,
             even_max_countable,
         }
@@ -100,54 +103,39 @@ impl WalledGarden {
         )(input)
     }
 
-    fn next(&self) -> WalledGarden {
-        WalledGarden {
-            tiles: (0..self.tiles.len() as isize)
-                .map(|y| {
-                    (0..self.tiles[y as usize].len() as isize)
-                        .map(|x| {
-                            let current = self.get(y, x);
-                            let neighbours = [
-                                self.get(y - 1, x),
-                                self.get(y + 1, x),
-                                self.get(y, x - 1),
-                                self.get(y, x + 1),
-                            ];
-                            if current == WalledGardenState::Rock {
-                                WalledGardenState::Rock
-                            } else if neighbours.contains(&WalledGardenState::Walkable) {
-                                WalledGardenState::Walkable
-                            } else {
-                                WalledGardenState::Empty
-                            }
-                        })
-                        .collect::<Vec<WalledGardenState>>()
-                })
-                .collect(),
-            even_max_countable: self.even_max_countable,
-            odd_max_countable: self.odd_max_countable,
+    fn count_closed_walls_walkable_after_steps(
+        &self,
+        start: (usize, usize),
+        steps: usize,
+    ) -> usize {
+        let mut garden = self.clone();
+        garden.walkable_to[start.1][start.0] = true;
+        for _ in 0..steps {
+            garden.closed_walls_next_mut();
         }
+        garden.count_walkable()
     }
 
-    fn get(&self, y: isize, x: isize) -> WalledGardenState {
-        if y < 0 || x < 0 {
-            WalledGardenState::Rock
-        } else {
-            let y = y as usize;
-            let x = x as usize;
-            if y >= self.tiles.len() || x >= self.tiles[y].len() {
-                WalledGardenState::Rock
-            } else {
-                self.tiles[y][x]
+    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() {
+                if !self.rocks[y][x] {
+                    *tile = (y > 0 && self.walkable_to[y - 1][x])
+                        || (y < self.walkable_to.len() - 1 && self.walkable_to[y + 1][x])
+                        || (x > 0 && self.walkable_to[y][x - 1])
+                        || (x < self.walkable_to[y].len() - 1 && self.walkable_to[y][x + 1]);
+                }
             }
         }
+
+        std::mem::swap(&mut self.walkable_to, &mut self.walkable_to_back);
     }
 
     fn count_walkable(&self) -> usize {
-        self.tiles
+        self.walkable_to
             .iter()
             .flat_map(|row| row.iter())
-            .filter(|s| **s == WalledGardenState::Walkable)
+            .filter(|s| **s)
             .count()
     }
 
@@ -158,6 +146,70 @@ impl WalledGarden {
             self.odd_max_countable
         }
     }
+
+    fn count_open_walls_walkable_after_steps(&self, steps: usize) -> usize {
+        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 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
+                };
+
+                let steps_in_chunk = steps - y_distance - x_distance;
+
+                // 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);
+                // }
+
+                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);
+            }
+        }
+
+        total_walkable
+    }
+
+    fn size(&self) -> (usize, usize) {
+        (self.rocks[0].len(), self.rocks.len())
+    }
+
+    fn center(&self) -> (usize, usize) {
+        let (size_x, size_y) = self.size();
+        (size_x / 2, size_y / 2)
+    }
 }
 
 impl WalledGardenState {