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

//helper

`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.

### Like this:

Like Loading...

*Related*

## About The Sunday Programmer

Joe is an experienced C++/C# developer on Windows. Currently looking out for an opening in C/C++ on Windows or Linux.