From 705e1a6ab99ee3292f8861b70664bfd0d7c2ea1a Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Wed, 27 Dec 2023 16:46:10 +0200 Subject: Days 21 and 18 part 2 --- 2023/src/bin/day_21.rs | 138 +++++++++++++++++++++++++++++++++++++++++++------ 1 file changed, 122 insertions(+), 16 deletions(-) (limited to '2023/src/bin/day_21.rs') 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> { let input = fs::read_to_string("inputs/day_21.txt")?; @@ -14,8 +14,6 @@ fn main() -> Result<(), Box> { 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) + ); +} -- cgit v1.2.3