Puzzling

First Pass

Most of my work these days is in C++, and while C++ doesn't have the world's best string manipulation facilities, I thought it had enough to do the job on this puzzle. Figuring that the problem was small enough to solve via brute force, I decided that the general course of the program would be to work my way through all 50*49/2 combinations of states, and test them against all 48*47/2 remaining combinations. That's just a little more than a million operations, which ought to be child's play. Thus, the basic program loop was going to look like this:

for ( int i = 0 ; i <49 ; i++ )
    for ( int j = i  + 1; j <50 ; j++ )
        for ( int m = 0 ; m <49 ; m++ )
            if ( m != i && m != j )
                for ( int n = m + 1 ; n <50 ; n++ )
                    if ( n != i && n != j )
                        //compare state i and j against state m and n

Still thinking brute force, I was looking for the simplest way to store the data so that it would be easy to compare, and turned to std::multiset. I knew that if I stored all the characters from states i and j in one std::multiset object, and all the characters from states m and n in another, I could quickly compare one against the other with a simple equality operator.

So in the above loop, I inserted these lines after the first two for statements:

std::multiset<char> label1;
char *p = states[ i ];
while (*p)
    label1.insert( *p++ );
p = states[ j ];
while (*p)
    label1.insert( *p++ );

(Note that I had snagged the names of the states from one of the first sites in a Google search, and inserted them into an array of character pointers called states.)

I inserted a similar definition for label2 inside the second set of two for statements, which means all I had left to do was a simple comparison of label1 against label2:

if ( label1 == label2 )
    std::cout <<states[ i ] <<", "
              <<states[ j ] <<", "
              <<states[ m ] <<", "
              <<states[ n ] <<"\n";

I did a quick compile, tested the code, and sure enough, the contents of the multisets were indeed sorted concatentations of the letters of each pair of states. Time to run!

My first disappointment was seeing that, while the program was indeed running properly, it was going slow enough that it looked like it was going to take a sizable fraction of an hour to make it through the entire alphabet. I could just wait, but in this case I decided I could optimize faster than it would take to wait for the first results.