#015

I’ve been back home this week for Christmas.

I finished Advent of Code this week (my solutions are on github). I particularly enjoyed day 23 part 2, which is to find the coordinate in range of most nanobots. Or, to put it in a more abstract setting, to find the point in 3-dimensional manhattan space which is contained within the most spheres. This was a challenge to come up with a good solution for, as I’ve not done much computational geometry stuff before.

The solution I came up with ended up being the same as most other people, as it turns out. The insight is that it’s cheap to check if a sphere overlaps a region of space, and it’s cheap to split a region into smaller regions, knowing which spheres overlap each such subregion. So you can recursively partition the space until you get to a region of a single point, with more overlapping spheres than any other region. If you explore regions in order of how many overlapping spheres they have (using a priority queue), you effectively rapidly zoom in on the best point, and don’t even consider most of the space. I got the idea by thinking of how you would solve this by eye in a 2d space with translucent circles on a huge piece of paper: you’d try to find the darkest bits of paper first and then examine those more closely.