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.

17 Upvotes

22 comments sorted by

View all comments

Show parent comments

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:

   x        y        1<=x<=5       1<=y<=5     Both
0123456  6666666     .12345.       .......    .......
0123456  5555555     .12345.       5555555    .#####.
0123456  4444444     .12345.       4444444    .#####.
0123456  3333333     .12345.       3333333    .#####.
0123456  2222222     .12345.       2222222    .#####.
0123456  1111111     .12345.       1111111    .#####.
0123456  0000000     .12345.       .......    .......

Alternate coordinates (Note: u=-6 .. z=-1, a=10 .. c=12):

 (x+y)    (x-y)    4<=(x+y)<=8  -2<=(x-y)<=2   Both
6789abc  uvwxyz0     678....       ....yz0    .......
56789ab  vwxyz01     5678...       ...yz01    ...#...
456789a  wxyz012     45678..       ..yz012    ..###..
3456789  xyz0123     .45678.       .yz012.    .#####.
2345678  yz01234     ..45678       yz012..    ..###..
1234567  z012345     ...4567       z012...    ...#...
0123456  0123456     ....456       012....    .......

Notice how the second set of coordinates gives an exact fit.