More on the Hamiltonian Plumber

This Sunday, I've launched a website with the goal of learning about good testcases that break a heuristic solution for a decisive TopCoder Open problem that can be reduced to Traveling Salesman: http://hamiltonianplumber.appspot.com/

So far, nobody except myself has submitted a testcase that makes the solution do at least two iterations — in other words, greedy improvement works in all submitted testcases. This is quite disappointing, so I'm wondering what's the reason for that. It could be:

1. The challenge is not interesting enough, so people either don't bother at all or try a few manual tests.
2. The website is confusing, so people don't understand what's really going on.
3. The website is broken, so people submit good testcases but they are scored incorrectly.
4. Something else? Please share what you don't like about the challenge!

Let me also share a simple strategy that allows to get a score higher than 1.0. It's actually quite straightforward - we can just try random big tests until we find one that scores more than 1.0. One might need to try several tests before that happens, and doing that using the website is slow and clumsy. However, the website actually has the code available for download (http://hamiltonianplumber.appspot.com/source.html), so one can quickly craft a local stress-test and find a case that requires many attempts. Since you don't know the hidden random seed, a testcase that requires two attempts on your machine might still be solvable in one on the server, but if you find a testcase that needs ten attempts, chances are your score on the server will be more than 1.0, too.

Tweet