Day 23 2022

3 files changed, 119 insertions, 0 deletions

diff --git a/2022/23/a.rs b/2022/23/a.rs
new file mode 100644
index 0000000..906dde7
--- /dev/null
+++ b/2022/23/a.rs
@@ -0,0 +1,24 @@
+use std::cmp::{min, max};
+mod common;
+use common::*;
+
+fn size(elves: &Vec<(i64, i64)>) -> usize {
+    let mut imax = i64::MIN;
+    let mut jmax = i64::MIN;
+    let mut imin = i64::MAX;
+    let mut jmin = i64::MAX;
+    for e in elves {
+        imax = max(imax, e.0);
+        jmax = max(jmax, e.1);
+        imin = min(imin, e.0);
+        jmin = min(jmin, e.1);
+    }
+    ((imax-imin+1) * (jmax-jmin+1)) as usize
+}
+
+fn main() {
+    let (mut elves, mut lookup) = read_from_stdin();
+    let _ = play(&mut elves, &mut lookup, 10);
+    let result = size(&elves) - elves.len();
+    println!("{result}");
+}
diff --git a/2022/23/b.rs b/2022/23/b.rs
new file mode 100644
index 0000000..20868b9
--- /dev/null
+++ b/2022/23/b.rs
@@ -0,0 +1,12 @@
+mod common;
+use common::*;
+
+fn main() {
+    const MAX_TURNS: usize = 1000;
+    let (mut elves, mut lookup) = read_from_stdin();
+    if let Some(n) = play(&mut elves, &mut lookup, MAX_TURNS) {
+        println!("{}", n+1);
+    } else {
+        panic!("Not enough turns ({}), try increasing MAX_TURNS", MAX_TURNS);
+    }
+}
diff --git a/2022/23/common.rs b/2022/23/common.rs
new file mode 100644
index 0000000..3cf974b
--- /dev/null
+++ b/2022/23/common.rs
@@ -0,0 +1,83 @@
+use std::collections::{HashMap, HashSet};
+
+const DIRECTIONS: [[(i64, i64); 3]; 4] = [
+    [(-1, 0), (-1, 1), (-1, -1)],
+    [(1, 0), (1, 1), (1, -1)],
+    [(0, -1), (1, -1), (-1, -1)],
+    [(0, 1), (1, 1), (-1, 1)]
+];
+
+pub fn read_from_stdin() -> (Vec<(i64, i64)>, HashMap<(i64, i64), usize>) {
+    let mut v = vec![];
+    let mut lookup = HashMap::new();
+    let mut line = String::new();
+    let mut i = 0;
+    while std::io::stdin().read_line(&mut line).unwrap() > 0 {
+        let bytes = line.as_bytes();
+        for j in 0..bytes.len() {
+            if bytes[j] == b'#' {
+                lookup.insert((i, j as i64), v.len());
+                v.push((i, j as i64));
+            }
+        }
+        i += 1;
+        line.clear();
+    }
+    (v, lookup)
+}
+
+pub fn free_around(e: (i64, i64), m: &HashMap<(i64, i64), usize>) -> bool {
+    for d in [
+        (-1, -1), (-1,  0), (-1,  1),
+        ( 0, -1),           ( 0,  1),
+        ( 1, -1), ( 1,  0), ( 1,  1)
+    ] {
+        if m.contains_key(&(e.0 + d.0, e.1 + d.1)) { return false; }
+    }
+    true
+}
+
+pub fn play(
+    elves: &mut Vec<(i64, i64)>,
+    lookup: &mut HashMap<(i64, i64), usize>,
+    nturns: usize
+) -> Option<usize> {
+    let mut claimed = HashMap::<(i64, i64), usize>::new();
+    let mut stopped = HashSet::<(i64, i64)>::new();
+    for t in 0..nturns {
+        // First half
+        for i in 0..elves.len() {
+            let e = elves[i];
+            if free_around(e, &lookup) { continue; }
+            for j in 0..4 {
+                let d = DIRECTIONS[(t+j)%4].iter()
+                        .map(|x| (e.0+x.0, e.1+x.1))
+                        .collect::<Vec<_>>();
+                if !lookup.contains_key(&d[0]) &&
+                   !lookup.contains_key(&d[1]) &&
+                   !lookup.contains_key(&d[2])
+                {
+                    if claimed.contains_key(&d[0]) { stopped.insert(d[0]); }
+                    claimed.insert(d[0], i);
+                    break;
+                }
+            }
+        }
+
+        // Second half
+        let mut any_moved = false;
+        for (moveto, i) in &claimed {
+            if stopped.contains(&moveto) { continue; }
+            any_moved = true;
+            lookup.remove(&elves[*i]);
+            elves[*i] = *moveto;
+            lookup.insert(elves[*i], *i);
+        }
+        if !any_moved { return Some(t); }
+
+        // Cleanup
+        claimed.clear();
+        stopped.clear();
+    }
+    None
+}