From b7379a29b9b83464bf60bca6d2d9e3e02863db94 Mon Sep 17 00:00:00 2001 From: Justin Wernick Date: Thu, 21 Dec 2023 22:30:07 +0200 Subject: Day 21 - Part 1 --- 2023/inputs/day_21.txt | 131 +++++++++++++++++++++++++++++++++++++++ 2023/src/bin/day_21.rs | 164 ++++++++++++++++++++++++++++++++++++++++++++++--- 2 files changed, 286 insertions(+), 9 deletions(-) create mode 100644 2023/inputs/day_21.txt diff --git a/2023/inputs/day_21.txt b/2023/inputs/day_21.txt new file mode 100644 index 0000000..b7f57f9 --- /dev/null +++ b/2023/inputs/day_21.txt @@ -0,0 +1,131 @@ +................................................................................................................................... +..............#...#........#...............#.#.......#....##...........#.#..#......#.....#.........#..##........................... +.#..##..##..#......#.#.#...##......###...##......#.#..#...................#.....#..........#..#................#...#..........#.... +.....................#..#.......#.....##.........#.......................................#........#....#.#..........#.#......#.#... +......##...#.....#.......#...#..###..........#..........#......................#........#.............#.....#........#....#........ +.................##.................#...#.........#................................#........#...........#............#........#.... +..............#.#....#........##.....##..........#.............##.............#...#......#..##..........#.........#.....#...#..#... +..#....#.......#...##..#......#.........#.#..#....#.#..............#........#...#...#...............#.#.....#..#..##......#...#.... +...#......##...##..#...#..........#...#..........#..............#...#..........#..#..#..#........#.#.#.#.#...........###........... +.#.#.#...#.#...##............................................#......................#...#......#......##.#......................... +.##.#.........#...#..................##...........#............#..................###...#...........#.................#....#....... +.....................#...#.#................#................#.#........................#...#...##....##....#.#...#.........#...#.. +...#.......#...#.........................#.#..................#........##..........................#......##....##............#.... +......................#.....................#...............#.......#.#...................#...............#...#........#.##......#. +............................#..........................#........#....#.##..#.......#.##..#...#.#..#...............#.#..#....#...... +.......................................................#.#..#.#....#......................#............#....#..#.......#.........#. +.....##........#...............#.......#...............#.#..........##..#...................#................#..#...#.#....#...###. +....#.....................##................#.......#.......#...#.#...#...............#................#...............##.......... +....#........#..#.......#.#.#........................#.#...........#.......#..#.........#....#.......#........#.#.#................ +......###.....#..#...........#.....#..#..#........#......#.#........###.....##............#..#...........#......................... +.....#...........#...................#..#..........#..#...###.#.........#.##...............#..##..........#.........#.............. +.#.........#....#............#.##..........................##.....#........#....#.............#.......#...#..............##.#...... +.#..#...#.......#...#.......##.......#.#.............................#...#...#.#...........#...#.................#.........#.#.#... +...#....................#.....##..............#.................#.................#............#......#....#.......#.........#..... +.......#...#.............#.##...#.#...................#.....#..#........#................................#.............#..#...##... +...#.###..............#....#........................#......#...#.........#......#.#....................#........#...#...#.......#.. +............#.#...#...........................#....###.###...#........#..#........#...................##.....###......#........#... +.....#...#................#.##..##..................#....#.........#............##...................##................#.....#..... +.#....#..............##...#..................#......#..........##.#....#......##.#...............#....##..............#....#....... +....#.#.##...........##.....#...........#.........#...#........#..#.......#......#................#.#...#....#...#................. +.......#...#...#...#..#.......#..........#..................#..#........#..#.#.....#.#.....................##...................... +.....##.........#.......##...#.............#.##.#.#...#.##.#...#......#...#....#.......#..#.........#...........#.##.###.#.....#... +...................#.#.......................#.....#.#......#.....##...#.#....#..#..........#...........#..##....#...#.......#.#... +.....#..#..#.........#...#.#.........#...#.#...##...#......##........#...............#.......#................#.....#...#.#........ +........#.....###.....................#.........#.........#.........#....##............#..##.............#.........#..#.......#.... +.#.........#....##..##.................#...#................................#...#.....#.........#.......#............#....#......#. +..#.........#.......#..................#..#.#...#........#.#.......#...##.#........#..........#.#..........#..#.....#.........#.... +..#...............#...................##.#.......#...#..........#....................##.........#.................#..#......##..#.. +.#........#.......#............##...........##........#.......................#................#....................#...###......#. +........###..........#..............#.............#..#.#.#............##...............#........#...#........#...................#. +...#............................#...##.##........#......#..#...................#.#.....#...#.##...............#........#...#....... +..#...##....................#.....##......#.......#..........#......#.........#...#..............#..............#.................. +.....#..#....................#....###.....#..#.............#...#....#................#.....#.....................#........#........ +.....#.#...#.....#..............##............#....##.#....#.#........##...........#....#.........................#....#......##... +....#..#.....##...........#.#.#.#............#....#.....#.........#........................##.......#.#..............##...#........ +...............#..............#................................#....#........#.......#.......##......#.#............#......#....#.. +.#......#....##........#.............#..#.#.............#...#..#.........#.........#................#..................#........... +.........#..............#....#......#.....##......#............#....#.........#....#...................#....#.........#......#..#.. +..............................#....#.#........#.#.....#..#.................#....#...#..........#............##.......#.#.#....#.... +.#..................#....#..#.......#.##..............#...#.......#................#............................................... +.#..##.........................#.....###......#....#......#.....#............#.#......##......##......##....#..........##.....#.... +..........................##.#.....#..........................................#.#..#....#..#..................#...........#........ +..##.....#.......#....#.........#..........#....................#.........#........###........................#..........#......... +.#.#...............#..........#.......#.....#....##.#..#.##...............#...#...#.#......#.......#.......#.#.............#....##. +..................#...............##.........##..#........#..#..........#.....................#............................#....... +.....#................#...##.......##.........#.....#.#....#.#........#...#..#....#..............#..#....#....#....#............... +..##.#........#...............#.#..#...................##...#......#.#...#..#.....##.................##...#.#...................#.. +...#...............#......#.....#.......#......#.........#...#......#...#..#....#..#......#.......#.......#...#.##.#...........##.. +..............##..........##..........#..##...............#...........##..#..#..#.#.......#...#.............#...................... +..........#.#........................#...#.#..#.#...##..#.#.#.#.......#....#.#.#..............#...#...#........###..##...........#. +......................#...#.#..##.....#....#.....###.#..#.....#..........#........#...........##...#..#...........##..#............ +..................................####.#..............#.................#........#.#............##......#.#..........#............. +..................#..........#.............................#...........#..#..#......#................#.......##...##..#............ +....................#...#....#.#.#.##......#................#.................#...........#....#..........#....#...##.###.......... +.................#.......#...#............###.###..#.......#......#.......#..##......#.#.....#.....................#............... +.................................................................S................................................................. +.......##...........#.........###.......#....###.#.#....#.#....#....#........#.......#...#...#.#.........#...................#..... +.......#...............#............#...#..#.......##...#...#.#............#.............#......##..........#..............#....... +.......##.........#.....................##...#...#.................#...#.......#..####......#.....#..............#..##............. +........#..#.............#.#..##..............#...#.............#.....#......#...#.#.......#...............##...##................. +.........#..#...#..#.#..#..#...................##......#.....#..#...##..............#......#..........#.##...#.#.##.#.............. +..............#..........#....................................#.........#.......#..#............##................#................ +...........#...#.....#.........#....#..###....#...#.......#....#...............##.....#.......#.#.....#.#....#.#..#................ +..#...................#........###..............#.#................#...###...##.............#.###......#...#...#.....#..........#.. +.#.#............#.....#....###......................................#..........................#..................#................ +................#..#...#................#.................##.................##..........#.......#...#.............#............... +.....##...........#....#.......#......#.#.....#.....#................#.....#.........#..#.................#........#........#...... +.#.#.............#..#.#..............#.....#..#.#.....#..#......#.........#.....#.#......#..#.......#.#......##............#..#.... +...................#............#....#...........#........#...................#.....##..............#........###...............#... +......###..........###.#.......#.................................................#..#.........#.#...#.........#.#..........#.#..... +..#.................#..#..#...#............#...#...#..##.#....##..#..................##.....#......#.........................#...#. +......................#.#.....#.#...#.......##...........#...#....#.............#.......#.............#.#.#.#...................... +......#..#.#..........#....#.........#......#................#.........##.#....#.......#........#.#....................#......#.... +..#....#....#...............#..........#...#.#......#...................#.........#..#.#......#..#.........................##....#. +..............#..........##......#.##...#...#.#................#...#..#.......#.#.....#........#...###..##.........#..##.........#. +........##...........................##.......#.#..................#........#.......#.#........#.........................##....#... +..#.#...........#.......................#.#.....#....#.....#...............####...#..............#...#....................#.#...... +.......#...#....#.#.......#####...##.....#.#.......#....#.#........#................................#.##..........##....#..#....... +.........#.....#................##.#..................#.....................#...#................#.###.#.......###....#............ +............#.#....#........#....#..................#...##.............#............#.......#.....#..#............##............... +....#.....#..........#..............#...#...#........##.....#.#....#....#........##.............................#.#.......#........ +..#..#.#.......#.................#................................#......##.#..#..............#.#................#...#.#........... +.....#.....#........................#..#................#......#.......#.........###.#.#.........#.........#.....#.......#......... +.......#.......................................#.......#...............#.#..###...#.#.##.......#...........#.#.....#.##........#... +......##.........#.................................#.........#........##.#................#.#...#.............#...#..#........#.... +......#.....#.#.......#...........#..#...........#.........#..#.#.......#.........##.....#....#.#...............#...#...#....#...#. +..#...#.#....#....#..............................#..#...#.......#.#.#..##..................#...............#......#..###..#.#...... +.....#...#..#......#.....##...............#..........#..#.#####.......#...........#...................#.....#...#.........#..#.#... +.................#.......#..................#........#.......##...##.#....#.#.............#.............#....#....#................ +...........####..#.....#....#.............#.......#...#..#.....#.............#...#....#.............#.#....#.#.............#....... +...#..#..#...#...#.#.....#.......................#....#..###.###.....#.........#....................#....#..#............#.....#... +.#.##....##...#......#.#.....#......................#.##..................#........#..#................#.#.......#.............#... +....##........#.......#..#..#............#..#..#..#...#......###..#..#..#...##...............................#.#........#......#.#. +..#..#..........#..........#..#.#.............#.....#...........#.##.......#............................#...........#...#.......... +..#.#..#...#....#.....#.....#...#................#.....#.....#....#..#...#..#....#....#.....................#....#................. +.......#........#...#.............#.................#...#.#.....#.#....#..........#......................#..#............#......... +....#........#........#..............#.........................#...................#..........#.........#..#.........#............. +................#........#.........#............................#.#.............#..##.......#......#..#.................#......#.#. +..#.....#.........#...#..#.#.........................#...#...#...........#.....#...........#........#.............#.....#........#. +....#...#....#......#....#...#..#.................#...##.....#.#............................##...#...#..##.#.....................#. +...#..##...............#............................#...........#......#.#.....#............#........#.##................#......... +................#..#.............#..#..............#.#....#...#.#...#...#.#.##.............................#..#...........#........ +.......#.......#....###............#.#.#.....................#.#..#....#.................##.....#.#..........##..#......#.......... +.......#..........##.#.......#.##...#...............##.....#..........#................#............#...#........#........#........ +...###.#.............................#.....#.#............##..#...#.....###..........#...............................#.....#....#.. +....###.#...#.......#.##........#......#..##.#..........#.#...#.#....#.#..............##....#..#...#...........#...#.#..#.......... +.....#....#.#..##.....#..........#..#...##..............#.......#.......#.............#..#.....#.......#.....#...##...###.......#.. +........##...#...##..#.#.....#..........................#.#.#..#..#...................#....#....#..#....#..........#....##......... +...........##.....#...#........##..#........#....#..........#..#...............................................#......#.#.......#.. +...#..##.........##....#...........##...#.......##.........#........#...........#........#.#.##...........#....#.....###...#....... +...#...#........................#..#...#..#........................................#......#..#...#.#....#...........#.............. +...#..#.......#..#......##...................#...............#.....#.#.............#.....#.........#.#..##.....#..........#..#..... +....###....#..#.....#.#........#.##.......##...#...............#...............###.###.#...#............##.....#.................#. +....#...#.........#.##............#.....#........#............................................##.#......#..##.........#....###..#.. +............#...##..#..........#........#.......#.#..........................#..#.#.......#......#.......................##.#..#... +....#......#....#....#..#.....#........#......#....#..#.#..............................#..#....#............#....#................. +..#.............#...#......#...#.....................#.##...............................##...#.......#........................#.##. +....#....##........#..............#....#.......#.....................................#........#........#...##..........#........... +....#.#.##..#..#....................#.................#.##.............#....#....#.............###...#...#..##....#.....##......... +.............#.......#...............#........#.#.....#..#.#................#.....#..##.....#....#...............#....#......#...#. +................................................................................................................................... diff --git a/2023/src/bin/day_21.rs b/2023/src/bin/day_21.rs index b3a610b..d5126bd 100644 --- a/2023/src/bin/day_21.rs +++ b/2023/src/bin/day_21.rs @@ -1,19 +1,165 @@ -use nom::IResult; -use std::fs; +use nom::{ + branch::alt, + character::complete::{char, line_ending}, + combinator::{map, value}, + multi::{many1, separated_list1}, + IResult, +}; +use std::{collections::BTreeSet, fs, mem}; fn main() -> Result<(), Box> { - let input = fs::read_to_string("inputs/day_2.txt")?; - let parsed = Example::parser(&input).unwrap().1; - dbg!(&parsed); + let input = fs::read_to_string("inputs/day_21.txt")?; + let mut walled_garden = WalledGarden::parser(&input).unwrap().1; + for _ in 0..64 { + walled_garden = walled_garden.next(); + } + dbg!(&walled_garden.count_walkable()); + + let mut open_garden = OpenGarden::parser(&input).unwrap().1; + let open_iters = 26501365; + for i in 0..open_iters { + if i % 100000 == 0 { + println!("{}", i as f32 / open_iters as f32); + } + open_garden.next_mut(); + } + dbg!(&open_garden.count_walkable()); Ok(()) } #[derive(Debug)] -struct Example; +struct WalledGarden(Vec>); + +#[derive(Debug, Clone, Copy, PartialEq, Eq)] +enum WalledGardenState { + Empty, + Walkable, + Rock, +} + +impl WalledGarden { + fn parser(input: &str) -> IResult<&str, Self> { + map( + separated_list1(line_ending, many1(WalledGardenState::parser)), + WalledGarden, + )(input) + } + + fn next(&self) -> WalledGarden { + WalledGarden( + (0..self.0.len() as isize) + .map(|y| { + (0..self.0[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(), + ) + } + + 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.0.len() || x >= self.0[y].len() { + WalledGardenState::Rock + } else { + self.0[y][x] + } + } + } + + fn count_walkable(&self) -> usize { + self.0 + .iter() + .flat_map(|row| row.iter()) + .filter(|s| **s == WalledGardenState::Walkable) + .count() + } +} + +impl WalledGardenState { + fn parser(input: &str) -> IResult<&str, Self> { + alt(( + value(WalledGardenState::Empty, char('.')), + value(WalledGardenState::Walkable, char('S')), + value(WalledGardenState::Rock, char('#')), + ))(input) + } +} + +#[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)) + } -impl Example { - fn parser(_input: &str) -> IResult<&str, Self> { - todo!() + fn count_walkable(&self) -> usize { + self.walkable.len() } } -- cgit v1.2.3