From ef82c8d175f44a1d8b7cf7f5e0fffe9159fae74b Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Sun, 24 Dec 2023 09:41:48 +0200 Subject: Day 21 - Work with smaller chunks at a time --- 2023/src/bin/day_21.rs | 168 ++++++++++++++++++++++++++++++++----------------- 1 file changed, 110 insertions(+), 58 deletions(-) (limited to '2023/src/bin') diff --git a/2023/src/bin/day_21.rs b/2023/src/bin/day_21.rs index f1bc29d..e3e5df4 100644 --- a/2023/src/bin/day_21.rs +++ b/2023/src/bin/day_21.rs @@ -9,22 +9,10 @@ use std::{collections::BTreeSet, fs, mem}; fn main() -> Result<(), Box> { let input = fs::read_to_string("inputs/day_21.txt")?; - let mut walled_garden = WalledGarden::parser(&input).unwrap().1; + let garden = WalledGarden::parser(&input).unwrap().1; - dbg!(walled_garden.walkable_spots_when_full(true)); - dbg!(walled_garden.walkable_spots_when_full(false)); - - for _ in 0..64 { - walled_garden = walled_garden.next(); - } - dbg!(&walled_garden.count_walkable()); - - // - the paths straight up / down, and left / right from the middle and edges are clear. - // - this would allow finding a "single tile" version (eg part 1) to see how much of a tile could be filled at the boundaries. - // - start at the top boundary I can get into, 26501365 / 131 - // - when I find a fully explored garden, I can extrapolate that any closer gardens are also filled out - // - for filled out gardens, there will be an 'even' and an 'odd' answer (alternating checkerboard). choose the right one to add it. - // - this is still around 202300 pages in each direction, so multiplying the rows etc seems like a good idea. Eg do the two sides, then multiply out the fully explored middle. + 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; @@ -36,9 +24,11 @@ fn main() -> Result<(), Box> { Ok(()) } -#[derive(Debug)] +#[derive(Debug, Clone)] struct WalledGarden { - tiles: Vec>, + rocks: Vec>, + walkable_to: Vec>, + walkable_to_back: Vec>, odd_max_countable: usize, even_max_countable: usize, } @@ -54,16 +44,27 @@ 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| { + row.iter() + .map(|t| *t == WalledGardenState::Rock) + .collect::>() + }) + .collect(); + let walkable_to: Vec> = vec![vec![false; rocks[0].len()]; rocks.len()]; let mut inner_figuring_out_max = WalledGarden { - tiles: tiles.clone(), + 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 = inner_figuring_out_max.next(); + inner_figuring_out_max.closed_walls_next_mut(); if i % 2 == 0 { let new_even_max_countable = inner_figuring_out_max.count_walkable(); @@ -87,7 +88,9 @@ impl WalledGarden { } WalledGarden { - tiles, + rocks, + walkable_to_back: walkable_to.clone(), + walkable_to: walkable_to.clone(), odd_max_countable, even_max_countable, } @@ -100,54 +103,39 @@ impl WalledGarden { )(input) } - fn next(&self) -> WalledGarden { - WalledGarden { - tiles: (0..self.tiles.len() as isize) - .map(|y| { - (0..self.tiles[y as usize].len() as isize) - .map(|x| { - let current = self.get(y, x); - let neighbours = [ - self.get(y - 1, x), - self.get(y + 1, x), - self.get(y, x - 1), - self.get(y, x + 1), - ]; - if current == WalledGardenState::Rock { - WalledGardenState::Rock - } else if neighbours.contains(&WalledGardenState::Walkable) { - WalledGardenState::Walkable - } else { - WalledGardenState::Empty - } - }) - .collect::>() - }) - .collect(), - even_max_countable: self.even_max_countable, - odd_max_countable: self.odd_max_countable, + fn count_closed_walls_walkable_after_steps( + &self, + start: (usize, usize), + steps: usize, + ) -> usize { + let mut garden = self.clone(); + garden.walkable_to[start.1][start.0] = true; + for _ in 0..steps { + garden.closed_walls_next_mut(); } + garden.count_walkable() } - fn get(&self, y: isize, x: isize) -> WalledGardenState { - if y < 0 || x < 0 { - WalledGardenState::Rock - } else { - let y = y as usize; - let x = x as usize; - if y >= self.tiles.len() || x >= self.tiles[y].len() { - WalledGardenState::Rock - } else { - self.tiles[y][x] + 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() { + if !self.rocks[y][x] { + *tile = (y > 0 && self.walkable_to[y - 1][x]) + || (y < self.walkable_to.len() - 1 && self.walkable_to[y + 1][x]) + || (x > 0 && self.walkable_to[y][x - 1]) + || (x < self.walkable_to[y].len() - 1 && self.walkable_to[y][x + 1]); + } } } + + std::mem::swap(&mut self.walkable_to, &mut self.walkable_to_back); } fn count_walkable(&self) -> usize { - self.tiles + self.walkable_to .iter() .flat_map(|row| row.iter()) - .filter(|s| **s == WalledGardenState::Walkable) + .filter(|s| **s) .count() } @@ -158,6 +146,70 @@ impl WalledGarden { self.odd_max_countable } } + + fn count_open_walls_walkable_after_steps(&self, steps: usize) -> usize { + 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 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 + }; + + let steps_in_chunk = steps - y_distance - x_distance; + + // 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); + // } + + 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); + } + } + + total_walkable + } + + fn size(&self) -> (usize, usize) { + (self.rocks[0].len(), self.rocks.len()) + } + + fn center(&self) -> (usize, usize) { + let (size_x, size_y) = self.size(); + (size_x / 2, size_y / 2) + } } impl WalledGardenState { -- cgit v1.2.3