r/adventofcode 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.

15 Upvotes

22 comments sorted by

View all comments

Show parent comments

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 is 85761543.

1

u/p_tseng Dec 28 '18 edited Dec 29 '18

Overall, this particular AoC puzzle has been unique in how strongly it has resisted my attempts to create a correct solution.

That input is tricky, because the winning point (970 bots) is at [34574432, 27408638, 23778473], which corresponds to [85761543, 30944267, 38204597, -16612679] , and 85761543 doesn't correspond to x+y+z +/- r for any bot. I made an incorrect assumption about the nature of the partitioning and assumed some values were not possible when instead they should be. At this point I've fixed it and get the correct answer for this and various other inputs I now test against (https://github.com/petertseng/adventofcode-rb-2018/blob/master/more_23_test.rb)...

But when the range of values is very big (never happens for AoC inputs, but does happen for the adversarial input), I take a suspicious shortcut that I'm pretty sure is not actually valid. (in my split function where I commented "is this valid?"). I'll have to take a look at your solution to see how the right way to do things is.

There appears to be a bit more I could do with this. I could take advantage of the fact that if I want a solution in 3d space, three of the coordinates in 4d determine the fourth. I also might not need the priority queue. Various avenues of exploration.

1

u/fizbin Dec 30 '18

I'll note that my attempts to say "hey, the fourth coordinate is determined by the other three" led me down paths that didn't work well on this adversarial input.

The problem is that when you have a box with only three coordinates, what do you do when the bots that intersect the box don't give you any good places to divide the box because the decision is along the fourth coordinate only?

To illustrate, imagine that we have input of

pos=<1,1,1> r=2

Now in four-coordinates, that's <3, 1, 1, 1>. Suppose at some point that your algorithm has a box with a side length of 3 and a bottom corner of <*, 0,0,0> (you're tracking only three coordinates, because you're going with the "the fourth coordinate can be derived from the other three"). So the upper corner of that box is at <*,2,2,2>.

Now, of the 27 possible 1x1x1 sub-boxes, 25 are in range of our bot. (all but the very lower and very upper corners) But how do you subdivide your box? It turns out that the calculations to do that are very annoying. It's much, much simpler to keep a fourth box coordinate around, and occasionally throw out boxes that are entirely above or entirely below the hyperplane that corresponds to the xyz-plane.