advent of code, haskell

Advent of Code 2022 day 18

After the past few days, day 18 was a bit of a relief! I wonder if this was intended to be a day where people could catch up?

Data structures

This is again direct. I have a droplet (a three-dimensional point) and some lava (a set of droplets).

type Droplet = V3 Int
type Lava = S.Set Droplet

Counting surfaces

The neighbours of a droplet are the positions at ±1 in each dimension.

neigbours :: Droplet -> Lava
neigbours here = S.fromList [ here & d %~ (+) n | d <- [_x, _y, _z], n <- [- 1, 1]]

The surface area contribution of a droplet is 6 faces, -1 for each neighbour that has a droplet. The only wrinkle is converting the lava to a list so it doesn't collapse the result to just the distinct areas.

surfaceArea :: Lava -> Int
surfaceArea lava = sum $ fmap countFree $ S.elems lava
  where countFree droplet = 6 - (S.size $ S.intersection lava (neigbours droplet))

Finding the steam

I started by thinking about how to find if a point was completely enclosed in a polyhedron, but then realised there was a more direct method.

  1. Define a box outside the droplet
  2. Fill it with steam (with the steam not penetrating the droplet)
  3. The enclosed droplet is the box minus the steam

The box is a bit larger than it needs to be, to ensure that the steam can reach all the surfaces of the droplet.

"Filling with steam" is a standard flood-fill process, with a boundary and a set of steam-filled locations. As a point in the boundary is processed, its neighbours are added to the bounary so long as they've not already been processed, are inside the box, and aren't a droplet of lava.

part2 lava = surfaceArea enclosed
  where box = boundingBox lava
        steam = floodFill lava box (S.singleton $ head $ range box) S.empty
        enclosed = (S.fromList (range box)) `S.difference` steam

boundingBox lava = ((V3 minX minY minZ), (V3 maxX maxY maxZ))
  where minX = (fromJust $ minimumOf (folded . _x) lava) - 1
        minY = (fromJust $ minimumOf (folded . _y) lava) - 1
        minZ = (fromJust $ minimumOf (folded . _z) lava) - 1
        maxX = (fromJust $ maximumOf (folded . _x) lava) + 1
        maxY = (fromJust $ maximumOf (folded . _y) lava) + 1
        maxZ = (fromJust $ maximumOf (folded . _z) lava) + 1

floodFill lava box boundary found
  | S.null boundary = found
  | otherwise = floodFill lava box (S.union nbrs $ S.delete here boundary) (S.insert here found)
  where here = S.findMin boundary
        nbrs = S.filter (`S.notMember` lava) 
                $ S.filter (`S.notMember` boundary) 
                $ S.filter (`S.notMember` found) 
                $ S.filter (inRange box) 
                $ neigbours here

Code

You can get the code from my locally-hosted Git repo, or from Gitlab.