Compressing coordinate systems

The infamous YouTube algorithm recommended me a very interesting video recently, in which Neal Wu was the first person to complete Advent of Code 2021 day 22.

I’ve never watched a competitive programmer in action before, so it was fascinating to watch his thought process and methods, since the values being optimised for are vastly different than when building software you intend to maintain for years.

The gist of the problem being solved is: You are given a series of axis-aligned bounding boxes and on/off states. Apply these boxes to a 3D grid, turning on or off all the cells within each bounding box as instructed. After applying all the bounding boxes, count how many cells are switched on.

The first twenty or so bounding boxes are easy enough, sitting within +-50 units from the origin. However, the remainder cover a much larger area, +-100,000 units from the origin. The obvious implication being that the naive solution of constructing the grid in memory isn’t feasible. 200,000 x 200,000 x 200,000 is far too many cells to iterate over in a reasonable amount of time.

My solution for this was to borrow from my hobby game-dev programming experience and manipulate the bounding boxes directly, rather than the cells that they affect.

My algorithm was roughly:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

regionList = []
input = [bounding boxes + on/off state]

for isOn,box in input:
  for region in regionList:
    if region fully within box:
      remove region
    if region partially within box:
      region_a, region_b = split region along an edge of box
      remove region from regionList
      add region_a and region_b to regionList
  repeat above until no further changes made to regionList
  if isOn:
    add box to regionList
result = sum of volumes of regions in regionList

What I’m quite pleased about with this algorithm is that it does not have special logic to deal with all the different ways that two AABBs can overlap with each other. The only edge case, pardon the pun, is when two AABBs partially overlap but one is not fully contained by the other. By picking any intersection edge, we can split one of the AABBs in two. With enough passes the intersection will eventually simplify to the complete overlap case.

This is the pure maths approach and I thought it was quite neat, but when I watched Neal’s video I couldn’t figure out what his approach was until he explained it afterwards.

His approach is something I’d never heard of before, and I don’t think I’d ever have thought of it. It’s beautiful in its simplicity.

Build a grid, much like the naive solution, but not out of 1x1x1 cells. Instead, put cell boundaries at all boundaries that the input AABBs will sit on. Let me try to clarify through the medium of ascii art:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

Dense grid of 1x1x1 cells.
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+
| | | | | | | | | | | | |
+-+-+-+-+-+-+-+-+-+-+-+-+

Sparse grid of differently sized cells.
+-+-+-+-+-+-+-+-+-+-+-+-+
|     |   |     |   |   |
|     |   |     |   |   |
|     |   |     |   |   |
+-+-+-+-+-+-+-+-+-+-+-+-+
|     |   |     |   |   |
|     |   |     |   |   |
+-+-+-+-+-+-+-+-+-+-+-+-+
|     |   |     |   |   |
|     |   |     |   |   |
+-+-+-+-+-+-+-+-+-+-+-+-+

When turning cells on and off by the given AABBs, both grids will give the same answer. By placing boundaries only where absolutely necessary based on the AABBs, the dimensions of the grid and memory requirements for it are vastly reduced. A 5x4x8 region in the dense grid requires a whopping 160 bits of memory to keep track of. In the sparse grid it’s reduced to a single bit, and 5x4x8 would be a very small cell compared to the ones typically generated by the advent of code input. So it’s obvious how this trick reduces the space and time requirements of the problem by orders of magnitude.

These kinds of neat hacks are exactly the sort of thing I’d love to know more of. I don’t know where Neal learned this, but I’m going to be sure to watch more of his competitive programming videos in future to see what other tricks I can pinch from his toolbox.