Programming Challenge: A Capital Idea!

In the last Purdue Perl Mongers meeting, Mark suggested a challenge. Going from state capital to state capital of the "lower 48" (no Alaska, no Hawaii) , without skipping one and without repeating one, what are the longest and shortest distances. We guessed without knowledge, and then, after the meeting was over, we started working on it.

As you may know, this is a restatement of the Travelling Salesman problem and as such is NP-Hard. There are, in this case, 48! possible answers.

My immediate thought was to specify the most extreme unused distance for each capital, longest or shortest, depending. I also thought to start at Maine, seeing as it's the furthest out of all the state capitals.



You should be able to see some problems. For example, Arizona wasn't the shortest choice until it was the last choice. I'm not remotely happy with the Midwest and New England sections, either. So the fastest choice of algorithm wasn't the best choice. Running the naive longest-path against each state showed that Tennessee and Kentucky were the best starting point, which shocked the heck out of me.

I added some code to pick the closest n and recurse through those, and that cleared up the Arizona problem quickly, but it will take a lot of redoing to get it to back up to the Tennessee-to-Michigan jump, much less the New England jumble. Considering a quick read-through of threading modules, which could help me get through my too-many-possibilities, but also considering ways to rethink this as a breadth-first problem.

I'm also seriously considering just making a web interface and solving it myself. I can't be sure it's the best possible, but I can vgrep for issues and optimizations.