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.

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.

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