2018 Advent of Code, Day 23

This page is interactive!

To interact with 3-dimensional images, position the pointer over it and:
For the last few years, I have spent some spare hours solving puzzles from the Advent of Code. This competition begins every year on December 1st, releasing two puzzles a day until its final puzzle on December 25th. It usually features a storyline where you save Christmas, but let’s be honest: while the storylines are cute and you can learn a lot, 2021’s storyline featured undersea creatures I’d never heard of no one does the Advent of Code to indulge in high literature, just as no one goes to Hardee’s for nutrition. If you’re working the Advent of Code puzzles, you are ipso facto part of a class of people who would rather spend a few minutes, hours, or even days working on a programming puzzle than watching television, playing a video game, reading a book, or baking a cake. In other words, you’re nuttier than squirrel poop.

And that’s a good thing! The world could use more of us.

One thing I appreciate about the Advent of Code is how its puzzles often include interesting mathematics. For instance:

Another thing I appreciate is that many of the puzzles require some advanced computer science topics that I’ve either forgotten or never even learned:

A third aspect I appreciate, even if I don’t exactly enjoy it, is how many problems use such large numbers, or such enormous spaces, as to make brute-force problems impossible.

Day 23 of the 2018 competition featured all these things, if not in the problem itself, then certainly in my eventual solution:


The problem’s setup:
You hit the "experimental emergency teleportation" button on the device and push I accept the risk on no fewer than 18 different warning messages. Immediately, the device deploys hundreds of tiny nanobots which fly around the cavern, apparently assembling themselves into a very specific formation. The device lists the X,Y,Z position (pos) for each nanobot as well as its signal radius (r) on its tiny screen (your puzzle input).

Each nanobot can transmit signals to any integer coordinate which is a distance away from it less than or equal to its signal radius (as measured by Manhattan distance). Coordinates a distance away of less than or equal to a nanobot's signal radius are said to be in range of that nanobot.

For example, given the following nanobot formation:
    pos=<10,12,12>, r=2
    pos=<12,14,12>, r=2
    pos=<16,12,12>, r=4
    pos=<14,14,14>, r=6
    pos=<50,50,50>, r=200
    pos=<10,10,10>, r=5      
While the example features only 6 nanobots, the puzzle input has 1000. I’ll illustrate the mathematics, along with the eventual solution, using the example’s simpler case.

Here is a simple illustration of the nanobots. Dolly in to see that they lie on the other side of the 3-dimensional axes. The fifth nanobot is pretty far away, so you may have to rotate before you can identify it — but it’s there. OK, but what is this “Manhattan” distance?

Different ways to measure distance

Mathematics offers many precise methods of measuring distance. Related to distance is the notion of a neighborhood:
A neighborhood of fixed radius \(r\) around a point \(P\) is the set of points whose distance from \(P\) is at most \(r\).

Euclidean distance

Schools ordinarily teach Euclidean distance, so most people think of it as the “ordinary” way of measuring distance.

On a Euclidean plane, the distance between points \(P=(a,b)\) and \(Q=(r,s)\) is the familiar “distance formula”, \[d(P,Q) = \sqrt{(a-r)^2+(b-s)^2}.\] In this case, neighborhoods look like circles.

In a Euclidean space, the distance between points \(P=(a,b,c)\) and \(Q=(r,s,t)\) is similar, if less familiar, \[d(P,Q) = \sqrt{(a-r)^2+(b-s)^2+(c-t)^2}.\] In this case, neighborhoods look like spheres.
This illustration shows a blue, 3-dimensional Euclidean neighborhood of radius 4 around a red point. A black radius joins the center to a blue point on the sphere. Rotate the ball until you’ve convinced yourself that the blue point is, indeed, on the sphere’s surface.

Manhattan distance, in two dimensions

Not all geometries are Euclidean, but even when you are working in a Euclidean geometry, not all problems are best solved using Euclidean distance.

Consider the streets of a city laid out with square blocks, where you can travel only north, east, south, or west. The strict Euclidean distance still measures how far you’d travel from one point to another — if you’re a bird!

