1 files changed, 157 insertions, 0 deletions
diff --git a/2022/src/bin/day_18.rs b/2022/src/bin/day_18.rs
new file mode 100644
index 0000000..1111441
--- /dev/null
+++ b/2022/src/bin/day_18.rs
@@ -0,0 +1,157 @@
+use nom::{
+    bytes::complete::tag,
+    character::complete::{i32, line_ending},
+    combinator::map,
+    multi::separated_list1,
+    sequence::tuple,
+    IResult,
+};
+use std::{collections::BTreeSet, fs};
+
+fn main() -> Result<(), Box<dyn std::error::Error>> {
+    let input = fs::read_to_string("inputs/day_18.txt")?;
+    let voxels = Voxels::parser(&input).unwrap().1;
+    dbg!(voxels.naive_surface_area());
+    dbg!(voxels.exterior_surface_area());
+
+    Ok(())
+}
+
+#[derive(Debug, Clone)]
+struct Voxels(BTreeSet<Point3d>);
+
+#[derive(Debug, Default, Clone, PartialEq, Eq, PartialOrd, Ord)]
+struct Point3d {
+    x: i32,
+    y: i32,
+    z: i32,
+}
+
+impl Voxels {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        map(separated_list1(line_ending, Point3d::parser), |vox| {
+            Voxels(vox.into_iter().collect())
+        })(input)
+    }
+
+    fn naive_surface_area(&self) -> usize {
+        let units = Point3d::units();
+        self.0
+            .iter()
+            .flat_map(|v| units.iter().map(move |u| v + u))
+            .filter(|v| !self.0.contains(v))
+            .count()
+    }
+
+    fn exterior_surface_area(&self) -> usize {
+        let units = Point3d::units();
+        let mut known_internal: BTreeSet<Point3d> = BTreeSet::new();
+        let known_external = self.bounds();
+
+        self.0
+            .iter()
+            .flat_map(|v| units.iter().map(move |u| v + u))
+            .filter(|v| !self.0.contains(v))
+            .filter(|v| {
+                if known_internal.contains(v) {
+                    return false;
+                }
+
+                let mut flooded: BTreeSet<Point3d> = BTreeSet::new();
+                let mut frontier: BTreeSet<Point3d> = BTreeSet::new();
+                flooded.insert(v.clone());
+                frontier.insert(v.clone());
+                let mut is_internal = true;
+                while is_internal && frontier.len() > 0 {
+                    let mut next_frontier = BTreeSet::new();
+                    for front in &frontier {
+                        for unit in &units {
+                            let adjacent = front + unit;
+                            if !self.0.contains(&adjacent) && !flooded.contains(&adjacent) {
+                                if known_external.contains(&adjacent) {
+                                    is_internal = false;
+                                }
+                                flooded.insert(adjacent.clone());
+                                next_frontier.insert(adjacent);
+                            }
+                        }
+                    }
+                    frontier = next_frontier;
+                }
+                if is_internal {
+                    known_internal.append(&mut flooded);
+                }
+
+                !is_internal
+            })
+            .count()
+    }
+
+    fn bounds(&self) -> BTreeSet<Point3d> {
+        let min_x = self.0.iter().map(|v| v.x).min().unwrap_or(0) - 1;
+        let max_x = self.0.iter().map(|v| v.x).max().unwrap_or(0) + 1;
+        let min_y = self.0.iter().map(|v| v.y).min().unwrap_or(0) - 1;
+        let max_y = self.0.iter().map(|v| v.y).max().unwrap_or(0) + 1;
+        let min_z = self.0.iter().map(|v| v.z).min().unwrap_or(0) - 1;
+        let max_z = self.0.iter().map(|v| v.z).max().unwrap_or(0) + 1;
+
+        let mut result = BTreeSet::new();
+        for x in [min_x, max_x] {
+            for y in [min_y, max_y] {
+                for z in [min_z, max_z] {
+                    result.insert(Point3d { x, y, z });
+                }
+            }
+        }
+        result
+    }
+}
+
+impl Point3d {
+    fn parser(input: &str) -> IResult<&str, Self> {
+        map(
+            tuple((i32, tag(","), i32, tag(","), i32)),
+            |(x, _, y, _, z)| Point3d { x, y, z },
+        )(input)
+    }
+
+    fn units() -> Vec<Point3d> {
+        vec![
+            Point3d {
+                x: -1,
+                ..Point3d::default()
+            },
+            Point3d {
+                x: 1,
+                ..Point3d::default()
+            },
+            Point3d {
+                y: -1,
+                ..Point3d::default()
+            },
+            Point3d {
+                y: 1,
+                ..Point3d::default()
+            },
+            Point3d {
+                z: -1,
+                ..Point3d::default()
+            },
+            Point3d {
+                z: 1,
+                ..Point3d::default()
+            },
+        ]
+    }
+}
+
+impl ::core::ops::Add<&Point3d> for &Point3d {
+    type Output = Point3d;
+    fn add(self, rhs: &Point3d) -> Point3d {
+        Point3d {
+            x: self.x.add(rhs.x),
+            y: self.y.add(rhs.y),
+            z: self.z.add(rhs.z),
+        }
+    }
+}