# Hamming distance traveling salesman problem

The Hamming distance between two strings is the number of positions they differ at.
You are given a set of binary strings. The task is to find the length of the shortest route that visits all of them at least once and ends where it started, in a metric space where the distance between two strings is the Hamming distance between them.

Let $$\N\$$ be the number of input strings and the string length. There are 3 test cases for every $$\N\$$. The strings are created from random bits obtained from an acceptable random number generator. A RNG is acceptable if I can replace it with a RNG I like more without significantly affecting the program's performance.

A program's score is the largest $$\N\$$ it can correctly solve all 3 tests for within 60 seconds. The higher the score, the better. Answers with equal scores are compared by posting time (older answer wins).
Submissions will be timed on a PC with an (12-thread) AMD Ryzen 2600 CPU and a (cheap but relatively modern) AMD Radeon RX 550 GPU.

Programs must solve tests in order - that is, they must output the answer for the current test before generating the next one. This is unobservable, but it could be made observable at the cost of simple IO requirements (imagine me supplying an external RNG that asks you for the outputs).

This problem is proven NP-complete. Short explanation of the proof: take rectilinear ($$\|\Delta x| + |\Delta y|\$$) integer TSP and replace $$\x\$$ by a string with $$\x\$$ ones and $$\[\text{something}] - x\$$ zeroes, same for $$\y\$$; repeat strings until their count is equal to their length.

• Deleted sandbox post Commented Apr 26, 2020 at 11:03
• You should ask for programs that take input and provide a specific RNG with a fixed seed, rather than just asking us to imagine that you did so. Like most NP-complete problems, TSP has easy cases and hard cases, and you don’t want programs to win just because they are lucky. Commented Apr 27, 2020 at 6:46
• I am interested in programs that perform the best in the average case, so I use 3 random test cases and mention that you must use a proper RNG. Commented Apr 27, 2020 at 8:00
• You will not get what you're interested in with a vague criterion like that. If answers can choose between a wide variety of RNGs and seeds, then submitters will be encouraged to re-run their program zillions of times until they find a favorable one. Or they will submit a non-deterministic program whose results can't be reproduced. You might decide that some of these break the rules, but it's really unclear where to draw the line. On the other hand, if you just specify a generator with a fixed seed, everything is clear and you'll get a better approximation of average behavior. Commented Apr 27, 2020 at 18:31
• I can't see how that is vague. Commented Apr 28, 2020 at 0:48