If, however, you are a mere man, you cannot travel “diagonally” through churches, skyscrapers, or police stations; you must “pound the pavement”, so to speak. If you want to know how many blocks you’d have to travel, the Euclidean formula is useless.

Let’s try this on a trip from the point \(P=(-2,-3)\) to the point \(Q=(4,1)\): The arrows show three different paths:

The illustration also highlights all points that lie in a neighborhood of radius 10 about \((-2,-3)\); it forms a rhombus rather than a circle. The green and orange paths may not look like the radii you’re accustomed to, but in this geometry, that’s precisely what they are.

The distance formula for the taxicab geometry is \[d(P,Q) = \Delta x + \Delta y = |a - r| + |b - s|\] in two dimensions, and \[d(P,Q) = \Delta x + \Delta y + \Delta z = |a - r| + |b - s| + |c - t|\] in three dimensions.

Manhattan distance, in three dimensions

In three dimensions, a taxicab neighborhood forms an octahedron rather than a sphere, as an octohedron is the 3-dimensional analogue of a rhombus. Each octohedron below highlights a nanobot’s neighborhood. You may also notice a red point; we’ll explain that below.

The problem itself

Isn’t that impressive? Yet that’s merely the problem’s setup!
[Y]ou need to find the coordinate which puts you in range of the largest number of nanobots. If there are multiple, choose one closest to your position (0,0,0 measured by manhattan distance).
In theory, you could solve the problem by simply enumerating all points within the minimum and maximum values of the nanobots’ neighborhoods’ x, y, and z components, going through each point methodically, checking how many nanobots it’s in range of, and selecting the the point in range of the most. That’s feasible for the example problem, as you could do it by hand, if you were determined enough: there “only” \(100\times100\times100=1,000,000\) points to consider. At one point a second (seems optimistic, but who am I to doubt you?) it would take “only” six days. Stock up on caffeine, because this estimate doesn’t include naps.

(I won’t explain why, but it’s relatively “easy” to see that you could in fact search half as many points without missing a winner. So your search time is now down to “only” three days. Hint: You only have to search inside each rhombus.)

(While I’m pointing out easy optimizations, a careful look at the nanobots also reveals that you could in fact search only \(25\times25\times25=15,625\) points. Good news: you’re now down to a much more manageable 4-and-a-half hours! Hint: One rhombus is clearly pointless, because it’s far too point-full.)

(Oh, and neither of these optimizations helps much for the puzzle.)

The illustration above shows a red point at \((12,12,12)\). This point is the solution to the example problem: Five octohedra intersect the red point in all. No other point intersects at least five octohedra, so we don’t have to apply the tie-breaking rule.
The puzzle input has a much, much larger space; a comprehensive search would require trillions of points. Even the fastest computers won’t finish that search anytime soon.

How do we solve it?

That’s a very good question.

This really is a difficult problem!

The puzzle master encourages participants to post their solutions at Reddit, and people stuck on the problem can always go there. If you visit the Reddit page of solutions to this puzzle, you will see quite a few comments along these lines:
In other words, a great many programs that “solve” the problem do not, in fact, solve the problem: they just get lucky on the particular input. This is not uncommon in the Advent of Code; I have often tried out someone else’s solution, only to find that it doesn’t produce the correct solution from my input. (I’ll write a bit about that below.)

Several people used a specialized SAT solver, which seemed like cheating, but in retrospect I ended up doing something morally and logically equivalent.

The approach I used

This approach should work for any input.

Mathematical background

It’s based on the notion of convex sets.

Essentially, a convex set is one where you can draw a line segment between any two points and still remain in the set. Spheres are convex sets; so are cubes and octohedra.

An interesting fact is that convex polyhedra, such as cubes and octohedra, can be described by a system of linear inequalities where each inequality corresponds to one of the polyhedron’s faces.

Here’s an illustration using the first nanobot above — the one positioned at \((10, 12, 12)\), with a range of 2 units. Each face is a different color, representing a different plane.

