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.

- Define a box outside the droplet
- Fill it with steam (with the steam not penetrating the droplet)
- 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.