day12 solution 2

1 files changed, 106 insertions, 9 deletions

diff --git a/src/bin/day12.rs b/src/bin/day12.rs
index 5ccf078..c31ce47 100644
--- a/src/bin/day12.rs
+++ b/src/bin/day12.rs
@@ -4,8 +4,8 @@ static DAY: u8 = 12;
 
 fn main() {
     let input = advent::read_lines(DAY);
-    println!("{DAY}a: {}", fencing_price(&input));
-    println!("{DAY}b: {}", 0);
+    println!("{DAY}a: {}", fencing_price(&input, false));
+    println!("{DAY}b: {}", fencing_price(&input, true));
 }
 
 #[derive(Eq, PartialEq, Copy, Clone, Hash)]
@@ -30,6 +30,78 @@ fn count_fences(region: &HashSet<Position>) -> usize {
     total_fences
 }
 
+fn count_sides(region: &HashSet<Position>) -> usize {
+    let mut horizontal = HashSet::new();
+    let mut vertical = HashSet::new();
+
+    let mut min_pos = Position { x: isize::MAX, y: isize::MAX };
+    let mut max_pos = Position { x: isize::MIN, y: isize::MIN };
+
+    for pos in region {
+        min_pos.x = min_pos.x.min(pos.x);
+        min_pos.y = min_pos.y.min(pos.y);
+        max_pos.x = max_pos.x.max(pos.x);
+        max_pos.y = max_pos.y.max(pos.y);
+
+        let neighbor = Position { x: pos.x, y: pos.y + 1 };
+        if !region.contains(&neighbor) {
+            horizontal.insert((neighbor, 1));
+            max_pos.y = max_pos.y.max(neighbor.y);
+        }
+
+        let neighbor = Position { x: pos.x, y: pos.y - 1 };
+        if !region.contains(&neighbor) {
+            horizontal.insert((neighbor, 0));
+            min_pos.y = min_pos.y.min(neighbor.y);
+        }
+
+        let neighbor = Position { x: pos.x + 1, y: pos.y };
+        if !region.contains(&neighbor) {
+            vertical.insert((neighbor, 1));
+            max_pos.x = max_pos.x.max(neighbor.x);
+        }
+
+        let neighbor = Position { x: pos.x - 1, y: pos.y };
+        if !region.contains(&neighbor) {
+            vertical.insert((neighbor, 0));
+            min_pos.x = min_pos.x.min(neighbor.x);
+        }
+    }
+
+    let mut sides = 0;
+    for separator in [0, 1] {
+        for x in min_pos.x ..= max_pos.x {
+            let mut is_side = false;
+            for y in min_pos.y ..= max_pos.y {
+                let check = Position { x, y };
+                if is_side && !vertical.contains(&(check, separator)) {
+                    is_side = false;
+                    sides += 1;
+                }
+                if !is_side && vertical.contains(&(check, separator)) {
+                    is_side = true;
+                }
+            }
+        }
+    }
+    for separator in [0, 1] {
+        for y in min_pos.y ..= max_pos.y {
+            let mut is_side = false;
+            for x in min_pos.x ..= max_pos.x {
+                let check = Position { x, y };
+                if is_side && !horizontal.contains(&(check, separator)) {
+                    is_side = false;
+                    sides += 1;
+                }
+                if !is_side && horizontal.contains(&(check, separator)) {
+                    is_side = true;
+                }
+            }
+        }
+    }
+    sides
+}
+
 fn find_region(plots: &HashMap<Position, char>, pos: Position, visited: &mut HashSet<Position>) -> HashSet<Position> {
     let mut region = HashSet::new();
     if visited.contains(&pos) {
@@ -71,10 +143,10 @@ fn find_regions(plots: &HashMap<Position, char>) -> HashMap<char, Vec<HashSet<Po
     regions
 }
 
-fn fencing_price(input: &[String]) -> usize {
+fn fencing_price(input: &[String], with_discount: bool) -> usize {
     let mut plots = HashMap::new();
-    for (x, line) in input.iter().enumerate() {
-        for (y, c) in line.chars().enumerate() {
+    for (y, line) in input.iter().enumerate() {
+        for (x, c) in line.chars().enumerate() {
             let pos = Position { x: x as isize, y: y as isize };
             plots.insert(pos, c);
         }
@@ -84,7 +156,11 @@ fn fencing_price(input: &[String]) -> usize {
     for regions in all_regions.values() {
         for region in regions {
             let area = region.len();
-            let fences = count_fences(region);
+            let fences = if !with_discount {
+                count_fences(region)
+            } else {
+                count_sides(region)
+            };
             total_price += area * fences;
         }
     }
@@ -104,7 +180,8 @@ mod tests {
             "BBCC",
             "EEEC",
         ].iter().map(|&x| String::from(x)).collect::<Vec<_>>();
-        assert_eq!(fencing_price(&input), 140);
+        assert_eq!(fencing_price(&input, false), 140);
+        assert_eq!(fencing_price(&input, true), 80);
 
         let input = [
             "OOOOO",
@@ -113,7 +190,8 @@ mod tests {
             "OXOXO",
             "OOOOO",
         ].iter().map(|&x| String::from(x)).collect::<Vec<_>>();
-        assert_eq!(fencing_price(&input), 772);
+        assert_eq!(fencing_price(&input, false), 772);
+        assert_eq!(fencing_price(&input, true), 436);
 
         let input = [
             "RRRRIICCFF",
@@ -127,6 +205,25 @@ mod tests {
             "MIIISIJEEE",
             "MMMISSJEEE",
         ].iter().map(|&x| String::from(x)).collect::<Vec<_>>();
-        assert_eq!(fencing_price(&input), 1930);
+        assert_eq!(fencing_price(&input, false), 1930);
+
+        let input = [
+            "EEEEE",
+            "EXXXX",
+            "EEEEE",
+            "EXXXX",
+            "EEEEE",
+        ].iter().map(|&x| String::from(x)).collect::<Vec<_>>();
+        assert_eq!(fencing_price(&input, true), 236);
+
+        let input = [
+           "AAAAAA",
+           "AAABBA",
+           "AAABBA",
+           "ABBAAA",
+           "ABBAAA",
+           "AAAAAA",
+        ].iter().map(|&x| String::from(x)).collect::<Vec<_>>();
+        assert_eq!(fencing_price(&input, true), 368);
     }
 }