The inequality governing each face is:

You’ll see in a moment that we’re also interested in cubes. A cube centered at the point \((a,b,c)\) with side length \(s\) is defined by the inequalities


The technique is a kind of binary search, adapted to three dimensions using an octree. (I’d never heard of an octree before this puzzle, but apparently that’s how the puzzle master solved it.)

Experienced programmers and mathematicians will recognize a flaw: there may be more than one cube with the most intersections, so it is inaccurate to speak of “the” cube in step 4. Indeed, I overlooked that fact at first! It’s not hard to overcome this hurdle, though: if there is a tie in step 4, repeat from step 1 with each winner, rather than just the first.


You can interact with this illustration to see the algorithm at work: change the cubes’s side length to watch it narrow down on the red point. The cube that intersects the most targets is red. If the octahedra obstruct the neighborhoods, un-check the box to remove them from the image.

As mentioned before, the example had only one cube of length 1 in range of 5 nanobots, but in the puzzle input, many cubes of length 1 intersected the most nanobots, so you had more work to do to break the tie.


Having worked out this theory, one challenge remained:
How could I turn the algorithm into a program?

As noted already, a point lies in an octohedron if it satisfies 8 inequalities, and it lies in a cube if it satisfies 6 inequalities. It lies within both an octohedron and a cube if it lies within all 14 inequalities. Solving systems of inequalities is sufficiently challenging that an entire field of mathematics is dedicated to it, linear programming.

Both the Soviets and the Americans invented linear programming independently during World War II to help material things around the war more efficiently. Despite its applicability, it’s not widely taught: I didn’t study it until I was working on my PhD, and I didn’t really learn it until I taught a class on it.

Why isn’t it taught? Probably because the “easiest” tool to solve linear programs is the simplex algorithm. Don’t misread the name; “simplex” is not “simple”.The word “simplex” refers to a geometric figure whose properties are closely tied to the algorithm.

I could in theory write a subprogram to solve such linear programs, but previous experience has shown that This Is Non-TrivialTM. I might be able to work out a “general solution” to the specific inequalities that apply to this problem, but I concluded quickly that it would take more time than I was willing to expend.

Quite a few libraries offer routines to solve linear programs: glpk, CPLEX, and CLP come to mind. I even used glpk before during my previous life as a research mathematician.

Unfortunately, none of these libraries are available in Ada, the programming language I’ve been using to solve the Advent of Code problems. So I wasted quite a bit of time trying some other approaches, including one that, even though it works on my input, I still don’t fully understand.I’m a little worried it doesn’t work in general, though I have no concrete evidence. I just don’t trust algorithms with a load-bearing, unexplained fudge factor.

Fortunately, Ada interfaces with C, and the GNAT compiler provides a tool to generate bindings automatically. So the hardest part of implementing the algorithm turned out to be handling the cases where there are ties: as hinted above, you can’t just take the first cube of radius 1 that you encounter, as another cube may also intersect the same number of octohedra, and its intersection may lie closer than the first.

Caveats aside, this approach worked!

SAT solvers and Z3

I mentioned above that some entries used something called a “specialized SAT solver”. While I’ve never used those, I likewise first heard of them while working on my PhD, and despite the frown I cast in their direction, they’re closely related to the approach I adopted. Without going too far into the details, a SAT solver can determine, at least in principle, whether any logical statement is true or false.

I say that this is “morally equivalent” to the approach I used because my impression is that SAT Solvers rely heavily on linear programming and linear programming problems can be rewritten as logical statements. For example, the system of linear inequalities that is part of any linear program is essentially a logical statement made up of other logical statements:
(x − 10) + (y − 12) + (z − 10) ≥ 0
(x − 10) + (y − 12) − (z − 10) ≤ 0
Even if my vague recollection is incorrect, this still reinforces my point about the problem’s difficulty: I never heard of SAT Solvers until I was working on a PhD in mathematics. This was a conceptually difficult problem!

Possible follow-ups

A couple of ideas I’ve had since completing this problem: