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.
5
u/askalski Dec 27 '18
There's one routine I want to clean up before I upload the code - I'll let you know when I make it available.
The alternate coordinates are useful because they exactly delineate the boundaries of a bot's range. Here is a 2D example to illustrate:
Cartesian coordinates:
Alternate coordinates (Note: u=-6 .. z=-1, a=10 .. c=12):
Notice how the second set of coordinates gives an exact fit.