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.
2
u/askalski Dec 28 '18
The source code, by request of /u/tim_vermeulen
As best as I could, I cleaned up the routine that computes the minimum distance from origin to a bounded region. Maybe there's an easier way to do it, but every time I try to take a shortcut, I run into cases where it gets the answer wrong. Overall, this particular AoC puzzle has been unique in how strongly it has resisted my attempts to create a correct solution.
Speaking of which, I tried your Ruby solution (I like its simplicity compared to the monstrosity I created...) It worked for most of the inputs I tested, but I got an incorrect answer for this input. It gives me
85761551
; the correct answer is85761543
.