This is the first problem for which I had to get a solution online for the second part.
For the first part of the problem, I solved it by finding the nanobot with the largest radius and counting the number of nanobot in range of it.
For the second part, I tried a couple of different things:
- Brute force the search: there are 1000 nanobots in an area of 10,000,000 cubed positions, this is just not viable;
- Use a divide-and-conquer approach, dividing the space into 8 regions, keeping the regions with the most nanobots and continuing this way: the nanobots have a radius so big that they cover almost all the regions all the time so the number of regions to check explodes pretty quickly;
- Find the coordinates for each axis where the number of nanobots is the biggest and find the triple that has the highest count: here again I found around 100,000 cubed possibilities, even brute-forcing this is not viable;
- Using a local search approach, starting at a point and slowly moving the point towards points that have a higher count: this is prone to finding local maxima instead the of the global maxima which we want and might not return the global maximum which is the closest to the origin.
So after all those attempts, I decided to go check online for some help. On the advent of code subreddit, there is a post for the solutions for this problem. After reading the comments, I figured I wasn't the only one that needed some help with this one. A lot of the proposed solutions wouldn't work for all inputs, and others used a Python library called Z3 to solve it, basically removing the grunt work of the problem. This is probably something that I should become familiar with if I want to do these problems next year also.
I started by trying a simpler solution that was proposed by u/EriiKKo in this comment. His solution is to create line segments from the origin to each nanobot and count the number of overlapping segments, returning the maximum count found, which is the solution. There are a couple of counter-examples, as described later in the comments, but this solution worked for my input.