The Pokémon Go Trainer’s Round Trip

A park holds $N$ Pokéstops at points with integer coordinates. The stops are connected in the sense that you can walk from any stop to any other by hopping between stops exactly one unit apart. You want to visit every stop and return to where you started, over the shortest possible total distance, walking in straight lines between stops (you are not confined to the grid). Exact optimisation is hard, so instead find an upper and a lower bound on the length of the best route, in terms of $N$, with the two bounds as close to each other as you can make them.

The Riddler, FiveThirtyEight(original post)

Solution

The best route is a closed tour through the $N$ stops, and two simple observations trap its length from both sides.

Lower bound. A tour that visits $N$ distinct stops and returns to the start is a loop built from $N$ straight segments. Each segment joins two different points with integer coordinates, and the closest two such points can be is $1$ unit apart, so every segment is at least $1$ long. The whole loop is therefore at least $N$. This is achieved: when $N$ is even, place the stops in a rectangular ring two deep (for example, the points $(0,0),(1,0),\dots$ across and back), and the unit steps around the ring form a tour of length exactly $N$.

Upper bound. Because every pair of stops is joined by a chain of unit steps through stops, the stops carry a spanning tree made entirely of unit edges, of total length $N-1$. Walk that tree, tracing each edge once out and once back; you return to the start having travelled $2(N-1)$. The genuine optimal route can only be shorter, since wherever this walk would double back, replacing the detour with the straight segment to the next stop is no longer, by the triangle inequality. So the optimum is at most $2(N-1)$. This too is achieved: put all the stops in a straight line, and any route must reach the far end and come back, for $2(N-1)$, with no shortcut available.

Putting the two together, $$\boxed{\,N \;\le\; L \;\le\; 2(N-1)\,},$$ where $L$ is the length of the optimal route. These are the tightest bounds expressible through $N$ alone: the even ring drives any valid lower bound down to $N$, and the straight line pushes any valid upper bound up to $2(N-1)$, so no $N$-only bounds can have a ratio better than $2(N-1)/N$, which approaches $2$ as the park fills up.

The puzzle’s submitter framed the same trap through the minimum spanning tree. That tree has weight exactly $N-1$ here, a tree of $N-1$ edges each at least $1$, with unit edges achieving it, and any tour lies between the tree’s weight and twice it. That route gives $N-1 \le L \le 2(N-1)$; counting the loop’s own segments sharpens the lower end from $N-1$ to $N$.

Extra Credit

Now place a Pokéstop at every point $(x,y)$ with $x$ and $y$ relatively prime positive integers at most $1{,}000$. Find upper and lower bounds on the optimal round trip, again with their ratio as close to $1$ as possible.

Solution

First, how many stops there are. Counting the pairs $(x,y)$ with $1\le x,y\le 1000$ and $\gcd(x,y)=1$ gives $$N = 608{,}383,$$ which sits right at the expected density of coprime pairs, $6/\pi^2 \approx 0.6079$, times the $1000^2$ grid. The lower bound from the main part still holds: the round trip is a loop of $N$ segments each at least $1$ unit, so it is at least $608{,}383$.

The upper bound is where this part earns its “advanced” label. The clean $2(N-1)$ ceiling came from a spanning tree of unit edges, and that needs the stops to be connected by unit steps. The coprime stops are not: stepping one unit from a coprime point can land on a non-coprime point, and a search outward from $(1,1)$ reaches only $587{,}105$ of the $608{,}383$ stops. There is no unit-edge spanning tree, so $2(N-1)$ is not guaranteed, and pinning the upper end becomes the genuine travelling-salesman computation the puzzle was pointing at, the kind handled in practice by approximation such as the Christofides algorithm, which guarantees a tour within a factor $1.5$ of the optimum for straight-line distances. The honest summary: the optimal trip is at least $608{,}383$ units, and tightening the ceiling is the hard part the question was inviting you to appreciate rather than to close.

The computation

For the main bounds, solve small parks exactly by trying every route, and watch the two extremes hit $N$ and $2(N-1)$. For the extra credit, count the coprime stops exactly and test, by a flood fill, whether unit steps connect them.

import itertools, math
from math import gcd

def best_tour(points):
    p0, n = points[0], len(points)
    return min(
        sum(math.dist(order[i], order[(i + 1) % n]) for i in range(n))
        for order in ([p0] + list(rest) for rest in
                      itertools.permutations(points[1:]))
    )

line = [(i, 0) for i in range(6)]                 # collinear, N=6
ring = [(0,0),(1,0),(2,0),(2,1),(1,1),(0,1)]      # 2x3 loop, N=6
print("line :", round(best_tour(line), 3), " 2(N-1) =", 2 * (6 - 1))
print("ring :", round(best_tour(ring), 3), " N =", 6)

M = 1000
stops = {(x, y) for x in range(1, M + 1) for y in range(1, M + 1)
         if gcd(x, y) == 1}
N = len(stops)
seen, stack = {(1, 1)}, [(1, 1)]
while stack:
    x, y = stack.pop()
    for nb in ((x+1,y),(x-1,y),(x,y+1),(x,y-1)):
        if nb in stops and nb not in seen:
            seen.add(nb); stack.append(nb)
print("coprime stops N :", N)
print("unit-connected  :", len(seen) == N, f"({len(seen)} of {N})")
# line : 10.0  2(N-1) = 10
# ring : 6.0  N = 6
# coprime stops N : 608383
# unit-connected  : False (587105 of 608383)