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_18.rs | 45 ++++++++++++---- 2023/src/bin/day_21.rs | 138 +++++++++++++++++++++++++++++++++++++++++++------ 2 files changed, 158 insertions(+), 25 deletions(-) (limited to '2023/src') 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> { 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); #[derive(Debug)] struct Instruction { - direction: Vector2, + direction: Vector2, distance: u32, } #[derive(Debug)] struct FloodFillMap { - map: HashMap, Fill>, - top_left: Point2, - bottom_right: Point2, + map: HashMap, Fill>, + top_left: Point2, + bottom_right: Point2, } #[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> { +fn dir_parser(input: &str) -> IResult<&str, Vector2> { 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> { ))(input) } -fn hex_dir_parser(input: &str) -> IResult<&str, Vector2> { +fn hex_dir_parser(input: &str) -> IResult<&str, Vector2> { 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> { } impl FloodFillMap { - fn new(map: HashMap, Fill>) -> FloodFillMap { + fn new(map: HashMap, 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, fill: &Fill) { + fn flood_fill(&mut self, start: Point2, 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> { 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