Expand description
§Experimental Emergency Teleportation
A generic solution to part two would be a 3D version of binary search. Starting with a single cube that encloses all nanobots, each cube is further split into 8 smaller cubes until we find the answer. Cubes can be stored in a min-heap ordered by:
- Greatest number of nanobots in range.
- Least distance to origin.
- Least size.
This means that when we encounter a cube of size 1, we can return the coordinates, since we know that:
- There are no cubes within range of more nanobots.
- There are no cubes that are closer.
- The coordinates cannot be refined any further.
However, the actual input files lend themselves to an even faster answer. At a high level, we can determine a one-dimensional range of Manhattan distances at which we are in range of a given nanobot. By sorting the points at which ranges begin and end, we can determine the maximum number of nanobots that can possibly be in range at once. In the generic case, two nanobots may have the same Manhattan distance but be non-overlapping in distinct octants of 3D space, so the actual best point may have fewer than the maximum determined in this manner. But for our input files, it so happens that there is exactly one range that has a higher potential than any other, and the low end of this range happens to be the Manhattan distance we are after, without actually having to find the point with that distance.