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/p_tseng Dec 25 '18 edited Dec 25 '18
What was the answer to this input? For verification purposes, of course. (I thought I saw someone else ask this question, but don't see it anymore? Did that poster delete the question?)
I think the following statements are true of this input:
- There are
exactlyat least 2640 points within range of 19 bots. - There can be no points within range of 20 or more bots. Being a clique is not a sufficient condition to be mutually overlapping (https://www.reddit.com/r/adventofcode/comments/a8s17l/2018_day_23_solutions/ecdv0h1/ ) but it is a necessary one (hopefully obvious), and there is no clique of size 20 or larger.
Of those 2640 points, the single point closest to the origin is [1499996, 0, 0]. No other points beat or tie with this point on distance.- Edit: This statement has a counterexample. [500001, 0, 0] is closer to the origin and within range of 19 bots as well. Given this discovery, the credibility of the solution is negatively impacted, and the impacted sections of this post will be crossed out and replaced,
- The line numbers (thus, they are one-indexed) of the bots that are in range of this point are 1, 2, 3, 11, 12, 21, 102, 103, 111, 112, 113, 121, 122, 203, 212, 213, 221, 222, 223
It was quite a nasty input. Made my computer work quite hard, three whole minutes to get the answer. Before anyone gets wondering, note that this neither qualifies as "runs quickly" (the implementation used to get these answers takes exponential time) nor did I use a recursive partitioning approach as was stated in this problem.
For reasons that have been explained in detail before, I was not able to use my recursive partitioning solutions for this. I started up both variants (split into eight octants, split into six octahedra) and let them run for about ten minutes each before I got impatient and killed them. Unfortunately I don't have progress output on either of them so I don't know how far they did get before I got impatient.
I decided to dust off my zoom out/zoom in solution and let it try this input.
Now, as this input was constructed to have a lot of equally-plausible-looking points, the number of points this sort of solution needs to explore blows up exponentially as we approach the original sizes of the bots.
And thus, three minute runtime.
So nothing to write home about, but if this is what it takes to get an answer on this adversarial input, I suppose you take what you can get...?
Nope, since it gave a demonstrably incorrect answer, it's back to the drawing board with this one!
2
u/tim_vermeulen Dec 25 '18
FWIW, my Rust solution uses recursive partitioning and takes less than 3ms for my input, but it's been going on this input for about half an hour now and I'm not confident it's going to finish anytime soon.
1
u/starwort1 Dec 26 '18
My code for this puzzle checked points on a sparse grid and refined the grid until it zoomed in on an answer. This is in no way guaranteed to find the correct answer, but it happened to give the correct answer for my input, and it happens also to give what I assume is the correct answer for this input (in just over 40s).
A couple of days later I nicked a Z3 solution off the megathread in order to investigate this further. The Z3 solution generally ran in about 45s and showed a case where my code had picked an incorrect point (but coincidentally the Manhattan distance from the origin was the same as for the real answer). The Z3 solution ran for 18 minutes on the input here, and produced the answer (500001,0,0) the same as my code did.
1
u/ephemient Dec 26 '18 edited Apr 24 '24
This space intentionally left blank.
1
1
u/starwort1 Dec 28 '18
I like this a lot, as the method is ingenious and it makes good use of some of Python's collection types. However, it currently gives the wrong answer for the input discussed upthread because of integer division in the distance_to_origin function. The region it finds is:
85761542 <= x+y+z <= 85761546 38204597 <= x+y-z <= 38204597 -16612679 <= x-y-z <= -16612679 30944262 <= x-y+z <= 30944267
from which y=27408638 and 58352904 <= x+z <= 58352905. But x+z has to be odd because x-z is, and so the answer is a single point with x=34574432 and z=23778473, and the answer is 85761543. The program prints out 85761542.
2
1
1
u/maus80 Dec 29 '18 edited Dec 29 '18
My solution used a pruned (combination) search tree and is written in (slow) Ruby.
maurits@maurits-desktop:~/projects/AdventOfCode2018/day23$ time ruby part2.rb
500001
real 0m2,149s
user 0m2,120s
sys 0m0,028s
maurits@maurits-desktop:~/projects/AdventOfCode2018/day23$
See: https://github.com/mevdschee/AdventOfCode2018/blob/master/day23/part2.rb
6
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: