Day 21 - Part 1

2 files changed, 286 insertions, 9 deletions

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<dyn std::error::Error>> {
-    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<Vec<WalledGardenState>>);
+
+#[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::<Vec<WalledGardenState>>()
+                })
+                .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()
     }
 }