Day 21 - number for how filled the walled garden can be

1 files changed, 75 insertions, 18 deletions

diff --git a/2023/src/bin/day_21.rs b/2023/src/bin/day_21.rs
index 11cdc07..f1bc29d 100644
--- a/2023/src/bin/day_21.rs
+++ b/2023/src/bin/day_21.rs
@@ -10,12 +10,15 @@ 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;
+
+    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());
 
-    let mut open_garden = OpenGarden::parser(&input).unwrap().1;
     // - 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
@@ -23,20 +26,22 @@ fn main() -> Result<(), Box<dyn std::error::Error>> {
     // - 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.
 
-    let open_iters = 26501365;
-    for i in 0..open_iters {
-        if i % 100000 == 0 {
-            println!("{}", i as f32 / open_iters as f32);
-        }
-        open_garden.next_mut();
-    }
-    dbg!(&open_garden.count_walkable());
+    // 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(())
 }
 
 #[derive(Debug)]
-struct WalledGarden(Vec<Vec<WalledGardenState>>);
+struct WalledGarden {
+    tiles: Vec<Vec<WalledGardenState>>,
+    odd_max_countable: usize,
+    even_max_countable: usize,
+}
 
 #[derive(Debug, Clone, Copy, PartialEq, Eq)]
 enum WalledGardenState {
@@ -46,18 +51,60 @@ enum WalledGardenState {
 }
 
 impl WalledGarden {
+    fn new(tiles: Vec<Vec<WalledGardenState>>) -> WalledGarden {
+        let mut odd_max_countable = 0;
+        let mut even_max_countable = 0;
+
+        let mut inner_figuring_out_max = WalledGarden {
+            tiles: tiles.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();
+
+            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 {
+            tiles,
+            odd_max_countable,
+            even_max_countable,
+        }
+    }
+
     fn parser(input: &str) -> IResult<&str, Self> {
         map(
             separated_list1(line_ending, many1(WalledGardenState::parser)),
-            WalledGarden,
+            WalledGarden::new,
         )(input)
     }
 
     fn next(&self) -> WalledGarden {
-        WalledGarden(
-            (0..self.0.len() as isize)
+        WalledGarden {
+            tiles: (0..self.tiles.len() as isize)
                 .map(|y| {
-                    (0..self.0[y as usize].len() as isize)
+                    (0..self.tiles[y as usize].len() as isize)
                         .map(|x| {
                             let current = self.get(y, x);
                             let neighbours = [
@@ -77,7 +124,9 @@ impl WalledGarden {
                         .collect::<Vec<WalledGardenState>>()
                 })
                 .collect(),
-        )
+            even_max_countable: self.even_max_countable,
+            odd_max_countable: self.odd_max_countable,
+        }
     }
 
     fn get(&self, y: isize, x: isize) -> WalledGardenState {
@@ -86,21 +135,29 @@ impl WalledGarden {
         } else {
             let y = y as usize;
             let x = x as usize;
-            if y >= self.0.len() || x >= self.0[y].len() {
+            if y >= self.tiles.len() || x >= self.tiles[y].len() {
                 WalledGardenState::Rock
             } else {
-                self.0[y][x]
+                self.tiles[y][x]
             }
         }
     }
 
     fn count_walkable(&self) -> usize {
-        self.0
+        self.tiles
             .iter()
             .flat_map(|row| row.iter())
             .filter(|s| **s == WalledGardenState::Walkable)
             .count()
     }
+
+    fn walkable_spots_when_full(&self, is_even: bool) -> usize {
+        if is_even {
+            self.even_max_countable
+        } else {
+            self.odd_max_countable
+        }
+    }
 }
 
 impl WalledGardenState {