Here is a puzzle that NPR broadcast in November 2010.
What two world capitals can be found by rearranging the letters in the phrase “serial number.”
Being the programmer I claim to be, I wanted to write a program that finds the answer given the list of capitals. Let’s try TDD (test driven development). Given a suggested solution X and Y how do you verify by means of a program that the suggestion is indeed correct. The verifier’s problem is: given two sets of characters verify that the two sets are identical. Stated that way the problem is one of matching two sets. In this case we know that the domain of discourse, the set of alphabets is finite and can be linearly ordered (sorted in layman’s terms). Hence we can sort all the characters in “serial number”, sort the characters that are found in the string, X concatenated with Y and now compare two sorted arrays. In pseudo-code
Normalise ( X )
let Y = ToLower( X) // convert all characters to lower case
return Sort ( Y)
Verify ( X , Y)
W = Normalise ( X ^ Y)
Z = Normalise (“serialnumber”)
return (W == Z) // assume we have a comparison operator
Now that we have a way of verifying the solution, all that we need to do to find a solution the original problem is to collect all possible pairs of capitals and ‘verify’ the suggested solution.