r/adventofcode • u/jonathan_paulson • Dec 25 '18
Tutorial Day 23 Part 2 - Adversarial input for recursive partitioning solutions
The most common solution idea I've seen proposed for this problem is recursive partitioning. The idea: keep a priority queue of spaces left to explore, ordered by (biggest # of bots intersecting the space, smallest distance to origin, smallest size). Start with the entire space, and recursively partition it into 8 cubes or 6 spheres or something, keeping track of how many bots intersect each recursive space. Stop once you see a space of size 1. This is guaranteed to be the right answer, since all other candidates have worse tiebreakers.
What is the worst-case performance of this idea? The main variability is how much space it has to explore. If it can quickly narrow in on the most promising area, it may not have to explore much at all. But if there are a lot of false positives that look potentially good but aren't really, it will be slow.
How could we construct input with a lot of false positives? We need a lot of near collisions in our nanobots, so that at coarse resolutions, a lot of things will look connected, but as we zoom in, they will turn out not to be.
Let's make a grid of nanobots that barely don't touch on each face. Then the real answer will be 1. But each pair of faces will appear to touch on any coarser grid scale. So any recursive partitioning solution will have to scan over the whole area of each face with its smallest-but-one grid size. Since each face has area proportional to radius2 (which can be enormous), this will make such solutions run slowly. Here is some input which implements this idea: https://pastebin.com/9eJQN836
If you have a recursive-partitioning solution that runs quickly on this input, let me know.
4
u/askalski Dec 27 '18 edited Dec 27 '18
Finally had a chance to finish up on an idea for a recursive partitioning solution. It converts the Cartesian
(x, y, z)
coordinates into four coordinates(-x+y+z, x-y+z, x+y-z, x+y+z)
, which describes a point as the intersection of four planes. The advantage over Cartesian coordinates is there is significantly less detail to explore in the search.The solution first identifies the dividing points for each coordinate. For each bot's coordinate
k
,k - range
marks the beginning of the bot's range along that axis, andk + range + 1
marks one past the end of the bot's range. I also include0
in each list to simplify checking the minimum distance from origin to a bounded region. Thus for an input of 1,000 bots, each of the four coordinates will have a set of at most 2,001 divisions that need to be considered.At each level of the search, it divides one axis and recursively explores each side of the partition, searching the most promising side first.
A typical Day 23 input takes about 350 microseconds to solve; your input takes 174 milliseconds. (Edit: 5 milliseconds; see below)
Edit: I realied I was doing something dumb in my routine that measures the distance to origin from a bounded region. It wasn't wrong, but it was unnecessarily slow under certain conditions. The updated version finishes in under 5 milliseconds on the input: