commit e63ff8ca6ee50f7a36f8f6ccef60c2e14736888d
parent 7b3b17c330c904af612faf4bd8c714aba92d0c8f
Author: Shimmy Xu <shimmy.xu@shimmy1996.com>
Date: Fri, 23 Dec 2022 18:38:41 -0500
Add 2022 day 23
Diffstat:
3 files changed, 229 insertions(+), 0 deletions(-)
diff --git a/2022/day23/Cargo.toml b/2022/day23/Cargo.toml
@@ -0,0 +1,8 @@
+[package]
+name = "day23"
+version = "0.1.0"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
diff --git a/2022/day23/input.txt b/2022/day23/input.txt
@@ -0,0 +1,74 @@
+#.#######..#...#....#.##..###..#..###..#.#..###.#.#...######..#..#.#.###..
+....#.####...##.#...#..#...#.###..#.###...#..#.##.#....#...#########...#..
+#...#...###.####...#..###.##.##....######..###.###.##...##..#.#.#.##...###
+##..###.#....#..#.#..###.#.####...##.#..#.#.#...#.###...#####.....####.#.#
+.#####...#.#.#.....#.###.......#.#...#####...#..#.###.###.#.#....#####.#..
+.#...###..#.#..#..#...####.#..###.#.####..###.#.#....#..#..#..##.##...#.#.
+.##...#.##..#.##.#.##..##...#..#...####..#.#..##.#####.#..#....##...#....#
+.###.#.#.#..###..#.#..##.####...#..#..#.#.########.#...#....##..##.#..###.
+..#..#.##.##..####......#..######..####.##..#..#....######..##.#...#...###
+.#....##.###.....#.#...#.##....#.#.#...##.#..#.##.#...##..#.#######..###..
+.#.##..#####..#######.....####.....##..#..###.####.#.#..###.##.#..####.#..
+###..##..######..#...##.#....#..#..###...##.#..####.##.#....##..#..####.#.
+###....###.##.#...####.#.#....###...#.#.##.#..###.#.#.##...#..###..#..#...
+###.#.....#....#.##....##.###....###.####...#.#....#..#...#.#..###.#..#.#.
+#.#.#..#...#####.####.##...#...###..###.#.##.#####.###.#####.#.##......###
+##.....#.####.#...#...##.####.#.##.###.#..#..##.###..#..#..###.##..##..###
+###..####.#.#...#..#..#.#.#..#...#.#.#..#.#.#.#.#..###.#####.#.#####....#.
+##.##.###..###.###..##.##.##..#..#.########.#.##........#...##.#...#......
+#.....#.#..######....##.....#.#.######.#...####.#.###.#...###.##..#.#.....
+#####.##......#.#####..##..#....##.#..##.....####.###.##.#####....#...#...
+..##..#..#.##.##.##.#..#.#...#..##.#...###...#.#######..#####.###...#....#
+##.###.##.##.#......##..####.#..#.######..#...#.#....##.#....####.#...#.##
+##.##....#.##....#.......###..##.#....#...####.#.#...###....######..###...
+...##.#..#.#...###..#..###.##..#.#...###.###.#.####..##.####.#....###.##..
+#.###.#.##.##..###..####.#.#######..###.#.#..##.####.#.##.....#.###....##.
+.#####.#..##..#.#...####.#......##..##..#.#.##.#.####..#.###...##.##.##...
+#.#####...##......####....####.#..#..#..#.##...##...#..#.#..#.#....####...
+##.######.#.#.#####.....#.####.#.#.#...##.#####....#...#..#.##...##.####.#
+#.#.##..#..##.##....######.####.###.##..####.##....##.#..##..#...#####...#
+.......##...#.##.##.........##.#.#.#.#.##.....###..###..###.#####.######.#
+#...#...#.####..#..###..#.#..#..##..##.#...#...####.#####.#.#.#.#......##.
+###...##.#.########.#.###.##.#####..#####...####.#.#..#.#.#....#.#.#.#.#..
+####.###.....#...#.#.#..#.####....##.........###.....######.#..###########
+.##...#.####..###.#...#...#....##..#..#####.##.##..##.#..###.#..##...#....
+.###..###.#.#..#.#..#.##..##..#...#..#.#.#.###....####..#.####..#.....####
+...##..###..#..#..##..##..##..#.#####..##..##.#..##.......#.#.##...##....#
+..#..#...#.#..####........#..##.#.....##..#.#####.#.##.#..#.####.#########
+......##.#.#.##.########.##.#.##.#....#..#..#...#.##.#.#..##..#.#.####..##
+...#..####.#...###...#...#..#####..#.#.#######...###...##.#..##..##.....#.
+#.##.#..####..###.#.##.##...##..#####.##.#.#.#.###....####...#....###.##.#
+#.#....#...#.##.#...#.....######.#..###....#.###.##...#.###.##..#..#..##..
+#.####.###.##....##.###.#.##...##...#.#.......##.....#.##..####.#.......##
+..##...######.##..#....###...#.###.##.####..#....#.##...#.###..#...###.##.
+.#....#..#..###.#####......##....####..##.####.###.#..##...####...#....#..
+#.##.##..##.#...#.......##########.###...##.#..#....#...######..#...##....
+.#...#..###..#......#..##.#.#.##.##.##...##.....##.#..#..##.####.####.#.##
+####.###.#.#.#.#......#####.#######.....###.###.#...#..##..#.######..#..#.
+.#..##.##...#..##.##.##.#...##.###..##.#.#.....###...#.#....#..#.#.##..##.
+###..#.##.#..##..#..#..#...#######.#...#...#####..#..#..##.........###.###
+##.#.#.##.##.#.....##.####.######..###..#..#..##.###.....##..##...###..###
+..#..#.....#.......#.###..#.##.##.##.....###.....#.#.##.##.##..##.##..#..#
+###..#..#.#.#.####.#.#..##..##.#.#.....###..#.....##.##.#....#...#...##..#
+##.###.#..##.#..##..#.#...#..#...##.#.#.#.....###.#.#.#.#.##.#..#..#.#.##.
+#..###....####.#..######.#..##....#..#...#..###.##.##..#....#.##.###.....#
+#.##.##..##...#.#####.###.#.###.##.####...##.....##.#..##..####...###.#.##
+#####..##....##....#.###..#.#.#.###.####.####...####......###...#..#.#.#..
+..###.##..#..#.##.##.#.####..#..##.###.##..####.##.###.##.##......#.#....#
+..#.#..#.##...##########.#..#.#..##.#.#....##.#.#....###........#.#.#.##..
+#######.#.#.#..##.#.#.####.#..######.#.##.#.##.####.#.##.####.##.##...#.##
+.###.#.##...####.....###.#.#..##...#.#..######...........####....#####.#.#
+#.##..##.####.####.##..........###.##.#.###..###..##...#.#.##.####..#..#.#
+#.#..##.###....##..#.#...#.#.#.###.#######....##.......##.#.#..#####.#..#.
+##..##..##..#.....##..###.##......###..#.#.###.#.#....##.####...#.#....#.#
+######..##.#.###....####.##...#####.#..##..##.#...#..##.#.......##....##..
+.####.##.##.#..#.#....####..##.##..#..##.#.#.....#...#...##.#..##.#.#.#.##
+.##.##.#....##.##...#.########..#..###..##.#..####.#.###..##...#.##..#..#.
+#.#.#.#..#....#####.##...#...##.##..##.#..###...######..#.##..###.###..##.
+#...#.##########..###.####..####.##....#.#....#...#.#.##.#...#...##...###.
+....#....#....##...#.#.#..#.##..##.#......##.##.##.#..#......#..#..#.###..
+##..##.#.......###..#.##..#.##.##.#.###.#.#.#####..###.#.#.#.#.#..#.###.#.
+#..##...##...#.....####.##.####...#.####.#.#.#####..##..#..#..###....###..
+##....##.##..####..####...#.##..#.##...#.....##..#..##..##....##..#..##...
+.#..###..#.##.#.#.#..#.#............#...#.#..#.######...##..##.#..#.#.#.##
+.....####.......#..#.#..###.##.####.##.#....#.##..#.##...#.....#..#...#...
diff --git a/2022/day23/src/main.rs b/2022/day23/src/main.rs
@@ -0,0 +1,147 @@
+use std::collections::{HashMap, HashSet};
+
+#[derive(Debug, Clone, Copy)]
+enum Dir {
+ North,
+ South,
+ West,
+ East,
+}
+
+impl Dir {
+ fn next(&self) -> Self {
+ match self {
+ Self::North => Self::South,
+ Self::South => Self::West,
+ Self::West => Self::East,
+ Self::East => Self::North,
+ }
+ }
+
+ fn can_move(
+ &self,
+ elf: &(i32, i32),
+ elves: &HashMap<(i32, i32), (i32, i32)>,
+ ) -> Option<(i32, i32)> {
+ let (t1, t2, t3) = match self {
+ Self::North => (
+ (elf.0 - 1, elf.1 + 1),
+ (elf.0, elf.1 + 1),
+ (elf.0 + 1, elf.1 + 1),
+ ),
+ Self::South => (
+ (elf.0 - 1, elf.1 - 1),
+ (elf.0, elf.1 - 1),
+ (elf.0 + 1, elf.1 - 1),
+ ),
+ Self::West => (
+ (elf.0 - 1, elf.1 - 1),
+ (elf.0 - 1, elf.1),
+ (elf.0 - 1, elf.1 + 1),
+ ),
+ Self::East => (
+ (elf.0 + 1, elf.1 + 1),
+ (elf.0 + 1, elf.1),
+ (elf.0 + 1, elf.1 - 1),
+ ),
+ };
+ if elves.contains_key(&t1) || elves.contains_key(&t2) || elves.contains_key(&t3) {
+ None
+ } else {
+ Some(t2)
+ }
+ }
+}
+
+fn main() {
+ let input = std::fs::read_to_string("input.txt")
+ .unwrap()
+ .trim()
+ .split('\n')
+ .map(|s| s.to_string())
+ .collect::<Vec<String>>();
+ // 4138
+ println!("Part 1: {}", part_1(&input, Some(10)));
+ // 1010
+ println!("Part 2: {}", part_1(&input, None));
+}
+
+fn can_stop(elf: &(i32, i32), elves: &HashMap<(i32, i32), (i32, i32)>) -> bool {
+ for dx in -1..=1 {
+ for dy in -1..=1 {
+ if dx != 0 || dy != 0 {
+ if elves.contains_key(&(elf.0 + dx, elf.1 + dy)) {
+ return false;
+ }
+ }
+ }
+ }
+ true
+}
+
+fn part_1(input: &Vec<String>, round_limit: Option<i32>) -> i32 {
+ let elves_init = {
+ let mut tmp = HashMap::new();
+ for (j, s) in input.iter().enumerate() {
+ for (i, c) in s.chars().enumerate() {
+ if c == '#' {
+ tmp.insert((i as i32, -(j as i32)), (i as i32, -(j as i32)));
+ }
+ }
+ }
+ tmp
+ };
+ let mut elves_curr = elves_init.clone();
+ let mut dir_curr = Dir::North;
+ let mut round = 0;
+ loop {
+ let mut elves_next = HashMap::new();
+ let mut proposed = HashSet::new();
+ for &e in elves_curr.keys() {
+ let mut target = e;
+ if !can_stop(&e, &elves_curr) {
+ for dir in [
+ dir_curr,
+ dir_curr.next(),
+ dir_curr.next().next(),
+ dir_curr.next().next().next(),
+ ] {
+ if let Some(t) = dir.can_move(&e, &elves_curr) {
+ target = t;
+ break;
+ }
+ }
+ }
+ if proposed.contains(&target) {
+ if let Some(&prev) = elves_next.get(&target) {
+ elves_next.remove(&target);
+ elves_next.insert(prev, prev);
+ }
+ elves_next.insert(e, e);
+ } else {
+ elves_next.insert(target, e);
+ }
+ proposed.insert(target);
+ }
+ dir_curr = dir_curr.next();
+ elves_curr = elves_next;
+ round += 1;
+ if elves_curr.iter().all(|(k, v)| k == v) {
+ break;
+ }
+ if let Some(limit) = round_limit {
+ if round >= limit {
+ break;
+ }
+ }
+ }
+ let x_min = elves_curr.keys().map(|(x, _)| x).min().unwrap();
+ let x_max = elves_curr.keys().map(|(x, _)| x).max().unwrap();
+ let y_min = elves_curr.keys().map(|(_, y)| y).min().unwrap();
+ let y_max = elves_curr.keys().map(|(_, y)| y).max().unwrap();
+ if round_limit.is_some() {
+ (x_max - x_min + 1) * (y_max - y_min + 1) - elves_curr.len() as i32
+ } else {
+ round
+ }
+}