2018 Advent of Code, Day 23
This page is interactive!
To interact with 3dimensional images, position the pointer over it and:
 Hold the left button and move the pointer to rotate the image.
 Hold the right button and move the pointer to pan the image.
 Use the middle button, scroll wheel, or two fingers on the trackpad to dolly in or out.
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
 geometry:
 twodimensional transformations
 threedimensional 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 bruteforce 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 threedimensional geometry
and linear programs —
something most mathematicians never learn;
 an advanced search algorithm I’d never heard of
called octree search; and
 a threedimensional space…
 …with coordinates so large as to make a bruteforce search impossible.
Setup
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 3dimensional 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{(ar)^2+(bs)^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{(ar)^2+(bs)^2+(ct)^2}.\]
In this case, neighborhoods look like spheres.
This illustration shows a blue, 3dimensional 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 red one is “as the crow flies”;
it takes us over skyscrapers, churches, and police stations.
That distance is
\[\sqrt{(24)^2+(31)^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 3dimensional 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 4andahalf hours!
Hint: One rhombus is clearly point
less, 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:
 Three octohedra have a vertex at the red point.
 One octohedron has a face that that passes through the red sphere’s center.
 The largest octohedron contains the red point altogether.
 The “greenest” octohedron does not intersect the point at all.
(If this isn’t initially clear, then dolly in.)
Five octohedra intersect the red point in all.
No other point intersects at least five octohedra,
so we don’t have to apply the tiebreaking 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:
 My "solution" to part 2 is definitely not correct. …
To my great surprise it turned out to be the correct answer,
due to the input data being a bit poorly constructed.
 This was my idea as well,
but it didn't give me the correct solution
(which I found later using the z3 recommendation from this thread).
 Looks like this is based on not one but two incorrect conclusions :)
 It appears there is something wrong with my approach.
 Edit: It will not work for general case but works for my input.
 This is roughly what I did (just... much better),
and both my code and it get the same, wrong answer.
[Wow: two insults for the price of one!]
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.
 You have a cube.
 Divide it into 8 equallysized cubes.
 Count how many octohedra intersect each smaller cube.
 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,
uncheck 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:
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.
 It almost always requires a preprocessing 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 NonTrivial
^{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 loadbearing, 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
and
(x − 10) + (y − 12) − (z − 10) ≤ 0
and
…
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 followups
A couple of ideas I’ve had since completing this problem:
 Turn the automaticallygenerated Ada thin binding to glpk
into a thick binding with a more Adalike API.
 Reimplement this yet again with a custommade simplex solver,
perhaps specialized to this system of linear equations.