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:
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:
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.