From fbd01358bf0c10d9f2df4b7f73de0b62cea916a4 Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Wed, 27 Dec 2023 09:01:44 +0200 Subject: Day 21 - start approach that seems like it will actually work Just need to fill in the middle --- 2023/src/bin/day_21.rs | 274 ++++++++++++++++++++++--------------------------- 1 file changed, 125 insertions(+), 149 deletions(-) diff --git a/2023/src/bin/day_21.rs b/2023/src/bin/day_21.rs index e3e5df4..7cb510b 100644 --- a/2023/src/bin/day_21.rs +++ b/2023/src/bin/day_21.rs @@ -14,13 +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)); - // 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(()) } @@ -29,8 +22,6 @@ struct WalledGarden { rocks: Vec>, walkable_to: Vec>, walkable_to_back: Vec>, - odd_max_countable: usize, - even_max_countable: usize, } #[derive(Debug, Clone, Copy, PartialEq, Eq)] @@ -40,10 +31,21 @@ enum WalledGardenState { Rock, } +#[derive(Debug)] +struct MaxWalkable { + odd_steps_max: usize, + even_steps_max: usize, + min_steps: usize, +} + +#[derive(Debug)] +struct EntryPoint { + entry: (usize, usize), + max: MaxWalkable, +} + impl WalledGarden { fn new(tiles: Vec>) -> WalledGarden { - let mut odd_max_countable = 0; - let mut even_max_countable = 0; let rocks: Vec> = tiles .iter() .map(|row| { @@ -54,45 +56,10 @@ impl WalledGarden { .collect(); let walkable_to: Vec> = vec![vec![false; rocks[0].len()]; rocks.len()]; - let mut inner_figuring_out_max = WalledGarden { - rocks: rocks.clone(), - walkable_to_back: walkable_to.clone(), - walkable_to: walkable_to.clone(), - odd_max_countable: 0, - even_max_countable: 0, - }; - - let mut unchanged_count = 0; - for i in 1.. { - inner_figuring_out_max.closed_walls_next_mut(); - - 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 { rocks, walkable_to_back: walkable_to.clone(), walkable_to: walkable_to.clone(), - odd_max_countable, - even_max_countable, } } @@ -116,6 +83,44 @@ impl WalledGarden { garden.count_walkable() } + fn closed_walls_find_max_walkable(&self, start: (usize, usize)) -> MaxWalkable { + let mut odd_steps_max = 0; + let mut even_steps_max = 0; + + let mut garden = self.clone(); + garden.walkable_to[start.1][start.0] = true; + + let mut unchanged_count = 0; + for i in 1.. { + garden.closed_walls_next_mut(); + + if i % 2 == 0 { + let new_even_max_countable = garden.count_walkable(); + if even_steps_max == new_even_max_countable { + unchanged_count += 1; + } else { + even_steps_max = new_even_max_countable; + } + } else { + let new_odd_max_countable = garden.count_walkable(); + if odd_steps_max == new_odd_max_countable { + unchanged_count += 1; + } else { + odd_steps_max = new_odd_max_countable; + } + } + + if unchanged_count > 1 { + return MaxWalkable { + odd_steps_max, + even_steps_max, + min_steps: i, + }; + } + } + unreachable!() + } + fn closed_walls_next_mut(&mut self) { for (y, row) in self.walkable_to_back.iter_mut().enumerate() { for (x, tile) in row.iter_mut().enumerate() { @@ -128,7 +133,7 @@ impl WalledGarden { } } - std::mem::swap(&mut self.walkable_to, &mut self.walkable_to_back); + mem::swap(&mut self.walkable_to, &mut self.walkable_to_back); } fn count_walkable(&self) -> usize { @@ -139,64 +144,84 @@ impl WalledGarden { .count() } - fn walkable_spots_when_full(&self, is_even: bool) -> usize { - if is_even { - self.even_max_countable - } else { - self.odd_max_countable - } - } - fn count_open_walls_walkable_after_steps(&self, steps: usize) -> usize { + // assumptions: + // - this field is square + // - there is a direct path from the starting point up, down, left, and right + // - there is a direct path around the edges + // - the start is in the center + let (size_x, size_y) = self.size(); let (center_x, center_y) = self.center(); - let max_y_deviance = ((steps - center_y) / size_y) as isize; + let max_chunks_deviance = (steps - center_y) / size_y; let mut total_walkable = 0; - // The paths straight up / down, and left / right from the middle and - // edges are clear, so it's possible to find the shortest path into - // another chunk trivially, and looking at only that chunk is - // equivalent. - for chunk_y in -max_y_deviance..=max_y_deviance { - dbg!(chunk_y); - let y_distance = if chunk_y == 0 { - 0 - } else { - center_y + 1 + (chunk_y.abs() as usize - 1) * size_y - }; - let max_x_deviance = ((steps - y_distance - center_x) / size_x) as isize; - for chunk_x in -max_x_deviance..=max_x_deviance { - dbg!(chunk_x); - let x_distance = if chunk_x == 0 { - 0 - } else { - center_x + 1 + (chunk_x.abs() as usize - 1) * size_x - }; + for quadrant in [ + EntryPoint::new((0, 0), &self), + EntryPoint::new((size_x - 1, 0), &self), + EntryPoint::new((0, size_y - 1), &self), + EntryPoint::new((size_x - 1, size_y - 1), &self), + ] { + 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; + if steps_in_chunk >= quadrant.max.min_steps + || distance_from_edge == max_chunks_deviance + { + break; + } - let steps_in_chunk = steps - y_distance - x_distance; + 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); + distance_from_edge += 1; + } - // TODO: Identify fully walkable gardens to use the walkable_spots_when_full. Maybe for full rows at a time? - // - // if steps_in_chunk > 100 { - // total_walkable += self.walkable_spots_when_full(steps_in_chunk % 2 == 0); - // } + // TODO: Checkerboard the remaining inside + } - let starting_x = match chunk_x.cmp(&0) { - std::cmp::Ordering::Less => size_x - 1, - std::cmp::Ordering::Equal => center_x, - std::cmp::Ordering::Greater => 0, - }; - let starting_y = match chunk_y.cmp(&0) { - std::cmp::Ordering::Less => size_y - 1, - std::cmp::Ordering::Equal => center_y, - std::cmp::Ordering::Greater => 0, - }; - let starting_point = (starting_x, starting_y); - total_walkable += - self.count_closed_walls_walkable_after_steps(starting_point, steps_in_chunk); + for cardinal in [ + EntryPoint::new((0, center_y), &self), + EntryPoint::new((center_x, 0), &self), + EntryPoint::new((size_x - 1, center_y), &self), + EntryPoint::new((center_x, size_y - 1), &self), + ] { + let mut distance_from_edge = 0; + loop { + let steps_in_chunk = + steps - center_y - 1 - (max_chunks_deviance - distance_from_edge - 1) * size_y; + if steps_in_chunk >= cardinal.max.min_steps + || distance_from_edge == max_chunks_deviance + { + break; + } + + let walkable_per_chunk = + self.count_closed_walls_walkable_after_steps(cardinal.entry, steps_in_chunk); + total_walkable += walkable_per_chunk; + distance_from_edge += 1; } + + // TODO: Checkerboard the remaining inside + } + + for center in [EntryPoint::new((center_x, center_y), &self)] { + total_walkable += if steps >= center.max.min_steps { + if steps % 2 == 0 { + center.max.even_steps_max + } else { + center.max.odd_steps_max + } + } else { + self.count_closed_walls_walkable_after_steps(center.entry, steps) + }; } total_walkable @@ -222,60 +247,11 @@ impl WalledGardenState { } } -#[derive(Debug)] -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 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() +impl EntryPoint { + fn new(entry: (usize, usize), garden: &WalledGarden) -> EntryPoint { + EntryPoint { + max: garden.closed_walls_find_max_walkable(entry), + entry, + } } } -- cgit v1.2.3