day 23

4 files changed, 259 insertions, 0 deletions

diff --git a/benches/2022.rs b/benches/2022.rs
index e4c40d5..6eb6c5e 100644
--- a/benches/2022.rs
+++ b/benches/2022.rs
@@ -43,6 +43,8 @@ mod day19;
 mod day20;
 #[path = "../src/bin/2022/day21.rs"]
 mod day21;
+#[path = "../src/bin/2022/day23.rs"]
+mod day23;
 // NEXT MOD
 
 day!(2022, 1, day1);
@@ -66,6 +68,7 @@ day!(2022, 18, day18);
 day!(2022, 19, day19);
 day!(2022, 20, day20);
 day!(2022, 21, day21);
+day!(2022, 23, day23);
 // NEXT DAY
 
 fn bench_2022(c: &mut criterion::Criterion) {
@@ -92,6 +95,7 @@ fn bench_2022(c: &mut criterion::Criterion) {
             day_combined!(2022, 19, day19);
             day_combined!(2022, 20, day20);
             day_combined!(2022, 21, day21);
+            day_combined!(2022, 23, day23);
             // NEXT DAY COMBINED
         })
     });
@@ -121,5 +125,6 @@ criterion::criterion_main!(
     bench_2022day19,
     bench_2022day20,
     bench_2022day21,
+    bench_2022day23,
     // NEXT GROUP
 );
