{"id":970,"date":"2016-08-14T18:43:22","date_gmt":"2016-08-14T23:43:22","guid":{"rendered":"http:\/\/www.laurentlessard.com\/bookproofs\/?p=970"},"modified":"2016-10-08T14:31:22","modified_gmt":"2016-10-08T19:31:22","slug":"pokemon-go-efficiency","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/pokemon-go-efficiency\/","title":{"rendered":"Pok\u00e9mon Go Efficiency"},"content":{"rendered":"

This Riddler puzzle<\/a> is about a topic near and dear to many hearts: Pok\u00e9mon!<\/p>\n

\nYour neighborhood park is full of Pok\u00e9stops \u2014 places where you can restock on Pok\u00e9balls to, yes, catch more Pok\u00e9mon! You are at one of them right now and want to visit them all. The Pok\u00e9stops are located at points whose (x, y) coordinates are integers on a fixed coordinate system in the park.<\/p>\n

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

You\u2019re an ambitious and efficient Pok\u00e9mon trainer, who is also a bit of a homebody: You wish to visit each Pok\u00e9stop 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 \u2014 you\u2019re not confined to the coordinate system\u2019s grid. It turns out that this is a really hard problem, so you seek an approximate solution.<\/p>\n

If there are N Pok\u00e9stops 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.)<\/p>\n

Advanced extra credit: For solvers who prefer a numerical question with this theme, suppose that the Pok\u00e9stops 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.\n<\/p><\/blockquote>\n

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

Here is my solution to the first part:
\n[Show Solution]<\/a><\/p>\n

\n

To clarify, we know there are $N$ Pok\u00e9stops but not how they are arranged. The question asks us to find the smallest and largest possible value for the minimum tour that visits each Pok\u00e9stop and returns to the starting point.<\/p>\n

Upper bound<\/h3>\n

The worst-case arrangement of Pok\u00e9stops is to have them lie in a line, which leads to a path length of $2(N-1)$. Proving that this is indeed the worst possible arrangements of stops is a bit more involved, so read on if you’re interested.<\/p>\n

Let $T$ be a minimum spanning tree<\/a> for the set of Pok\u00e9stops. Any tree with $N$ nodes has $N-1$ edges, so $T$ has $N-1$ edges. It also follows from the adjacency property of Pok\u00e9stops that each edge of $T$ must have length $1$. One way to visit all the nodes is by using a depth-first tree traversal<\/a>:<\/p>\n