“Serial Number”

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.

Advertisements

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.
This entry was posted in Software Puzzle and tagged , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s