1 files changed, 177 insertions, 0 deletions
diff --git a/2024/day12.rs b/2024/day12.rs
new file mode 100644
index 0000000..1dc2a1a
--- /dev/null
+++ b/2024/day12.rs
@@ -0,0 +1,177 @@
+#![allow(dead_code)]
+#![allow(unused_variables)]
+#![allow(unused_mut)]
+use std::collections::HashMap;
+use std::collections::HashSet;
+use std::env;
+use std::fs::File;
+use std::io::Read;
+
+fn flood(x0: i64, y0: i64, m: &Vec<Vec<char>>) -> HashSet<(i64, i64)> {
+    let mut visited: HashSet<(i64, i64)> = HashSet::new();
+    let mut new: HashSet<(i64, i64)> = HashSet::new();
+    let h = m.len() as i64;
+    let w = m[0].len() as i64;
+
+    visited.insert((x0, y0));
+    let mut go = true;
+    while go {
+        go = false;
+        for (x0, y0) in visited.clone() {
+            for (dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1)] {
+                let x = x0 + dx as i64;
+                let y = y0 + dy as i64;
+                if (0 <= x) && (x < w) && (0 <= y) && (y < h) {
+                    if visited.contains(&(x, y)) {
+                        continue;
+                    }
+                    if m[y0 as usize][x0 as usize] == m[y as usize][x as usize] {
+                        go = true;
+                        new.insert((x, y));
+                    }
+                }
+            }
+        }
+        visited.extend(&new);
+    }
+
+    return visited;
+}
+
+fn get_border(region: &HashSet<(i64, i64)>) -> HashMap<(i64, i64), HashSet<(i64, i64)>> {
+    let region: HashSet<(i64, i64)> = region.iter().map(|(x, y)| (*x as i64, *y as i64)).collect();
+    let mut border: HashMap<(i64, i64), HashSet<(i64, i64)>> = HashMap::new();
+    for (x0, y0) in &region {
+        for (dx, dy) in [(1, 0), (-1, 0), (0, 1), (0, -1)] {
+            let x = x0 + dx as i64;
+            let y = y0 + dy as i64;
+            if !region.contains(&(x, y)) {
+                border.entry((x, y)).or_default().insert((dx, dy));
+            }
+        }
+    }
+    return border;
+}
+
+fn flood_border(
+    x0: i64,
+    y0: i64,
+    dx0: i64,
+    dy0: i64,
+    mut border: HashMap<(i64, i64), HashSet<(i64, i64)>>,
+) -> HashMap<(i64, i64), HashSet<(i64, i64)>> {
+    let mut visited: HashSet<(i64, i64)> = HashSet::new();
+    let mut new: HashSet<(i64, i64)> = HashSet::new();
+
+    //println!("{} {}", x0, y0);
+    border.get_mut(&(x0, y0)).unwrap().remove(&(dx0, dy0));
+    if border.get(&(x0, y0)).unwrap().len() == 0 {
+        border.remove(&(x0, y0));
+    }
+
+    visited.insert((x0, y0));
+    let mut go = true;
+    while go {
+        go = false;
+        for (x0, y0) in visited.clone() {
+            for (dx, dy) in [(dy0, dx0), (-dy0, -dx0)] {
+                let x = x0 + dx;
+                let y = y0 + dy;
+                //println!("{} {} {} {}", x, y, dx, dy);
+                //println!("{:?}", border);
+                if visited.contains(&(x, y)) {
+                    continue;
+                }
+                if border.contains_key(&(x, y))
+                    && border.get(&(x, y)).unwrap().contains(&(dx0, dy0))
+                {
+                    go = true;
+                    new.insert((x, y));
+
+                    border.get_mut(&(x, y)).unwrap().remove(&(dx0, dy0));
+                    if border.get(&(x, y)).unwrap().len() == 0 {
+                        border.remove(&(x, y));
+                    }
+                }
+            }
+        }
+        visited.extend(&new);
+    }
+
+    return border;
+}
+
+fn get_sides(mut border: HashMap<(i64, i64), HashSet<(i64, i64)>>) -> i64 {
+    let mut s = 0;
+    loop {
+        let elem = border.iter().next().unwrap().clone();
+        let ((x0, y0), dirs) = elem;
+        //println!("{} {}", x0, y0);
+        if dirs.len() == 0 {
+            border.remove(&(*x0, *y0));
+            continue;
+        }
+        let (dx, dy) = dirs.iter().next().unwrap().clone();
+
+        border = flood_border(*x0, *y0, dx, dy, border);
+        s += 1;
+        //println!("border {:?}", border);
+        if border.len() == 0 {
+            break;
+        }
+    }
+
+    return s;
+}
+
+fn main() {
+    let args: Vec<String> = env::args().collect();
+    let filename = if args.len() == 1 {
+        "in/".to_owned() + args[0].split('/').last().unwrap() + ".pzl"
+    } else {
+        args[1].clone()
+    };
+    let mut f = File::open(filename).expect("cannot open file");
+    let mut content = String::new();
+    f.read_to_string(&mut content).expect("cannot read file");
+    let lines = content.trim_end().split("\n");
+
+    let mut m: Vec<Vec<char>> = Vec::new();
+    for line in lines {
+        let mut row: Vec<char> = Vec::new();
+        for c in line.chars() {
+            row.push(c);
+        }
+        m.push(row);
+    }
+
+    let mut res1 = 0;
+    let mut res2 = 0;
+    let mut visited: HashSet<(i64, i64)> = HashSet::new();
+    for y in 0..m.len() {
+        for x in 0..m[y].len() {
+            let x = x as i64;
+            let y = y as i64;
+            if visited.contains(&(x, y)) {
+                continue;
+            }
+            let region = flood(x, y, &m);
+            let border = get_border(&region);
+            let area = region.len() as i64;
+
+            let perimeter = border.values().map(|v| v.len()).sum::<usize>() as i64;
+            res1 += area * perimeter;
+
+            let sides = get_sides(border.clone());
+            //println!("sides {}", sides);
+            res2 += area * sides;
+
+            visited.extend(&region);
+        }
+    }
+
+    println!("res1: {}", res1);
+    println!("res2: {}", res2);
+    assert_eq!(res1, 1381056);
+    assert_eq!(res2, 834828);
+}