day18 part2

1 files changed, 61 insertions, 4 deletions

diff --git a/src/bin/day18.rs b/src/bin/day18.rs
index 87f2133..f38e86b 100644
--- a/src/bin/day18.rs
+++ b/src/bin/day18.rs
@@ -1,11 +1,14 @@
+use std::collections::HashSet;
+
 static DAY: u8 = 18;
 
 fn main() {
     let input = advent::read_lines(DAY);
     println!("{DAY}a: {}", surface_area(&input));
-    println!("{DAY}b: {}", 0);
+    println!("{DAY}b: {}", exterior_surface_area(&input));
 }
 
+#[derive(PartialEq, Eq, Clone, Hash)]
 struct Cube {
     x: i32,
     y: i32,
@@ -22,6 +25,12 @@ impl Cube {
     }
 
     fn unconnected_surfaces(&self, cubes: &[Cube]) -> usize {
+        6 - cubes.iter()
+                 .filter(|&c| self.has_common_surface(c))
+                 .count()
+    }
+
+    fn has_common_surface(&self, other: &Cube) -> bool {
         let neighbors = [
             (self.x + 1, self.y, self.z),
             (self.x - 1, self.y, self.z),
@@ -30,9 +39,7 @@ impl Cube {
             (self.x, self.y, self.z + 1),
             (self.x, self.y, self.z - 1),
         ];
-        6 - cubes.iter()
-             .filter(|c| neighbors.contains(&(c.x, c.y, c.z)))
-             .count()
+        neighbors.contains(&(other.x, other.y, other.z))
     }
 }
 
@@ -45,6 +52,55 @@ fn surface_area(input: &[String]) -> usize {
          .sum()
 }
 
+fn find_outer_air(air: &mut HashSet<Cube>, cubes: &HashSet<Cube>, pos: &Cube, min: &Cube, max: &Cube) {
+    if cubes.contains(pos) || air.contains(pos) {
+        return;
+    }
+    air.insert(pos.clone());
+    let neighbors = [
+        Cube { x: pos.x - 1, y: pos.y, z: pos.z },
+        Cube { x: pos.x + 1, y: pos.y, z: pos.z },
+        Cube { x: pos.x, y: pos.y + 1, z: pos.z },
+        Cube { x: pos.x, y: pos.y - 1, z: pos.z },
+        Cube { x: pos.x, y: pos.y, z: pos.z + 1 },
+        Cube { x: pos.x, y: pos.y, z: pos.z - 1 },
+    ];
+    for neigh in neighbors {
+        if neigh.x < min.x || neigh.y < min.y || neigh.z < min.z || neigh.x > max.x || neigh.y > max.y || neigh.z > max.z {
+            continue;
+        }
+        find_outer_air(air, cubes, &neigh, min, max);
+    }
+}
+
+fn exterior_surface_area(input: &[String]) -> usize {
+    let cubes = input.iter()
+                     .map(|x| Cube::new(x))
+                     .collect::<HashSet<_>>();
+    let min_x = cubes.iter().map(|c| c.x).min().unwrap();
+    let min_y = cubes.iter().map(|c| c.y).min().unwrap();
+    let min_z = cubes.iter().map(|c| c.z).min().unwrap();
+    let min_cube = Cube { x: min_x - 1, y: min_y - 1, z: min_z - 1 };
+    let max_x = cubes.iter().map(|c| c.x).max().unwrap();
+    let max_y = cubes.iter().map(|c| c.y).max().unwrap();
+    let max_z = cubes.iter().map(|c| c.z).max().unwrap();
+    let max_cube = Cube { x: max_x + 1, y: max_y + 1, z: max_z + 1 };
+
+    let mut air = HashSet::new();
+    let start = Cube { x: 0, y: 0, z: 0 };
+    assert!(!cubes.contains(&start));
+    find_outer_air(&mut air, &cubes, &start, &min_cube, &max_cube);
+
+    let mut surfaces = 0;
+    for air_cube in air {
+        surfaces += cubes.iter()
+                         .filter(|c| c.has_common_surface(&air_cube))
+                         .count();
+    }
+
+    surfaces
+}
+
 #[cfg(test)]
 mod tests {
     use super::*;
@@ -68,5 +124,6 @@ mod tests {
         ].iter().map(|&x| String::from(x)).collect::<Vec<_>>();
 
         assert_eq!(surface_area(&input), 64);
+        assert_eq!(exterior_surface_area(&input), 58);
     }
 }