Note: This topic is to talk about Day 23 of the Advent of Code.
For general discussion about the Advent of Code 2018 and links to topics of the other days, see this topic.
Here is my solution for day 13.
The hardest one so far. I implemented a divide and conquer algorithm. Basically, I divided the 3D space into cubes and found the cubes with the most number of bots in range. I then divided that cube into smaller cubes and so on. (Actually, I don’t explicitly sub-divide the space. Instead, I scale down the coordinates and radii for the bots. When I have found a solution for the scaled down problem, I transform the found point back to the original coordinate system.)
When I finally got it working and producing a reasonable answer, the answer was wrong.
I got the right answer when I extended the search. When I have found one cube, I added the adjacent cubes to it and then continue to sub-divide that cube.
My solution runs in about a second.
1 Like
I saw on reddit that most people are using the same approach. I wonder is it a general solution though? Once you pick an optimal region and even if you take adjacent regions, I still think it’s possible that the solution may lie in an intersection of discarded regions.
Since I’m not convinced that this will solve all the cases, I decided not to take that path. After some thinking, I started thinking how would I solve this problem in 1D, and then see how could this be extended to 3D. This brought me to the idea of using some sort of a line sweep (or plane sweep) to quickly find the largest set of overlapping regions. Once we have that, it takes another single pass to intersect those regions, and then I expect the resulting region would be small enough that it can be linearly scanned for the global optimum.
Unfortunately I got stuck at the very first step (line sweep). I still think the idea is sound, but I just don’t get the proper results 
I think I’ll postpone part 2 for the moment and get back to it later, but I definitely want to take another stab at this.
Once I’m past the line sweep, there is still a remaining challenge of intersecting octahedrons. I feel that this could be simplified if I extrapolated to cubes instead. In fact, perhaps I should extrapolate to cubes before doing the line sweep too. The result would be a somewhat larger region, but I still hope it would be small enough to do a quick linear scan.
1 Like
Yes, I thought about that too. My solution is probably not general enough for any input data.
It will be interesting to see your line sweeping solution.
After waking up, I thought some more about this, and I think that line sweeping won’t work for 3D. The reason is that these nanobots are octahedrons, while line sweeping would assume that the regions are cuboids. So while this approach would possibly give the correct solution for the input, I can think of cases where this approach would mistakenly pick a wrong region.
So I decided to browse the reddit comments again and see if someone came up with a more sound approach, and I think I finally found it. The idea is similar to yours (divide-and-conquer), but the important difference is that we don’t discard other choices.
So let’s say that we split the entire area into four large cubes, and then compute the amount of nanobots each cube intersects with. We’ll store all the cubes into a priority queue. Then, from the queue we pull the cube which intersects with the most nanobots. If there are multiple cubes with the same best score, we pick the one closest to the origin (0, 0, 0). We then divide that cube, compute the intersection scores for each subcube, and put the subcubes into the queue. Then rinse and repeat. The first cube of size 1 that we pull is the solution.
I currently can’t see anything wrong with this algorithm. Of course, there are some cases where this optimization won’t help (e.g. if we only have pair intersections), but I think that this algorithm would always return the correct result, no matter what the input is. I’ll turn my attention to day 24 now, and keep this in the back of my mind, but this is currently my best candidate 
1 Like
Finally implemented part 2. My solution is here and it takes 2 seconds. The algorithm is basically what I’ve described in the previous post.
1 Like
Wow, that was really the toughest day so far.
At first I was thinking about trying to solve this in each dimension separately and combine the results, but it was not obvious how to combine those. Then I tried to approach this with simulated annealing and made some progress, but was really stuck with getting to the global optimum.
So I ended up with the same strategy that you’ve all mentioned. I start with the bounding box of the nanobots. For each box, I calculate the upper bound of the max intersecting nanobots (for the unit box - 1x1x1 - the count is exact). I use upper bound to simplify the code - I use a sphere instead of a box for easier check of intersections. If the upper bound is less than my best solution, then I discard that box, otherwise split it and continue. As you’ve mentioned, the key thing is not to discard the box with smaller count. Since I’m lazy, I only split the box in two, along the longest dimension. Looking at @sasajuric’s solution it turns out that splitting the box into 8 was less effort than I thought would be. When I get down to the unit box, I check if it’s better than the current solution and replace it if needed.
Instead of using a priority queue, I went with a plain list. That would make the algorithm run forever, but the trick that I used is to re-run my algorithm with different initial best solutions: with count from 1000 down to 1. For high initial values of counts, the algorithm stops almost immediately because it discards all the boxes and finds no solution. In the end, the whole thing finds the proper solution in about 1 second.
