[2018 Day 23] In Review (Experimental Emergency Teleportation)

[u/musifter]

Having discovered that the man's friend is sick reindeer, we're now in the position of having to use emergency teleport to get out of the cave. Not something you typically want to use (if experience in classic roguelikes and robots says anything).

For this we get a thousand nanobots, with coordinates in the 8-9 digit range (positive and negative) and radii from about 49.5 million to 100 million. So the scale is huge. All the radii are unique so there's no confusion on what nanobot to use for part 1, and so it's mostly a test of doing Manhattan distances between that bot and the others.

Part 2 is where things get interesting. For this one, I did an octant tree search (k-d tree where k=3). But to direct things, I use a priority queue for the boxes, and queue them based on the number of nanobots who's influence intersects it. So I'm always looking at the best ones early, and I quickly get at least a good estimate (I do find one with 980 bots that's one closer first, before finding the answer (which has more bots) shortly after), so most of the queue gets pruned. For my input, I only do 120 boxes before getting the answer, and almost all of the remaining 937 get tossed immediately.

Another thing I did was scan regions below a certain threshold instead of partitioning right down. The threshold that worked well was 4... so any box with all dimensions <= 4 gets scanned. This is another reason why I get to the answer in only 120 regions. Only 256 coordinates get checked in the end with this... over a total of 7 scans. So it's really quite fast, only taking 2 seconds. And there's lots left on the table because it being in scripting language. For example, just unrolling of the loop that calculates distance from a point to a box, saves .3 seconds. A compiler will do that for you without making your code look like copy pasta. And so, I don't really think bumming things right down is that worth it... 2 seconds for a scripting language on old hardware working on a problem of this scale is more than good enough. If I want speed, I'll use the appropriate tools for it.

This is another of my favourites... it's fun working to find the optimal spot in such a huge space that you can't really cheese it.

[u/e_blake]

I was pleased to get my star in 2018 without reading the megathread; my solution in C used a form of gradient descent search. I started at the origin with a power-of-2 step size large enough to cover all the nanobots, then checked the 27 points at half the step size to see which had the most bots in range with a radius of that size. The code then either moved in the direction that had more bots than the current location, moved to the location with the same number but closer to the origin, or stayed put but cut the step size down; until eventually reaching a step size of 1. Figuring out how to decide if a nanobot was in range of a given point with a radius was a bit tricky; my code ended up with a lengthy nested conditional for 8 different +- conditions for x, y, and z considered separately (probably something I would try to clean up if revisiting this). I got a wrong answer when I tried cutting the step size exactly in half, but when I changed one line in code to instead reduce the step size by 3/4 (so that the 27 points I was probing each iteration shared more overlap and less likely to land me on a local maximum distinct from the global max), the code quickly narrowed in on the right location in just 125 iterations (125*27*1000 Manhattan distances computed); running in 70ms, and directly computing the magic coordinate.

But when implementing my m4 solution in 2021, I read the megathread to see if there was a better approach to consider. And one thread called out a particularly clever algorithm that happens to work on input files, even though it is not generic to the larger universe of all possible 3-D nearest neighbor searches. The idea is that you flatten each nanobot's sphere-of-influence into a range of Manhattan distances from the origin in which an intersection is even possible. For example, a nanobot at 2,-2,2 with radius 1 has a closest Manhattan distance of 5 and furthest of 7 (|2|+|-2|+|2| +- 1), while a bot at -1,1,-2 with range 5 has a minimum distance 0 (since the origin is in range) and maximum distance 9. Computing the range of possible Manhattan distances is O(1) per nanobot, or O(n) to come up with 2000 interesting points along a 1-D number line where the number of maximum possible overlaps increases or decreases as nanobots go in and out of range (without regards to whether the nanobots are actually in range of each other, or are in distinct octants of the overall 3-D space). If you then sort this number line with O(n log n) effort (a radix sort is impractical given the size of the numbers being sorted), to learn which Manhattan distance(s) are candidates for having the most possible overlapping nanobots (+1 at a nanobot's start-of-range, -1 at one past end-of-range; for just the two bots I mentioned above, this would be [0,5)=>1, [5,8)=>2, [8,10)=>1, [10,inf]=>0, or a best possible of 2 overlaps at distance 5). In the general case, this is still just a starting point: a maximum number of plausible intersections, but not necessarily the actual result. For example, if this says that the maximum possible overlap is 967, but you don't actually have 967 nanobots that are each in range of at least 966 others, then you know for certain that at least two nanobots at that distance have non-overlapping ranges (or back to my 2 points above - they don't intersect, so your actual answer would be 1 intesection at the origin). But for THIS puzzle, it so happens that Eric's inputs are extremely nice (because of how the part 1 largest-radius nanobot was laid out): everyone who mentioned trying this approach documents having just ONE possible range on the 1-D number line that has a maximum possible of Manhattan overlaps, and the low end of that range HAPPENS to be the right answer, without you ever having to figure out the actual coordinates of the magic point that produces that Manhattan distance. So my m4 solution runs in 230ms, with just 2000 Manhattan distances computed and an O(n log n) sort.

[u/ednl → u/e_blake]

Yes to the second part. Runs in 91 µs on an Apple M4.

typedef struct {
    int dist, delta;
} Tuple;

qsort(nanobot, N, sizeof *nanobot, range_desc);
int count = 1;  // "including itself"
for (size_t i = 1; i < N; ++i)
    count += inrange(&nanobot[0], &nanobot[i]);
printf("Part 1: %d\n", count);

// Part 2
const Pos origin = (Pos){0, 0, 0};
for (size_t i = 0; i < N; ++i) {
    const int dist = manh(&nanobot[i].pos, &origin);
    const int add = dist > nanobot[i].range ? dist - nanobot[i].range : 0;
    const int sub = dist + nanobot[i].range;
    counter[i * 2]     = (Tuple){add, +1};  // add this bot at the near end of its range
    counter[i * 2 + 1] = (Tuple){sub, -1};  // subtract this bot at the far end of its range
}
qsort(counter, N * 2, sizeof *counter, dist_asc);
size_t i = 0;
while (counter[i].delta == 1)  // this only works because no delta is -1 until after maximum
    ++i;
printf("Part 2: %d\n", counter[i - 1].dist);

[u/DelightfulCodeWeasel]

I had to step through my solution just to remember what it was doing! It does rely on there being one unique region for the largest number of overlapping bots, but I think that's a fairly safe bet.

For each nanobot I form an octahedral bounding box using min and max planes along each of the four axis. Then for each axis I treat the planes as begin and end segments, sort them and run through them in order looking for the biggest set of overlapping segments.

The set of nanobots overlapping the target region is the set intersection of the four largest overlapping sets from each axis. The target region is then just the intersection of all of the bounding volumes for those nanobots, and finally the Manhattan distance is the maximum plane distance of the 8 bounding planes.

Overall complexity is something like O(n) to form the bounding boxes, O(n log n) for the sorted planes, O(n log n)-ish to form the overlapping sets, O(n) for the set intersection and O(n) to form the target region bounding volume.

[u/terje_wiig_mathisen]

On this one I'm looking at my code, and I have no idea what I was actually thinking?

It is also one of the slowest solutions I've ever written in Rust, taking 2 seconds...