day12 solution 1

1 files changed, 132 insertions, 0 deletions

diff --git a/src/bin/day12.rs b/src/bin/day12.rs
new file mode 100644
index 0000000..5ccf078
--- /dev/null
+++ b/src/bin/day12.rs
@@ -0,0 +1,132 @@
+use std::collections::{HashMap, HashSet};
+
+static DAY: u8 = 12;
+
+fn main() {
+    let input = advent::read_lines(DAY);
+    println!("{DAY}a: {}", fencing_price(&input));
+    println!("{DAY}b: {}", 0);
+}
+
+#[derive(Eq, PartialEq, Copy, Clone, Hash)]
+struct Position {
+    x: isize,
+    y: isize,
+}
+
+fn count_fences(region: &HashSet<Position>) -> usize {
+    let mut total_fences = 0;
+    for pos in region {
+        /* every plot has 4 fences, except it has neighbors of the same type */
+        let mut fences = 4;
+        for diff in [(-1, 0), (1, 0), (0, -1), (0, 1)] {
+            let neighbor = Position { x: pos.x + diff.0, y: pos.y + diff.1 };
+            if region.contains(&neighbor) {
+                fences -= 1;
+            }
+        }
+        total_fences += fences;
+    }
+    total_fences
+}
+
+fn find_region(plots: &HashMap<Position, char>, pos: Position, visited: &mut HashSet<Position>) -> HashSet<Position> {
+    let mut region = HashSet::new();
+    if visited.contains(&pos) {
+        return region;
+    }
+
+    let plot_type = plots.get(&pos).unwrap();
+    region.insert(pos);
+    visited.insert(pos);
+    for diff in [(-1, 0), (1, 0), (0, -1), (0, 1)] {
+        let neighbor = Position { x: pos.x + diff.0, y: pos.y + diff.1 };
+        if let Some(t) = plots.get(&neighbor) {
+            if t == plot_type {
+                for r in find_region(plots, neighbor, visited) {
+                    region.insert(r);
+                }
+            }
+        }
+    }
+
+    region
+}
+
+fn find_regions(plots: &HashMap<Position, char>) -> HashMap<char, Vec<HashSet<Position>>> {
+    let mut regions = HashMap::new();
+    let mut visited = HashSet::new();
+
+    for (pos, c) in plots {
+        if visited.contains(pos) {
+            continue;
+        }
+        let region = find_region(plots, *pos, &mut HashSet::new());
+        for plot in &region {
+            visited.insert(*plot);
+        }
+        regions.entry(*c).or_insert(Vec::new()).push(region);
+    }
+
+    regions
+}
+
+fn fencing_price(input: &[String]) -> usize {
+    let mut plots = HashMap::new();
+    for (x, line) in input.iter().enumerate() {
+        for (y, c) in line.chars().enumerate() {
+            let pos = Position { x: x as isize, y: y as isize };
+            plots.insert(pos, c);
+        }
+    }
+    let all_regions = find_regions(&plots);
+    let mut total_price = 0;
+    for regions in all_regions.values() {
+        for region in regions {
+            let area = region.len();
+            let fences = count_fences(region);
+            total_price += area * fences;
+        }
+    }
+
+    total_price
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test() {
+        let input = [
+            "AAAA",
+            "BBCD",
+            "BBCC",
+            "EEEC",
+        ].iter().map(|&x| String::from(x)).collect::<Vec<_>>();
+        assert_eq!(fencing_price(&input), 140);
+
+        let input = [
+            "OOOOO",
+            "OXOXO",
+            "OOOOO",
+            "OXOXO",
+            "OOOOO",
+        ].iter().map(|&x| String::from(x)).collect::<Vec<_>>();
+        assert_eq!(fencing_price(&input), 772);
+
+        let input = [
+            "RRRRIICCFF",
+            "RRRRIICCCF",
+            "VVRRRCCFFF",
+            "VVRCCCJFFF",
+            "VVVVCJJCFE",
+            "VVIVCCJJEE",
+            "VVIIICJJEE",
+            "MIIIIIJJEE",
+            "MIIISIJEEE",
+            "MMMISSJEEE",
+        ].iter().map(|&x| String::from(x)).collect::<Vec<_>>();
+        assert_eq!(fencing_price(&input), 1930);
+    }
+}