Days 21 and 18 part 2

2 files changed, 158 insertions, 25 deletions

diff --git a/2023/src/bin/day_18.rs b/2023/src/bin/day_18.rs
index c3e9f58..a4c9355 100644
--- a/2023/src/bin/day_18.rs
+++ b/2023/src/bin/day_18.rs
@@ -16,9 +16,11 @@ fn main() -> Result<(), Box<dyn std::error::Error>> {
     let mut fill_map = parsed.draw_map();
     fill_map.derive_inside_outside();
     dbg!(&fill_map.count_inside());
+    dbg!(&parsed.find_internal_area());
 
     let hex_parsed = Instructions::hex_parser(&input).unwrap().1;
-    dbg!(&hex_parsed);
+    dbg!(&hex_parsed.find_internal_area());
+
     Ok(())
 }
 
@@ -27,15 +29,15 @@ struct Instructions(Vec<Instruction>);
 
 #[derive(Debug)]
 struct Instruction {
-    direction: Vector2<i32>,
+    direction: Vector2<i64>,
     distance: u32,
 }
 
 #[derive(Debug)]
 struct FloodFillMap {
-    map: HashMap<Point2<i32>, Fill>,
-    top_left: Point2<i32>,
-    bottom_right: Point2<i32>,
+    map: HashMap<Point2<i64>, Fill>,
+    top_left: Point2<i64>,
+    bottom_right: Point2<i64>,
 }
 
 #[derive(Debug, PartialEq, Eq, Clone, Copy)]
@@ -71,6 +73,31 @@ impl Instructions {
 
         FloodFillMap::new(trench)
     }
+
+    fn find_internal_area(&self) -> i64 {
+        let mut current_point = Point2::new(0, 0);
+        let mut points = vec![current_point];
+
+        let mut perimeter = 0;
+        for instruction in &self.0 {
+            let next_point = current_point + instruction.direction * instruction.distance as i64;
+            points.push(next_point);
+            current_point = next_point;
+            perimeter += instruction.distance as i64;
+        }
+
+        let mut area = 0;
+        for point in points.windows(2) {
+            if let &[p1, p2] = point {
+                area += p1.x * p2.y;
+                area -= p1.y * p2.x;
+            } else {
+                unreachable!()
+            }
+        }
+
+        (perimeter + 2 + area) / 2
+    }
 }
 
 impl Instruction {
@@ -112,7 +139,7 @@ impl Instruction {
     }
 }
 
