AoC 2022 D18: Boiling Boulders

| Problem statement | Source code | Tags: BFS/DFS

Part 1

We want the total surface area. The contribution of each cube to the surface area is determined only by its neighbors: For each face, if it has a neighbor in that direction, the face doesn't contribute to the surface area; otherwise, it contributes 1.

neighbors3d :: (Int, Int, Int) -> [(Int, Int, Int)]
neighbors3d (x, y, z) = [(x + 1, y, z), (x - 1, y, z), (x, y + 1, z), (x, y - 1, z), (x, y, z + 1), (x, y, z - 1)]

surfaceArea :: Set (Int, Int, Int) -> Int
surfaceArea cubes = Set.foldr (\p -> (+ exposedSides p)) 0 cubes
  where
    exposedSides p = count (`Set.notMember` cubes) (neighbors3d p)

Part 2

Now we want the exterior surface area. The contribution of each face now needs to check more than its neighbors. The perfectly physically sensible solution is to immerge the thing in water and see how many faces touch water—this is flood filling, which is, again, implemented with BFS. We add one unit of padding around the whole shape, so that we can deterministically have a starting point outside the shape, as well as be sure that the water can eventually reach all faces of the shape without getting stuck in a corner.

Once we have the set of water cubes, we can check all faces to see if they are exposed to water. If a face is adjacent to a water cube, it contributes 1 to the exterior surface area.

exposedArea :: Set (Int, Int, Int) -> Int
exposedArea cubes = Set.foldr (\p -> (+ exposedSides p)) 0 cubes
  where
    minX = minimum (Set.map (\(x, _, _) -> x) cubes) - 1
    maxX = maximum (Set.map (\(x, _, _) -> x) cubes) + 1
    minY = minimum (Set.map (\(_, y, _) -> y) cubes) - 1
    maxY = maximum (Set.map (\(_, y, _) -> y) cubes) + 1
    minZ = minimum (Set.map (\(_, _, z) -> z) cubes) - 1
    maxZ = maximum (Set.map (\(_, _, z) -> z) cubes) + 1
    inBox (x, y, z) = x >= minX && x <= maxX && y >= minY && y <= maxY && z >= minZ && z <= maxZ
    start = (minX, minY, minZ)
    outsideAir = bfs (Seq.singleton start) (Set.singleton start)
    bfs :: Seq (Int, Int, Int) -> Set (Int, Int, Int) -> Set (Int, Int, Int)
    bfs Seq.Empty seen = seen
    bfs (p Seq.:<| q) seen =
      let next = [n | n <- neighbors3d p, inBox n, n `Set.notMember` cubes, n `Set.notMember` seen]
          seen' = foldr Set.insert seen next
          q' = q Seq.>< Seq.fromList next
       in bfs q' seen'
    exposedSides p = count (`Set.member` outsideAir) (neighbors3d p)

← Previous Back to AoC Index Next →