Day 21 - it gives a part 2 answer now, but it's the wrong answer, need debugging

1 files changed, 42 insertions, 10 deletions

diff --git a/2023/src/bin/day_21.rs b/2023/src/bin/day_21.rs
index 7cb510b..53a3a03 100644
--- a/2023/src/bin/day_21.rs
+++ b/2023/src/bin/day_21.rs
@@ -5,7 +5,7 @@ use nom::{
     multi::{many1, separated_list1},
     IResult,
 };
-use std::{collections::BTreeSet, fs, mem};
+use std::{fs, mem};
 
 fn main() -> Result<(), Box<dyn std::error::Error>> {
     let input = fs::read_to_string("inputs/day_21.txt")?;
@@ -14,6 +14,8 @@ 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));
 
+    // 609006215097383 is too low
+
     Ok(())
 }
 
@@ -164,15 +166,16 @@ impl WalledGarden {
             EntryPoint::new((0, size_y - 1), &self),
             EntryPoint::new((size_x - 1, size_y - 1), &self),
         ] {
+            let steps_to_quadrant_alignment = center_x + center_y + 2;
+
             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;
+                let steps_from_alignment_to_target_chunk =
+                    (max_chunks_deviance - distance_from_edge - 1) * size_y;
+                let steps_in_chunk =
+                    steps - steps_to_quadrant_alignment - steps_from_alignment_to_target_chunk;
                 if steps_in_chunk >= quadrant.max.min_steps
-                    || distance_from_edge == max_chunks_deviance
+                    || distance_from_edge == max_chunks_deviance - 1
                 {
                     break;
                 }
@@ -184,7 +187,21 @@ impl WalledGarden {
                 distance_from_edge += 1;
             }
 
-            // TODO: Checkerboard the remaining inside
+            let remaining_diagonals = max_chunks_deviance - 1 - distance_from_edge;
+            let even_length_diagonals = remaining_diagonals / 2;
+            let odd_length_diagonals = even_length_diagonals + remaining_diagonals % 2;
+
+            let even_length_diagonal_chunks = even_length_diagonals * (even_length_diagonals + 1);
+            let odd_length_diagonal_chunks = odd_length_diagonals.pow(2);
+
+            let odd_diagonal_has_even_steps_left = (steps - steps_to_quadrant_alignment) % 2 == 0;
+            total_walkable += if odd_diagonal_has_even_steps_left {
+                odd_length_diagonal_chunks * quadrant.max.even_steps_max
+                    + even_length_diagonal_chunks * quadrant.max.odd_steps_max
+            } else {
+                even_length_diagonal_chunks * quadrant.max.even_steps_max
+                    + odd_length_diagonal_chunks * quadrant.max.odd_steps_max
+            };
         }
 
         for cardinal in [
@@ -193,10 +210,14 @@ impl WalledGarden {
             EntryPoint::new((size_x - 1, center_y), &self),
             EntryPoint::new((center_x, size_y - 1), &self),
         ] {
+            let steps_to_cardinal_alignment = center_y + 1;
+
             let mut distance_from_edge = 0;
             loop {
+                let steps_from_alignment_to_target_chunk =
+                    (max_chunks_deviance - distance_from_edge - 1) * size_y;
                 let steps_in_chunk =
-                    steps - center_y - 1 - (max_chunks_deviance - distance_from_edge - 1) * size_y;
+                    steps - steps_to_cardinal_alignment - steps_from_alignment_to_target_chunk;
                 if steps_in_chunk >= cardinal.max.min_steps
                     || distance_from_edge == max_chunks_deviance
                 {
@@ -209,7 +230,18 @@ impl WalledGarden {
                 distance_from_edge += 1;
             }
 
-            // TODO: Checkerboard the remaining inside
+            let remaining_chunks = max_chunks_deviance - 1 - distance_from_edge;
+            let even_index_chunks = remaining_chunks / 2;
+            let odd_index_chunks = even_index_chunks + remaining_chunks % 2;
+
+            let odd_chunk_has_even_steps_left = (steps - steps_to_cardinal_alignment) % 2 == 0;
+            total_walkable += if odd_chunk_has_even_steps_left {
+                odd_index_chunks * cardinal.max.even_steps_max
+                    + even_index_chunks * cardinal.max.odd_steps_max
+            } else {
+                even_index_chunks * cardinal.max.even_steps_max
+                    + odd_index_chunks * cardinal.max.odd_steps_max
+            };
         }
 
         for center in [EntryPoint::new((center_x, center_y), &self)] {