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.
