First of all, happy new year to you :)

Last december, I participated to the annual Advent of Code event. Each day, @Eric Wastl releases a programming problem to solve for all folks who wants a bit of a challenge. All the problems are contextualized in a Christmas adventure that makes the whole experience feel less like an academic exercise.

You can find my Python solutions for each of the 25 days on my advent-of-code Github repository if you want.

In this blog post I will do a quick walkthrough of the solution I ended up with, one of many ways to solve the problem of Day 22 : Reactor Reboot.

Discovering problem 22

I enjoyed day 22. It's one of those that makes you feel that the answer is easy to get, but actually it's not. The concept is fairly simple to understand at first read :

To reboot the reactor, you just need to set all of the cubes to either on or off by following a list of reboot steps (your puzzle input).

Reboot steps consist in setting some 3D region to either a ON or OFF status, fair enough.

on x=10..12,y=10..12,z=10..12
on x=11..13,y=11..13,z=11..13
off x=9..11,y=9..11,z=9..11
on x=10..10,y=10..10,z=10..10

What we are asked for is to count the number of positions (cubes) set to ON after all the instructions were applied.

From reading the first few lines of instructions, a trivial way to solve this we can think about is by updating a big boolean matrix for each instruction by setting either $0$ or $1$ values into the right indexes.

But if you keep scrolling...

on x=-54112..-39298,y=-85059..-49293,z=-27449..7877
on x=967..23432,y=45373..81175,z=27513..53682

Oh.

Those are big numbers. In 3D. Clearly, allocating a $[100000, 100000, 100000]$ matrix and working on it does not seems like a great idea. At least for part 2, because part 1 involves only cuboids with coordinates belonging to $[-50, 50]$.

Now what ?

Knowing that you can't build that matrix, what are your options ?

The main issue here is to manage the multiple intersections between cuboids, the list growing as you keep adding cuboids.

I didn't feel like doing iterative intersection work that day, so I implemented something that I found out later had a name : coordinate compression.

Coordinate compression

Get all the boxes

Intersections are what make this problem hard. So I wanted to compute all possible intersections right away. I did so by sorting the vector $\mathbf{x}$ of $x$ coordinates, same for $\mathbf{y}$ and $\mathbf{z}$.

Then, I considered a 3D lattice with splits in planes $xy$, $xz$ and $yz$ occurring at each value of respectively $\mathbf{z}$, $\mathbf{y}$ and $\mathbf{x}$.

Below is an animated view of a lattice created from $3$ bounding boxes.

This is a lot of useless boxes. But we also have all of the possible intersections from all the boxes contained in the cuboids list. The good news being that we actually have to store a matrix with a size much more manageable now : $\text{dim}(\mathbf{x}) * \text{dim}(\mathbf{y}) * \text{dim}(\mathbf{z})$.

Encode the boxes

Now that we took care of intersections, let's make an observation : the span of coordinates is big, but the whole problem really is sparse. There is a lot of empty space between each faces of the boxes. From this observation, one can conclude that there is no need to actually store $N$ times the same value $v$, but simply the value $N$, somewhere.

Because the coordinates of the problem are indexes, the size of this box is $16$.

on x=0..3,y=0..3,z=0..3

From this definition, I ended up encoding every cuboid the following way.

First, I created a new matrix of size $2*\text{dim}(\mathbf{x})* 2*\text{dim}(\mathbf{y}) * 2*\text{dim}(\mathbf{z})$, I think of it as a matrix with a hole between every coordinate of the original coordinates vector that we will need to fill.

Then, I filled the matrix with the following values at the right indexes :

• A given corner has its own index.
  • e.g. $(i, j, k) = 1$.
• Between two corners in $x$, $y$ and $z$ directions, we encode the length of the distance between them, think of it as edges.
  • e.g. in $(i+1, j, k) = L$
• Between four corners, we encode the area of the plane between them, think of it as areas.
  • e.g. in $(i+1, j+1, k) = S$
• Between eight corners, we encode the inner volume.
  • e.g. in $(i+1, j+1, k+1) = V$

And here is an extract of the corresponding Python code :

def build_matrix(sortx, sorty, sortz):
    len_x, len_y, len_z = len(sortx), len(sorty), len(sortz)
    mat = np.zeros((2*len_x+1, 2*len_y+1, 2*len_z+1), dtype = np.int64)
    for xi in range(len_x):
        for yi in range(len_y):
            for zi in range(len_z):
                xib, yib, zib = xi+1 < len_x, yi+1 < len_y, zi+1 < len_z
                if xib: dx = sortx[xi+1] - sortx[xi] - 1
                if yib: dy = sorty[yi+1] - sorty[yi] - 1
                if zib: dz = sortz[zi+1] - sortz[zi] - 1
                mat[1+2*xi,1+2*yi,1+2*zi] = 1 # corner
                if xib and yib and zib: 
                    mat[1+2*xi+1,1+2*yi+1,1+2*zi+1] = dx * dy * dz # inner volume
                if xib: 
                    mat[1+2*xi+1,1+2*yi,1+2*zi] = dx # edge
                    if yib: mat[1+2*xi+1,1+2*yi+1,1+2*zi] = dx * dy # area
                    if zib: mat[1+2*xi+1,1+2*yi,1+2*zi+1] = dx * dz # area
                if yib: 
                    mat[1+2*xi,1+2*yi+1,1+2*zi] = dy # edge
                    if zib: mat[1+2*xi,1+2*yi+1,1+2*zi+1] = dy * dz # area
                if zib: mat[1+2*xi,1+2*yi,1+2*zi+1] = dz # edge
    return mat

And this is what it would look like in 3D for a $5\times 5\times5$ cuboid:

Each corner is mapped to one $(x, y, z)$ coordinate of the 3D lattice computed earlier. Every in-between space is compressed by computing either length, area or volume is represents. We compress the empty space into fewer values.

This new representation of the problem was really straightforward to use in actually solving the problem, the hardest was done.

Solving the actual problem

From now, it's a bit too easy : that's what I wanted !

All I had to do was iterating on the list of boxes, and updating a mask of $1$ and $0$ in my new coordinates system. A $1$ would mean I have to add this particular [corner, edge, area, volume] to the final sum.

You have to get the conversion between the box and the compressed matrix right, but because everything is sorted and we only introduced a factor of 2, nothing too complicated.

def compute_mask(cuboids):
    mask = np.zeros(shape = np.shape(mat), dtype = np.int64)
    for c in cuboids:
        v = 1 if c[0] == 'on' else 0
        x, _x = x_pos[c[1][0]], x_pos[c[1][1]]
        y, _y = y_pos[c[2][0]], y_pos[c[2][1]]
        z, _z = z_pos[c[3][0]], z_pos[c[3][1]]
        mask[1+2*x:1+2*_x+1, 1+2*y:1+2*_y+1, 1+2*z:1+2*_z+1] = v
    return mask

Once the mask is computed, I summed the values of my corner, edges, areas, volumes matrix where the mask was equal to 1.

And that's it, two more stars ;)