Day 23 (incomplete)

3 files changed, 259 insertions, 0 deletions

diff --git a/2022/inputs/day_23.txt b/2022/inputs/day_23.txt
new file mode 100644
index 0000000..f2ffcef
--- /dev/null
+++ b/2022/inputs/day_23.txt
@@ -0,0 +1,74 @@
+......#.##.###.###..##...#.###..###....##....#.#.#.#...#.#..#####.#..#.#..
+#######.##...##.##..#..##.#....#.###.##...#...##......######...#...###..#.
+...#.#.##.#.##.#.#..#..#.#.##.######...###.....#.#.##..##..##.#..####..###
+.##.#.##.#.#.#..#.##.###..........###..#.##.....#..#####.#....#.##...#..##
+#.#...###...#.##.....#####.#.#.###..##.#...#..#.#.###.##......#.###.#####.
+....##....#####..##.#....#.##.#.##....##.####..#.##...#..##..#.##....#.##.
+.......##.#..#..##...####.##.#..###.....##.##...#.....###.###...#....#....
+.####.##.##..#...##.##...###..####..####....#####.###.####....###.###.#...
+####..##.#..##.###...####..#####....#.####.............##.###.......#....#
+..........#...##....#.#####..#....##.###...####...##..###.##.#.##......###
+.........#.#.##.##..#.#.####.#.##.#.##..#...##..##...#.#####...##.#..#..#.
+##..#...#..#.###.###..#....##.#......###...#.#...#.#.##...#####..##.###...
+.##.##......#.####..#..#...#.#..##..##..#..##..###.#.##.....#..##.###.#.#.
+.############...#.#.##..##...........#.######.#..####.####...###..#.#.#.#.
+#...##..##.....###.#...##..##..##.....#...#..###..###..####.#.#..#.##..###
+#...##.#.#..##.###.#.....####.#.#...#....#####.##...#.#.###....#.#.#.#..##
+##.###..####.....#####..###.##..###..#####.#.#####.#.#...#.#...###.###.###
+####...#.####..#.#.##..#..#..##..##.#.........#.#..##.####.###......#...##
+#....##.####.##.#.#.#.##.##..##.##.#.#.#......#.####.##..#..##..#..##..#..
+..##...##.#.###.##..##.#..##.......#.####.#...#...#.#...###...#..####..###
+##.#..####..#.#.##.##..#.##..##.......####...######.######...#....#.......
+##....##.####..###.....####..###.#..#.######.##..###.#..##...#.###..#.###.
+.####.#.###########..###........#.#.##.##.###...#.##.#..###.#.#.....#####.
+##.#.###..##....###...##.##....##.#.#..#.###.##..#.#...###...####.##..###.
+.#.#.#.###.#.###.....#..#.#######.......#.#.#.#######..####.#..###.#...#.#
+#..##..##.#.#.#.##....#.#.###.#..##.##..##.####.#.#.#.........##.#.#....##
+###..#.#...#...##.###...#..#.#.#.#.###..#.###...#.#.###.######.##.##....##
+#.#....#.###.#.##..#...#..###.####..#.##..#.#.#.##...###...#.##..#.#.#####
+.....#.#.....#.###.#.##.#...#....##.#.#.#..#.#####.##..#.#..##.#.#####..##
+...#......#.###.###...####..####...##...####.###.##...#...#######..#..##..
+##.....#...####.#.#...#...#..##..#...#####.##.#..#....##.###.##....#.#.###
+#.####.#..##.#####.##..###.#..........###..#...#.#..##.#..####.....#......
+....#.###.....#...#.#.##.##...####..##.#.##.#...###.#####.#..#.##.#.....##
+#.###.#....#..#.###..#..##..######.##.#.#.###.#.#.##..##...#.##..#..##...#
+###..####.##...#..#.##...#...#...###.###..###.#...#..##.#.#.###..##.#..##.
+#.##.###..#....#....#..#.##.......###.###.#.###.##......#####..#...###.###
+#.#.#..#..#.#######.##..#....##....#.###.##...##...#..#.####.#.##..#....#.
+##..##.###.#..#.#..#.#.#.#..#.##.###.#.##..##...###########..###.#.#..###.
+..#..##..##########...#########.#.#.#......###......#.....#....##..######.
+.#.#...#..#..#....#.#.#...##..##.##.#....##....#..#...##..#.##...#...##.#.
+##..#.#.#.####...##.####..###....#.#.##.#.#...#.##.#...######.##..#####.#.
+#.#..###...#..##..###.#.#.#..#..#.#.#...#.##.#....#...##.###.##.#..##.#..#
+#...#..##..#...#......####....#.#.##..#.##.###..##.##.#..#.#####.##.#.####
+.####....##.#..####..##.#..#.#.######.####..##.......###...#####.....#....
+..#..##.#.#..#####...##.#....####...##.#.#.###.#.##.#..#.###..###.##..##..
+###..###.##.#.......##...##..#..#.#..#.#.##..#.####.#.##..#.##.###.##..###
+#.....######.#...##...#.#.#####..#.######.....#..#..###..#.###....###..###
+#...##....###..#.#.##..#.###.##..####.#..#...#.#....##.#.####...#####.#.#.
+#.#.#...##.#######....#..###..####.#.#####....###.##.#...#.#####.#...###.#
+####.#......#..#.#.##.####....#.#.##.#...#...##..#........###.###.##.#...#
+#####..##..##.#####....#.#.#..#.##......##.##...#.#...#.####.#.##.#####.##
+.#.#.####..##...#...#..##..#.#..###...#...#######..##.#####..#..#..#....##
+###.....###..##.#..#####.#..#...###.##.##.###..#....#.....##.#.#.###...###
+..#...######..##.#.#.#.########.###....#...#.##...#..##.#.##..###...#.###.
+##..#....##..########.###..#..#.##..#######.#.#..#.#.##..##.#...##....#..#
+#.##..#....###...#.##..#.#.#..#.....#...####....####..##..#..#..#..#.##.#.
+##...#...#.#..#...#..####.#...##..#..###.##.....#.##.##..#.##.##.#..#.####
+####....####.##...#.##..#...##...#.##.####.....###.#.#.###...#.##.##.##.##
+#...#.#....#.#.#####.##.#.##.#...#.##.#...#...#.##..##...#...#..#...#..##.
+#..####.#..#...##.#.####..###...##.###.#######...#.....#..#.#####..##..##.
+##.#...##..###########.....##.##..#...#.####....#.#....####.##.#.###.#.##.
+#...#..#.#####.#....#.##..###...#..#...#######.#...##..#..#.###..#.##.#..#
+###.##...#.####....##.########......#...#...####.#..####.##.##..##..##....
+##..###..#####...###..#.#...#..###....###.#..###....#.......#.###.#.#.#.##
+........#.#....#..#.#...#...#####.####.....###...##.#.#...#.#..###...##..#
+#.....###.####....###.#.##.##.#.##..#.#...##..##.....#.#..#.###.##.#......
+..#...##.#..###.###..#..##...#.#..#.#####.##..##..#..#.....#####.######..#
+...#...##.#.#......###.####..#.##...#..#....##.#.####..#.#..#...#.##.#..#.
+.#.....##.#..####.###.#.#...#..#...#.##.#.#.#.####.##...#..###..####.#####
+..##..##.#.##......#.#.####.#####.#.##..###.##........#....#..#.#..##.##..
+..##..##...#..###...#..#.#...#.....###...##..###.###..##.#.#....#..#..##..
+##.#..#.#.###....###..##...###.##.#..#####..##..##..#.......##..#.###..#..
+#..#.###.###.##.###.###....#..#..##.##.#.#.##.#.#....##.#..#.#.###.##.###.
+.##.#..#.###....##.####.##........#..####..#..#.....#.##..#.#..#..###.#..#
diff --git a/2022/inputs/day_23_test.txt b/2022/inputs/day_23_test.txt
new file mode 100644
index 0000000..c84aa7c
--- /dev/null
+++ b/2022/inputs/day_23_test.txt
@@ -0,0 +1,12 @@
+..............
+..............
+.......#......
+.....###.#....
+...#...#.#....
+....#...##....
+...#.###......
+...##.#.##....
+....#..#......
+..............
+..............
+..............
diff --git a/2022/src/bin/day_23.rs b/2022/src/bin/day_23.rs
new file mode 100644
index 0000000..5f58dea
--- /dev/null
+++ b/2022/src/bin/day_23.rs
@@ -0,0 +1,173 @@
+use nom::{
+    branch::alt,
+    bytes::complete::tag,
+    character::complete::line_ending,
+    combinator::{map, value},
+    multi::{many1, separated_list1},
+    IResult,
+};
+use std::{
+    collections::{BTreeMap, BTreeSet, VecDeque},
+    fs,
+};
+
+fn main() -> Result<(), Box<dyn std::error::Error>> {
+    let input = fs::read_to_string("inputs/day_23_test.txt")?;
+    let mut elves = ElfMap::parser(&input).unwrap().1;
+
+    dbg!(&elves);
+    for _ in 0..10 {
+        elves.process_round();
+        dbg!(&elves);
+    }
+
+    dbg!(elves.count_empty_ground());
+
+    Ok(())
+}
+
+#[derive(Debug, Clone)]
+struct ElfMap {
+    elves: BTreeSet<Point>,
+    check_order: VecDeque<Direction>,
+}
+
+#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord)]
+struct Point {
+    y: i64,
+    x: i64,
+}
+
+#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
+enum Direction {
+    North,
+    South,
+    West,
+    East,
+}
+
+impl ElfMap {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        map(
+            separated_list1(
+                line_ending,
+                map(
+                    many1(alt((value(true, tag("#")), value(false, tag("."))))),
+                    |row| {
+                        row.into_iter()
+                            .enumerate()
+                            .filter_map(|(x, occupied)| occupied.then_some(x as i64))
+                            .collect::<Vec<i64>>()
+                    },
+                ),
+            ),
+            |rows| {
+                let elves = rows
+                    .into_iter()
+                    .enumerate()
+                    .flat_map(|(y, row)| row.into_iter().map(move |x| Point { x, y: y as i64 }))
+                    .collect();
+                ElfMap {
+                    elves,
+                    check_order: [
+                        Direction::North,
+                        Direction::South,
+                        Direction::West,
+                        Direction::East,
+                    ]
+                    .into(),
+                }
+            },
+        )(input)
+    }
+
+    fn process_round(&mut self) {
+        // key is destination!
+        let mut elf_moves: BTreeMap<Point, Point> = BTreeMap::new();
+        let mut conflict_moves: BTreeSet<Point> = BTreeSet::new();
+
+        // phase 1: figure out where each elf wants to move
+        for elf in &self.elves {
+            if let Some(destination) = self.find_elf_move(&elf) {
+                if elf_moves.contains_key(&destination) {
+                    elf_moves.remove(&destination);
+                    conflict_moves.insert(destination);
+                } else if !conflict_moves.contains(&destination) {
+                    elf_moves.insert(destination, elf.clone());
+                }
+            }
+        }
+
+        // phase 2: move the elves
+        for (dest, src) in elf_moves {
+            self.elves.remove(&src);
+            self.elves.insert(dest);
+        }
+
+        let rotate = self
+            .check_order
+            .pop_front()
+            .expect("Where did the directions go?");
+        self.check_order.push_back(rotate);
+    }
+
+    fn find_elf_move(&self, elf: &Point) -> Option<Point> {
+        let all_adjacent = elf.adjacent(None);
+        let any_adjacent_elves = all_adjacent.into_iter().any(|p| self.elves.contains(&p));
+        if !any_adjacent_elves {
+            None
+        } else {
+            self.check_order
+                .iter()
+                .filter_map(|dir| {
+                    let adjacent = elf.adjacent(Some(*dir));
+                    let any_adjacent_elves = adjacent.iter().any(|p| self.elves.contains(p));
+                    if !any_adjacent_elves {
+                        Some(adjacent[1].clone())
+                    } else {
+                        None
+                    }
+                })
+                .next()
+        }
+    }
+
+    fn count_empty_ground(&self) -> i64 {
+        let mut min_x = 0;
+        let mut min_y = 0;
+        let mut max_x = 0;
+        let mut max_y = 0;
+        for elf in &self.elves {
+            min_x = min_x.min(elf.x);
+            min_y = min_y.min(elf.y);
+            max_x = max_x.max(elf.x);
+            max_y = max_y.max(elf.y);
+        }
+
+        let all_ground = (max_x - min_x + 1) * (max_y - min_y + 1);
+        let covered_ground = self.elves.len() as i64;
+        all_ground - covered_ground
+    }
+}
+
+impl Point {
+    fn adjacent(&self, direction: Option<Direction>) -> Vec<Point> {
+        let (y_range, x_range) = match direction {
+            None => ((-1..=1), (-1..=1)),
+            Some(Direction::North) => ((-1..=-1), (-1..=1)),
+            Some(Direction::South) => ((1..=1), (-1..=1)),
+            Some(Direction::East) => ((-1..=1), (-1..=-1)),
+            Some(Direction::West) => ((-1..=1), (1..=1)),
+        };
+
+        y_range
+            .flat_map(|dy| {
+                x_range.clone().map(move |dx| Point {
+                    x: self.x + dx,
+                    y: self.y + dy,
+                })
+            })
+            .filter(|p| p != self)
+            .collect()
+    }
+}