Pokémon Go Efficiency

This Riddler puzzle is about a topic near and dear to many hearts: Pokémon!

Your neighborhood park is full of Pokéstops — places where you can restock on Pokéballs to, yes, catch more Pokémon! You are at one of them right now and want to visit them all. The Pokéstops are located at points whose (x, y) coordinates are integers on a fixed coordinate system in the park.

For any given pair of Pokéstops in your park, it is possible to walk from one to the other along a path that always goes from one Pokéstop to another Pokéstop adjacent to it. (Two Pokéstops are considered adjacent if they are at points that are exactly 1 unit apart. For example, Pokéstops at (3, 4) and (4, 4) would be considered adjacent.)

You’re an ambitious and efficient Pokémon trainer, who is also a bit of a homebody: You wish to visit each Pokéstop and return to where you started, while traveling the shortest possible total distance. In this open park, it is possible to walk in a straight line from any point to any other point — you’re not confined to the coordinate system’s grid. It turns out that this is a really hard problem, so you seek an approximate solution.

If there are N Pokéstops in total, find the upper and lower bounds on the total length of the optimal walk. (Your objective is to find bounds whose ratio is as close to 1 as possible.)

Advanced extra credit: For solvers who prefer a numerical question with this theme, suppose that the Pokéstops are located at every point with coordinates (x, y), where x and y are relatively prime positive integers less than or equal to 1,000. Find upper and lower bounds for the length of the optimal walk, again seeking bounds whose ratio is as close to 1 as possible.

The problem of visiting a set of locations while minimizing total distance traveled is known as a Traveling Salesman Problem (TSP), and it is indeed a famous and notoriously difficult problem in computer science. That being said, bounding the solution to a particular TSP instance can be easy if we take advantage of its structure.

Here is my solution to the first part:
[Show Solution]

Here is my solution to the second part:
[Show Solution]

6 thoughts on “Pokémon Go Efficiency”

  1. It’s not easy to evaluate this without a computer, but one way to get a higher lower bound is to sum over all pairs the average of the distances to its two nearest neighbors (since every point needs to be connected to 2 other distinct points). I don’t have the exact number here, but that got me to about 709k.

    For the upper bound, any actual path will do. One example that comes fairly close to the LB above is to start at (1,1), go up the first column, then going down and up pairs of alternating columns (e.g. down cols 2/3, up 4/5, down 6/7, etc, then end by going down 998/999/1000 together) excluding the bottom row, then finally go back along the bottom row. Because many of the columns are fairly sparse, going up and down in pairs takes a lot less distance than going up and down each one (but groups of 3 or more columns seem to give too big a trade-off with extra over-and-back horizontally). That got me to an upper bound of about 735k.

    I can’t think of any way to get further than that without using a lot more computing power – but will be interested to see what you come up with! Thanks for another good solution.

    (Also, as a small niggle, I think you’ve got the bounding inequality for L*(M) the wrong way around!)

    1. Very nice! My upper bound isn’t as good as yours but I think my lower bound is better. I’m still working on the write-up. Should be done soon. Would you mind checking your numbers again? When I tried your suggestion of averaging the two nearest neighbors for each node, I got 643,811 instead of 709k. I’ll include both your solution and mine in the write-up, since that will give the best possible approximation ratio.

      1. Ah – what a shame… I thought the bounds seemed surprisingly close together, I guess I should have realized it was too close to be true! I don’t have the original file I did it in to hand, but yes, when I reran it, I got your value for the LB (643,811.507). Thanks for double-checking!

  2. Thanks for doing all this work! Are the curves straight if you use M^2 as the axis? I would guess that they are apart from a little steepening for M under 100 where coprimes get a bit more dense.

    The optimum for M=50 is 1773.05, which can be computed in a few seconds with MAOS:

    https://github.com/wiomax/MAOS-TSP

    So a reasonable bet is that the optimium for 1000 is a little less than 400 times that (709220). A little less because the coprimes are about 1% more dense for M=50 than for M=1000.

    My computer runs out of its 8G of memory by M=100, but it wouldn’t be too hard to compute and splice together 400 50×50 paths (or maybe 100 100×100 ones with a roomier computer) to get a rather tight upper bound.

Leave a Reply to Diarmuid Early Cancel reply

Your email address will not be published. Required fields are marked *