diff --git a/data/2022/23.txt b/data/2022/23.txt
new file mode 100644
index 0000000..44cae66
--- /dev/null
+++ b/data/2022/23.txt
@@ -0,0 +1,75 @@
+..###.#####....####.......###.####.#.....##..#.##.....#.##..#.#.........#.#
+.##...#.##...#.##.######.######.#######.#####.#..##...#..#....#.#.#.#...#..
+#.#.#......#.#..#...#..###..###.#####..#####.#.....##.#.#...##.#.###..#..##
+#..##...#####..##...#.##.#.##..##..#...#.###.###..##..####.####.#..#...##..
+#.#...#..#.#####..#####..##.##...#....#.###.....##.#..###....#.#.##..#####.
+#.#..#.#.#..#....#...#..##.#.##...#####.#..###..#.#.#.##...#.##.#.##..#..#.
+#.####..#...####..........##.#.#....#.#.#...###.#......#.######.#..##.###..
+######...#.#.######.........#.##..####.##..#.#.##....##.#.##.#.#..##.##...#
+.##.#.#.###..#.#.##.#..###..##..##.#.###...#..###..#..###.####...###.##.#..
+#.#..#.....##.#.#..##...##..####.####...##..#....##.##.#....#.#..#.#.#..###
+..#.###..#..######.##..#.#..#.#..#.#####.##.####...##.#....#.####....##.##.
+.......#.###..#.##.#.##....#....#.#...##....####..#.#.#...###.##..#.#.#.###
+.####.####..#..##...##...##.####.#.#.#.#.####..##..###.##...##.##....##..#.
+###..##.###..###...###....###....####...#..#######....#.#.#.#....###..##..#
+##.###..######....#.##..####..#...##..#.#...#..#..#.#.#.#..#.###.###.######
+#....#.#....#.#...####...#.#..##...##.#..#..#.#############....#.###....#..
+#..##.#######.#..###...##...#...####.#.####.....#.....#...##.#.####.##.#.##
+#.#.#..###.######.#.###.#.#####.........##....###.#####..###.#.####.#..###.
+####.#.#..#.####....#######...###.#.#####.#..#.....###.#.###..#.#..###..###
+##..#.#..#.....###.####..###.#...##.#....#..#..#.##....#..#.#...#.#.###..#.
+########..#.....##.##.####..#####....##.#.####.###.....#.......###.##....#.
+#..#.#######..#...###..#.###..###...##..#.###.##..###..#......##.###..##..#
+##..###.#..#.###...##..##.#.#...#.###.##.###.#..#..#...###..#.#####..##....
+##.#.#...#.#..#.#.###....#.#.#.#..#..#.###..#..#.#..##.#####.#..##.######..
+##..#####..........##.##...#.....#..##.#####..##.##.#..#..#####....##...###
+#..###.#.##.##..##...######..#.###..#.#.#..###.###.####.##.##.#...##..####.
+#.###..###..##.#####..####.....##.#.....#..#.#...#..####.#.######.##.#.#..#
+.##....#.#.##...#.#.#...##..#.....#...##..##..####.#..####.##.#.#.#..#.###.
+########..#.#.#...#...##...##....##..#.....#.......##..#.#######.##.#....##
+.#..#...##.#.##..##.#..#..#.#####.#.#.#..#.....##.##.....##.#.##.##.#.#.###
+#..####.##.###..#...#..#.##.#########.#######...#...#..##..#.....###..#..##
+##....###..#.#....##...##.####.######..####....###....########..##...###..#
+.##...##.#.#.##..###.##.###..#.#..#......#######..#..##....#....###.##..#..
+##..###...###..#.###.#.##.###.#...#.#.#.####.#.####..#.#..###..#####...####
+#####...######.#.#..##.#.###.#.#.#...###......#.#..##..#..##...##.#########
+#..#.##.....#.#####.##.....#.#..#.###.#..##.##..##..##..##..#.#..#..##.####
+..###.#...#.##...##.#.....#.#####..#.#..#...#.####...#.#####.#######..#.###
+..#.##..#.#..#.###.##..#...#.#....##.....#..#.#...#.##..###.###.##..###..#.
+..#.#.#..#....#.#..##..#......#..#...#####.##.....#.##..##.#####.#.#...#...
+.#..#.....########......##.####..#..#...##.#.###...#.#...##..#####.#..##...
+#..#.#.##.#......##.#......#..####.###....#.#.##..##.....#.#.##.#####..##.#
+...#...###...####..#.#.#......#.#..#..##.##..###.#...#.###..#..#...###.###.
+##.##.#.........#..#..#....#..#......##.#.######.#..#.#...##.#.##..#..#..#.
+.#.##..####.#..##.##....#....###...##..#.#..#.#.##.####...##..#..####....#.
+.....##.#..##.#.###.....####..###.##.###.....##..##...#.#..#.##..#.##.#.#.#
+##.##.#.#..........#..#.####.#..##.#..#.#.###....###.###.#.##.###.#.....#..
+#..#.#.##.##..##.###..###..#.#..#..##.....#......#####.#..###.#.#.....####.
+.##....###..##...#..#.######.####..#.##....#..##.#..####..##....#.....#.##.
+..#.#.##....#...#.#..#.....#...###.#.#.#####...####.###.##...###.###.#.##..
+#..###.#...##.#.#.#.#..#.#..#.##...#######....#.####.####.##.#######..#####
+..#..#.####...#....#...#......#...#..##.#...#...#######..#..#.#####.###..##
+.#.#.###...##.###....#.....####.##.####...#...........###..##...####.#..##.
+.###.####.#..#....###.#.##.#.#####..#.#######.#..##.#.###...#.#..####.#.#..
+..###.#....###.#.....###.#####.#.##.#..###.####.....#..#..#..##.....##.#.##
+##.##.##...#....##..###.##.#...#......#.....##.#....#.#...##..##...#..####.
+.###.....#....##..#####.##..#.#.....#..###..#####.#.#...##..##....#.###.#..
+.##..####..#....##.#####.#.#..#.#.#.##.#..#.#....###.##.###..#....######.#.
+#.###..#...##.##...####..##....#.##..###.....#.....#..##.#...###..###.....#
+..#.#.##...##.##.##..#.#.##.##...##..#.###.#...######.....#.....#.....#.##.
+#.#.#.##.#.#.##.###...####...####..#.....###.#..###.....#..##.#...#.###..##
+#..###.##.#####..#.##...#..###.#.#.#.#....##...###.#..#####.#......##..#.#.
+##.#.##...##.#####...#...#.#...#..##.##.#...#.###..##...##..##.#..##.#.###.
+....####....##..#....##.#...##.#.....##.####.#..#......#.##.##....#.#..#.##
+#.#.#####.##...#..#.#....#.####..#####....#.###..######..##....####..#.####
+.##.#...##..####.#....##..##....#....##.#.#....#....#.##......##....#...#.#
+####..#..#.#.#.#.#..###.###.##..##..#..#.####...##.#..####.........#..#.#..
+.##...#..###.#.#.#.#.###.#.#.#########........###.#.#..#.....####..#..#.#.#
+##..###..#.##......#.#.....#....#....#..#####.#.####..###.#.###....#.##.#..
+#.#.#.##...#.....#.#..###.#..######.#..##.#.###..#.####..###.#....##.####..
+.##...#..#..###.###.........##....##...#.###..#..#.#.#.#.#.###......##..##.
+.##.##.##..#.######..#.##..##.#...#.##.#..###.#....#..#####.##..#..#.###...
+..####.##.#..#..##..##...####.######.##.#.....##.#....#....###.##.##....###
+.##......#.....#.#..#.#.##....#.#.#.####...#...##...##...#.##.#.#.#.##...##
+.##.#######..#.#..#.#..##..#.#....##...#####...##..#.......##...##..##..#.#
+#...#.#..#.###.#.##....##..#...#.#..##.###.......##.#.....######..#########
diff --git a/src/bin/2022/day23.rs b/src/bin/2022/day23.rs
new file mode 100644
index 0000000..d469095
--- /dev/null
+++ b/src/bin/2022/day23.rs
@@ -0,0 +1,177 @@
+#![allow(dead_code)]
+#![allow(unused_variables)]
+
+use advent_of_code::prelude::*;
+
+fn print_elves(elves: &HashSet<(IRow, ICol)>) {
+    let min_row = elves.iter().map(|elf| elf.0).min().unwrap();
+    let max_row = elves.iter().map(|elf| elf.0).max().unwrap();
+    let min_col = elves.iter().map(|elf| elf.1).min().unwrap();
+    let max_col = elves.iter().map(|elf| elf.1).max().unwrap();
+    for row in (min_row.0..=max_row.0).map(IRow) {
+        for col in (min_col.0..=max_col.0).map(ICol) {
+            if elves.contains(&(row, col)) {
+                print!("#");
+            } else {
+                print!(".")
+            }
+        }
+        println!()
+    }
+}
+
+pub fn parse(fh: File) -> Result<HashSet<(IRow, ICol)>> {
+    let mut elves = HashSet::new();
+    for (row, line) in parse::raw_lines(fh).enumerate() {
+        for (col, c) in line.chars().enumerate() {
+            match c {
+                '#' => {
+                    elves.insert((IRow(row as isize), ICol(col as isize)));
+                }
+                '.' => {}
+                _ => panic!("unexpected char {}", c),
+            }
+        }
+    }
+    Ok(elves)
+}
+
+fn neighbors(elf: (IRow, ICol)) -> Vec<(IRow, ICol)> {
+    vec![
+        (elf.0 - 1, elf.1 - 1),
+        (elf.0 - 1, elf.1),
+        (elf.0 - 1, elf.1 + 1),
+        (elf.0, elf.1 - 1),
+        (elf.0, elf.1 + 1),
+        (elf.0 + 1, elf.1 - 1),
+        (elf.0 + 1, elf.1),
+        (elf.0 + 1, elf.1 + 1),
+    ]
+}
+
+pub fn part1(mut elves: HashSet<(IRow, ICol)>) -> Result<isize> {
+    let mut possible: VecDeque<(IRow, ICol)> = VecDeque::new();
+    possible.push_back((IRow(-1), ICol(0)));
+    possible.push_back((IRow(1), ICol(0)));
+    possible.push_back((IRow(0), ICol(-1)));
+    possible.push_back((IRow(0), ICol(1)));
+    for _ in 0..10 {
+        let mut moves: HashSet<((IRow, ICol), (IRow, ICol))> = HashSet::new();
+        for elf in &elves {
+            if neighbors(*elf)
+                .iter()
+                .all(|neighbor| !elves.contains(neighbor))
+            {
+                continue;
+            }
+            for diff in &possible {
+                let occupied = if diff.0 == IRow(0) {
+                    elves.contains(&(elf.0 - 1, elf.1 + diff.1 .0))
+                        || elves.contains(&(elf.0, elf.1 + diff.1 .0))
+                        || elves.contains(&(elf.0 + 1, elf.1 + diff.1 .0))
+                } else {
+                    elves.contains(&(elf.0 + diff.0 .0, elf.1 - 1))
+                        || elves.contains(&(elf.0 + diff.0 .0, elf.1))
+                        || elves.contains(&(elf.0 + diff.0 .0, elf.1 + 1))
+                };
+                if !occupied {
+                    moves.insert((
+                        *elf,
+                        (elf.0 + diff.0 .0, elf.1 + diff.1 .0),
+                    ));
+                    break;
+                }
+            }
+        }
+        let mut targets: HashMap<(IRow, ICol), usize> = HashMap::new();
+        for (from, to) in &moves {
+            *targets.entry(*to).or_default() += 1;
+        }
+        for (from, to) in &moves {
+            if targets.get(to).copied().unwrap_or(0) == 1 {
+                elves.remove(from);
+                elves.insert(*to);
+            }
+        }
+
+        let first = possible.pop_front().unwrap();
+        possible.push_back(first);
+    }
+    let min_row = elves.iter().map(|elf| elf.0).min().unwrap();
+    let max_row = elves.iter().map(|elf| elf.0).max().unwrap();
+    let min_col = elves.iter().map(|elf| elf.1).min().unwrap();
+    let max_col = elves.iter().map(|elf| elf.1).max().unwrap();
+    let area = (max_row.0 - min_row.0 + 1) * (max_col.0 - min_col.0 + 1);
+    Ok(area - elves.len() as isize)
+}
+
+pub fn part2(mut elves: HashSet<(IRow, ICol)>) -> Result<usize> {
+    let mut possible: VecDeque<(IRow, ICol)> = VecDeque::new();
+    possible.push_back((IRow(-1), ICol(0)));
+    possible.push_back((IRow(1), ICol(0)));
+    possible.push_back((IRow(0), ICol(-1)));
+    possible.push_back((IRow(0), ICol(1)));
+    let mut round = 0;
+    loop {
+        round += 1;
+        let mut moves: HashSet<((IRow, ICol), (IRow, ICol))> = HashSet::new();
+        for elf in &elves {
+            if neighbors(*elf)
+                .iter()
+                .all(|neighbor| !elves.contains(neighbor))
+            {
+                continue;
+            }
+            for diff in &possible {
+                let occupied = if diff.0 == IRow(0) {
+                    elves.contains(&(elf.0 - 1, elf.1 + diff.1 .0))
+                        || elves.contains(&(elf.0, elf.1 + diff.1 .0))
+                        || elves.contains(&(elf.0 + 1, elf.1 + diff.1 .0))
+                } else {
+                    elves.contains(&(elf.0 + diff.0 .0, elf.1 - 1))
+                        || elves.contains(&(elf.0 + diff.0 .0, elf.1))
+                        || elves.contains(&(elf.0 + diff.0 .0, elf.1 + 1))
+                };
+                if !occupied {
+                    moves.insert((
+                        *elf,
+                        (elf.0 + diff.0 .0, elf.1 + diff.1 .0),
+                    ));
+                    break;
+                }
+            }
+        }
+        let mut targets: HashMap<(IRow, ICol), usize> = HashMap::new();
+        for (from, to) in &moves {
+            *targets.entry(*to).or_default() += 1;
+        }
+        let mut moved = false;
+        for (from, to) in &moves {
+            if targets.get(to).copied().unwrap_or(0) == 1 {
+                elves.remove(from);
+                elves.insert(*to);
+                moved = true;
+            }
+        }
+        if !moved {
+            break;
+        }
+
+        let first = possible.pop_front().unwrap();
+        possible.push_back(first);
+    }
+
+    Ok(round)
+}
+
+#[test]
+fn test() {
+    assert_eq!(
+        part1(parse(parse::data(2022, 23).unwrap()).unwrap()).unwrap(),
+        0
+    );
+    assert_eq!(
+        part2(parse(parse::data(2022, 23).unwrap()).unwrap()).unwrap(),
+        0
+    );
+}
diff --git a/src/bin/2022/main.rs b/src/bin/2022/main.rs
index 25e7c34..14aac9b 100644
--- a/src/bin/2022/main.rs
+++ b/src/bin/2022/main.rs
@@ -32,6 +32,7 @@ mod day18;
 mod day19;
 mod day20;
 mod day21;
+mod day23;
 // NEXT MOD
 
 #[paw::main]
@@ -59,6 +60,7 @@ fn main(opt: Opt) -> Result<()> {
         19 => advent_of_code::day!(2022, opt.day, opt.puzzle, day19),
         20 => advent_of_code::day!(2022, opt.day, opt.puzzle, day20),
         21 => advent_of_code::day!(2022, opt.day, opt.puzzle, day21),
+        23 => advent_of_code::day!(2022, opt.day, opt.puzzle, day23),
         // NEXT PART
         _ => panic!("unknown day {}", opt.day),
     }