ShareMyScreen/AdventOfCode/2022/18/BoilingBouldersJP

The Problem << >>

This was my favourite day of AoC 2022: a non-trivial problem with a very elegant and fast solution.

Entire solution

i18 =: freads '18.txt'
NB. face offsets, vertices sorted per face.
fo  =:(3#2)#:0 1 4 5,4 5 6 7,2 3 6 7,0 1 2 3,1 3 5 7,:0 2 4 6
NB. convert voxels to faces
vtf =: [: ,/ +"1/&fo
NB. count where single occurrence of faces
part1 =: [: +/ (1=#/.~)@vtf@(".;._2)
NB. Same, but consider only external faces (i.e. not closed spaces disjunct from outside air)
part2 =: {{
  lava  =. (+"(1)1 1 1- <./) ".;._2 y          NB. lava (offset input) to get min of all coords at 0
  air   =. ((#: [:i.*/)@:>:@:(>./) -. ]) lava  NB. air & lava (offset by 1 for edge)
  cc    =. _1,~i.#air                          NB. initial component identifiers (_1 for non-found)
  sh    =. 0,(,-)3 3$1 0 0 0                   NB. shifts for self & 6-neighbourhood
  neigh =. |: (,#) air i.!.0 air +"1/ sh       NB. indices of neighbours into cc
  cc    =. neigh (>./@:{)^:_ cc                NB. 6-connected components, repeat until no change
  +/ (1=#/.~) lava -.&vtf air #~ (~: {.)@}: cc NB. Count unique faces not being in pockets (i.e. having identifier = to first)
}}

Part 1

Data is in a very nice format for parsing today, indicating cubes or voxels of lava by comma-separated triples of coordinates. Parsing is trivial using ".;._2 . Part 1 asks for the surface area of the lava. This means I need the faces from each of the voxels, and see which are not touching.

To expand each voxel to its faces, I chose the following encoding, e.g. for voxel 0 0 0 (excluding the vertical edges of the cube for clarity):

       0,0,1           1
     /      \         / \
  1,0,1    0,1,1     5   3
     \      /         \ /
       1,1,1           7
                ==>
       0,0,0           0
     /      \         / \
  1,0,0    0,1,0     4   2
     \      /         \ /
       1,1,0           6

So, the offsets of the vertices from the voxel center coordinate of each of the faces can be compactly encoded as integers:

NB.           left    front   right   back    top     bottom
fo =: (3#2)#:0 1 4 5,4 5 6 7,2 3 6 7,0 1 2 3,1 3 5 7,:0 2 4 6

The verb to convert voxels to faces is trivial, as it just needs adding the offsets to the center to represent the faces (note that it needs a list of voxels, though, and returns a single list of faces):

   vtf =: [: ,/ +"1/&fo
   #. vtf ,: 0 0 0
0 1 4 5
4 5 6 7
2 3 6 7
0 1 2 3
1 3 5 7
0 2 4 6

Now I just need the number of unique faces:

part1 =: [: +/ (1=#/.~)@vtf@(".;._2)

Part 2

Part 2 is similar, but only faces connected to outside air should be counted (so no faces in entirely internal air bubbles). For this I'd need to see which air voxels are connected to outside air, and which not. The idea I had is something along the lines of connected-component labelling on the air voxels. This is easy by giving each air voxel an id number, and then iteratively taking the maximum between neighbouring voxels. This will cause all voxels in a single connected component to get the maximum identifier of the entire component, and all disjunct components will have different identifiers. For the outside air voxels to be connected, they have to surround the lava from all sides. To do so, I offset the lava coordinates so there's air at each coordinate's 0 plane:

lava =. (+"(1)1 1 1- <./) ".;._2 y

Then the air voxels are all voxels that are in the space of 0,0,0 to >:@(>./) lava and that are not lava:

air =. ((#: [:i.*/)@:(2&+)@:(>./) -. ]) lava

For the connected component analysis, the initial labels are:

cc=. _1,~i.#air

with _1 such that neighbours that are not found do not influence the maximum taken later on. Now, I need to make an array that records for each voxel, the indices of the neighbourhood over which we'll take the maximum. To do so, I need coordinates for 6 shift directions:

sh  =. 0,(,-)3 3$1 0 0 0

Note that the zero shift (0,) is absolutely essential because the central voxel has to be part of the neighbourhood. Now, the neighbour indices can be gotten by adding the shifts, and looking them up in the original array (The exact comparison, !.0, speeds up i. when operating on non-scalar items). Adding the maximum causes positions that have no neighbour to correspond to the _1 in cc that I added earlier. The transpose makes for a very simple and quick implementation of the iterative part, as it gets the neighbours for a single voxel in rows, so insert (/) works between the neighbours of a voxel, for all voxels at once.

neigh =. |: (,#) air i.!.0 air +"1/ sh

Having done all the heavy lifting beforehand, the iteration becomes very simple and boils down to indexing the identifies to get the neighbours ones, and taking the maximum, until none change.

cc =. neigh (>./@:{)^:_ cc NB. connected components

Now the voxels of each connected component have a unique identifier and, due to the padding, the first identifier, corresponding to (0,0,0), is outside air. Any air that is not connected to outside air is an air pocket, and we have to count faces of lava that are not being shared with airpockets:

+/ (1=#/.~) lava -.&vtf air #~ (~: {.)@}: cc

I really learnt something from this day's solution: a connected neighbourhood analysis using indices is more elegant and far faster than having to do coordinate lookups, or even shifts inside the loop. The above solution does most steps in an array-oriented way (like coordinate shifting and coordinate lookups) on the entire arrays, leaving only very fast operations (max and indexing) to be done in the iterations.