Milk Run▶Play

Tap the stops in the order you will drive them and match the shortest possible round trip, counted in city blocks.

How to play

The square is the depot and the circles are stops. Tap the stops in the order you want to drive them, then press Deliver; the van returns to the depot at the end. Distance is counted in city blocks, so you travel along the streets and never diagonally. Each round shows a Par, which is the exact length of the shortest round trip that exists on that map, computed by search rather than estimated. Match it, or stay within the blocks of slack the round allows, and you clear the round; from round seven the slack is zero and only the true shortest route is accepted. After every round the optimal route is drawn in green so you can see what you missed. Each round adds a stop, tightens the slack and shortens the planning clock. Three failed rounds ends the game, and your score is the number of rounds you clear.

Tips & strategy

The reason this game has a Par at all is that the shortest route is not a matter of opinion. With a dozen stops the number of possible orders is in the hundreds of millions, but the true minimum can still be found exactly, and that is the number you are being measured against.

The method almost everyone starts with is to drive to the nearest stop you have not visited yet. It feels like the efficient thing to do and it is measurably not. Across hundreds of maps it comes out about two blocks long with five stops and close to six blocks long with twelve, and on the larger maps it lands on the true shortest route only about one time in six. Sweeping around the map in a circle is worse, roughly twice that penalty. Ordering the stops with no thought at all costs thirty to forty blocks.

Why does nearest-first fail? Because it spends its cheap moves first and leaves the expensive ones for the end. Each time you take the closest stop you are also deciding where you will be standing afterwards, and the stops you skipped do not disappear — they wait for you out on the edge of the map, and eventually you have to cross the whole city to collect one straggler. The last leg of a greedy route is almost always its longest.

So plan the loop, not the next step. Look at the map before you tap anything and find the outline: which stops sit at the extremes, and which way round the circuit is going to run. Then work inward, slotting the middle stops into the side of the loop they are already closest to. A stop that looks like a detour costs almost nothing if you collect it on the way past, and costs double if you have to come back.

Two habits pay for themselves. First, decide the direction of travel early — a route and the same route reversed are always the same length, so the only real question is which stops go on the outbound side and which on the return. Second, when you have a route, look for a crossing: if your path crosses itself, you can almost always shorten it by swapping the order of the two stops involved. Untangling crossings is the single easiest way to squeeze out the last block or two, and from round seven onward those last blocks are the whole game.