2018 Advent of Code, Day 23

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:

• elementary number theory
  • triangular numbers
  • modular arithmetic
  • fast exponentiation
  • the Chinese Remainder Theorem
• geometry:
  • two-dimensional transformations
  • three-dimensional objects
• Conway’s Game of Life
• The puzzle master is obsessed with taxicab geometry, also called Manhattan distance.

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:

• search algorithms
• recursive descent parsing
• implementing virtual machines

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:

• advanced mathematics, in the form of both three-dimensional geometry and linear programs — something most mathematicians never learn;
• an advanced search algorithm I’d never heard of called octree search; and
• a three-dimensional space…
• …with coordinates so large as to make a brute-force search impossible.

Setup

The problem’s setup: 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:

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.

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 red one is “as the crow flies”; it takes us over skyscrapers, churches, and police stations. That distance is \[\sqrt{(-2-4)^2+(-3-1)^2}=\sqrt{40}\approx6.3.\]
• However, this route is not available to a pedestrian or a taxicab, who must walk along grid points, forcing one to walk only horizontally or vertically. Because of this, the shortest route always requires one to traverse 10 grid points:
  • Option 1: leave \((-2,-3)\) and pass through \((-2,-2),(-2,-1),(-2,0),(-2,1)\), turn right, then pass through \((-1,1),(0,1),(1,1),(2,1),(3,1)\), ending at \((4,1)\).
  • Option 2: leave \((-2,-3)\) and pass through \((-1,-3),(0,-3)\), turn left, then pass through \((0,-2),(0,-1)\), turn right, then pass through, \((1,-1),(2,-1),(3,-1),(4,-1)\), turn left, then pass through \((4,0)\), ending at \((4,1)\).
  • There are many others. Try a different one and verify that it takes at least 10 units.

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

• (x − 10) + (y − 12) + (z − 10) ≥ 0
• (x − 10) + (y − 12) − (z − 10) ≤ 0
• (x − 10) − (y − 12) + (z − 10) ≥ 0
• (x − 10) − (y − 12) − (z − 10) ≤ 0
• (x − 10) + (y − 12) + (z − 14) ≤ 0
• (x − 10) + (y − 12) − (z − 14) ≥ 0
• (x − 10) − (y − 12) + (z − 14) ≤ 0
• (x − 10) − (y − 12) − (z − 14) ≥ 0

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

• −s/2 ≤ x −a ≤ s/2
• −s/2 ≤ y −b ≤ s/2
• −s/2 ≤ z −c ≤ s/2 .

Algorithm

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

• Start with a cube large enough to encompass all the octohedra.
  
• Repeat the following steps until the cube radius is 1.
  1. You have a cube.
  2. Divide it into 8 equally-sized cubes.
  3. Count how many octohedra intersect each smaller cube.
  4. Select the cube with the most intersections.

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.

Illustration

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.

Implementation

Having worked out this theory, one challenge remained:

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.

• It almost always requires a pre-processing stage to massage the inequalities into a “nice” form.
• Avoiding an infinite loop requires some care at each step.
• If you do it by hand, you’re likely to encounter fractions, and few people appreciate those.

I could in theory write a subprogram to solve such linear programs, but previous experience has shown that This Is Non-Trivial^TM. 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: 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:

• Turn the automatically-generated Ada thin binding to glpk into a thick binding with a more Ada-like API.
• Re-implement this yet again with a custom-made simplex solver, perhaps specialized to this system of linear equations.