A dropped digit

The original results recorded a best route of 1257 on swiss42. The published optimum for swiss42 — proven, decades ago — is 1273.

Nothing can beat a proven optimum. If your program does, your program is not measuring what you think it is measuring. So one of those two numbers had to be wrong, and it was not the one that had been independently verified for thirty years.

The distances between cities are stored as a table — a grid where the entry in row 25, column 9 is the distance from city 25 to city 9. For this problem that grid holds 1,764 numbers, and they were typed in by hand from a reference file.

Two properties should hold. The distance from A to B should equal the distance from B to A, so the grid should be symmetric. And it should match the reference. Checking both takes about ten lines of code, and turns up exactly one problem:

asymmetric pairs: 1 of 861
  [25][9] = 5   vs   [9][25] = 65

cells differing from reference: 1 of 1764
  [25][9]  repo=5  reference=65

One cell. A 6 lost while typing, turning 65 into 5. It is the only asymmetric cell in an otherwise perfectly symmetric grid, which is precisely what makes it findable — and the other two problems, bayg29 and brazil58, transcribe perfectly across all 841 and 3,364 cells.

The scoring code reads distance_matrix[from][to] — it looks up the direction it is actually travelling. So any route that happens to drive from city 25 to city 9 gets charged 5 for a leg that really costs 65, and comes out 60 short.

The algorithm has no idea this is a mistake. It is doing exactly its job: hunting for cheap routes. It found a leg that was accidentally free and used it in every good route it produced.

Running a strong local search over the table as stored bottoms out at 1255. Repair that single cell and the same search bottoms out at 1273 — exactly the published optimum, to the digit. That match is the proof: with the typo fixed, the data is provably correct, and the impossible result disappears.

It is visible in the original program's own output, too. A run today returns a best route containing the sequence … 11, 25, 9, 29 … — city 25 straight to city 9, collecting the discount.

Open the demo, pick swiss42, and switch the distance table to as stored. The route length drops below the amber optimum line on the chart. That is the bug, on screen.

The code in this repository is left exactly as it was written, typo included, because the bug is more useful as evidence than as an embarrassment. Reading it back, five things stand out — less as mistakes than as the habits the intervening years replaced.

Validate the data before trusting the result

A one-line symmetry check would have caught this immediately. Beating a published optimum should read as a red flag, not a result. Assert what you believe about your inputs, then measure.

Seed the randomness

Nothing in the original fixes a random seed, so no individual figure can be reproduced exactly — only its distribution. The demo on this site seeds every run for that reason.

Do not write the log inside the loop

The logging code rewrites its entire CSV file every single generation. That one line dominates the runtime: 20 runs take about 200 seconds in Python against 5 seconds for the same work in the browser, and most of that gap is file writing, not language speed.

Pass dependencies explicitly

The route class defaults its distance table to swiss42, and the main loop leans on that default when building children — so an experiment on bayg29 is quietly scored against Switzerland. A required argument would have made that impossible to write.

Report reliability, not just the best number

The success-rate table is the most useful result in the whole study, and it was reported last. It changes which operator you would choose.