-fn dir_parser(input: &str) -> IResult<&str, Vector2<i32>> {
+fn dir_parser(input: &str) -> IResult<&str, Vector2<i64>> {
     alt((
         value(Vector2::new(0, -1), char('U')),
         value(Vector2::new(0, 1), char('D')),
@@ -121,7 +148,7 @@ fn dir_parser(input: &str) -> IResult<&str, Vector2<i32>> {
     ))(input)
 }
 
-fn hex_dir_parser(input: &str) -> IResult<&str, Vector2<i32>> {
+fn hex_dir_parser(input: &str) -> IResult<&str, Vector2<i64>> {
     alt((
         value(Vector2::new(0, -1), char('3')),
         value(Vector2::new(0, 1), char('1')),
@@ -131,7 +158,7 @@ fn hex_dir_parser(input: &str) -> IResult<&str, Vector2<i32>> {
 }
 
 impl FloodFillMap {
-    fn new(map: HashMap<Point2<i32>, Fill>) -> FloodFillMap {
+    fn new(map: HashMap<Point2<i64>, Fill>) -> FloodFillMap {
         let top_left = Point2::new(
             map.keys().map(|key| key.x).min().unwrap() - 1,
             map.keys().map(|key| key.y).min().unwrap() - 1,
@@ -166,7 +193,7 @@ impl FloodFillMap {
             .count()
     }
 
-    fn flood_fill(&mut self, start: Point2<i32>, fill: &Fill) {
+    fn flood_fill(&mut self, start: Point2<i64>, fill: &Fill) {
         let mut to_fill = vec![start];
 
         while let Some(next) = to_fill.pop() {
diff --git a/2023/src/bin/day_21.rs b/2023/src/bin/day_21.rs
index 53a3a03..9ef273e 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::{fs, mem};
+use std::{collections::BTreeSet, fs, mem};
 
 fn main() -> Result<(), Box<dyn std::error::Error>> {
     let input = fs::read_to_string("inputs/day_21.txt")?;
@@ -14,8 +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));
 
-    // 609006215097383 is too low
-
     Ok(())
 }
 
@@ -156,7 +154,11 @@ impl WalledGarden {
         let (size_x, size_y) = self.size();
         let (center_x, center_y) = self.center();
 
-        let max_chunks_deviance = (steps - center_y) / size_y;
+        let max_chunks_deviance = if (steps - center_y) % size_y > 0 {
+            1 + (steps - center_y) / size_y
+        } else {
+            (steps - center_y) / size_y
+        };
 
         let mut total_walkable = 0;
 
@@ -169,25 +171,26 @@ impl WalledGarden {
             let steps_to_quadrant_alignment = center_x + center_y + 2;
 
             let mut distance_from_edge = 0;
-            loop {
+            while max_chunks_deviance > distance_from_edge {
                 let steps_from_alignment_to_target_chunk =
                     (max_chunks_deviance - distance_from_edge - 1) * size_y;
+                if steps_to_quadrant_alignment + steps_from_alignment_to_target_chunk > steps {
+                    distance_from_edge += 1;
+                    continue;
+                }
                 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 - 1
-                {
+                if steps_in_chunk >= quadrant.max.min_steps {
                     break;
                 }
 
                 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);
+                total_walkable += walkable_per_chunk * (max_chunks_deviance - distance_from_edge);
                 distance_from_edge += 1;
             }
 
-            let remaining_diagonals = max_chunks_deviance - 1 - distance_from_edge;
+            let remaining_diagonals = max_chunks_deviance - distance_from_edge;
             let even_length_diagonals = remaining_diagonals / 2;
             let odd_length_diagonals = even_length_diagonals + remaining_diagonals % 2;
 
@@ -213,14 +216,12 @@ impl WalledGarden {
             let steps_to_cardinal_alignment = center_y + 1;
 
             let mut distance_from_edge = 0;
-            loop {
+            while max_chunks_deviance > distance_from_edge {
                 let steps_from_alignment_to_target_chunk =
                     (max_chunks_deviance - distance_from_edge - 1) * size_y;
                 let steps_in_chunk =
                     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
-                {
+                if steps_in_chunk >= cardinal.max.min_steps {
                     break;
                 }
 
@@ -230,7 +231,7 @@ impl WalledGarden {
                 distance_from_edge += 1;
             }
 
-            let remaining_chunks = max_chunks_deviance - 1 - distance_from_edge;
+            let remaining_chunks = max_chunks_deviance - distance_from_edge;
             let even_index_chunks = remaining_chunks / 2;
             let odd_index_chunks = even_index_chunks + remaining_chunks % 2;
 
@@ -287,3 +288,108 @@ impl EntryPoint {
         }
     }
 }
+
+#[derive(Debug, Clone)]
+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 count_open_walls_walkable_after_steps(&self, steps: usize) -> usize {
+        let mut garden = self.clone();
+        for _ in 0..steps {
+            garden.next_mut();
+        }
+        garden.count_walkable()
+    }
+
+    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()
+    }
+}
+
+#[test]
+fn open_matches_optimized_for_small_steps() {
+    let input = fs::read_to_string("inputs/day_21.txt").unwrap();
+    let walled_garden = WalledGarden::parser(&input).unwrap().1;
+    let open_garden = OpenGarden::parser(&input).unwrap().1;
+
+    let steps = 132;
+    assert_eq!(
+        walled_garden.count_open_walls_walkable_after_steps(steps),
+        open_garden.count_open_walls_walkable_after_steps(steps)
+    );
+}
+
+#[test]
+fn open_matches_optimized_for_medium_steps() {
+    let input = fs::read_to_string("inputs/day_21.txt").unwrap();
+    let walled_garden = WalledGarden::parser(&input).unwrap().1;
+    let open_garden = OpenGarden::parser(&input).unwrap().1;
+
+    let steps = 65 + 132;
+    assert_eq!(
+        walled_garden.count_open_walls_walkable_after_steps(steps),
+        open_garden.count_open_walls_walkable_after_steps(steps)
+    );
+}
+
+#[test]
+fn open_matches_optimized_for_bigger_steps() {
+    let input = fs::read_to_string("inputs/day_21.txt").unwrap();
+    let walled_garden = WalledGarden::parser(&input).unwrap().1;
+    let open_garden = OpenGarden::parser(&input).unwrap().1;
+
+    let steps = 270;
+    assert_eq!(
+        walled_garden.count_open_walls_walkable_after_steps(steps),
+        open_garden.count_open_walls_walkable_after_steps(steps)
+    );
+}