I posted this programming puzzle on Monday this week, and have received a solution in Fox Pro from Calvin Hsia, one in C# from Justin Rodgers, and one in C++ from Michael Scholz.  So we have 3 players using 3 different languages.  Cool!

 

I promised to post my own solution, and here you go.  I even threw in some analysis for free!

 

Of the 4 solutions, I like mine the most. :-)  OK, so I may be a Narcissist, but please read what I have to say first – you can decide afterwards.

 

1.     Overview of the data structure and algorithm

 

Like coding, problem-solving is often about abstraction: once you abstract away all irrelevant details, the solution becomes much more obvious.  This is how I tried to attack this problem: by first finding the essence of the problem.  I made the problem more formal by re-phrasing (excuse the pun) it as:

 

Given a sequence of n digits, find all the ways to represent it using a sequence of words.

 

Note that the original problem allows digits in the result, while the above simplification allows only words.  Rest assured that there is no loss of generality though: we can simply add the 10 digits to our vocabulary list and count them as words.

 

Next, I observed that once we fix the first word w in the result sequence, we only need to solve the same problem on a smaller scale:

 

Given a sequence of n-k digits, where k is the length of w, find all the ways to represent it using a sequence of words.

 

When we have a solution to the smaller problem, we can just append it to w to get a solution to the original problem.  In fact, all solutions to the original problem can be obtained this way, by enumerating all possible w’s.

 

This divide-and-conquer strategy naturally lends itself to a recursive definition:

 

Let P(s) be the set of all valid ways to represent the digit sequence s with a sequence of words, and P1(s) be the set of all valid ways to represent s with a single word.  We have (the base case):

 

P( empty sequence ) = { empty sequence }

 

and when s is not empty (the inductive case):

 

          P( s ) = { w++p | s1 is non-empty, s1++s2 == s, w is in P1( s1 ) and p is in P( s2 ) }

 

(Here I’m using “++” for concatenation.)

 

Now, scroll up to the beginning of this section and read again.  Do this until you are convinced this is the right definition.  Or until you find an error (in this case, drop me a note).  If neither of these happens, I’m sorry I have confused you – let me know and I will happily refund you and try to explain it better.

 

Now that you’ve digested P( s ), we only need to find a way to calculate P1( s ).  Basically, this means given a digit sequence s, we want to find all the words that can single-handed represent s.  This suggests that we need a map from digit sequences to sets of words.  And that’s what I used to represent the word list.  I call it the WordMap in my program.

 

With this WordMap, we don’t need to enumerate all possible source strings that correspond to a phone #, as Calvin and Scott’s solutions do.  Instead, we only generate valid source strings.  This is much more efficient.

 

Calvin’s program treats different ways for dividing a digit sequence as different phrases (so “1-2-3-4” and “123-4” are considered different phrases).  I believe this is undesirable and hence don’t generate those otherwise identical entries.  This also improves the efficiency a lot without sacrificing clarity.

 

Michael took a similar approach and also expressed his algorithm using recursion.  However, his has one more level of loop surrounding the recursive call, and is more complex.  I believe his program’s efficiency and mine are comparable.

 

We now have a complete algorithm.  Bingo!

 

2.     Choice of the programming language

 

Next I need to implement the algorithm.  Unlike other contestants, who use Fox Pro, C#, and C++, my favorite programming language is a functional language called Haskell.  (“What the heck is that?”  Don’t worry.  I’ll walk you through my code and hopefully you’ll start to appreciate Haskell afterwards.)

 

I chose Haskell for its ability to abstract – it allows me to express ideas at a high level, as if I’m explaining them to an intelligent person, as opposed to explaining to a machine that seems more interested in low-level details.  As a result, Haskell programs are often much shorter (an order of magnitude for large programs) than those written in C++, and therefore easier to maintain.

 

My program contains 53 non-blank lines, shorter than Calvin’s 100-line Fox Pro, Justin’s 140-line C#, and Michael’s 120-line C++.  If you don’t count I/O and typedefs, my core logic is just 22 lines.  Now try to beat that. :-)

 

In fact, I could’ve made my code even shorter (and clearer to a functional programmer), but then an unprepared audience will have a harder time understanding it.  Therefore what I have now is a compromise.  Still, I hope it can convince you of Haskell’s abstraction power!

 

Of course, fewer lines don’t always lead to clarity (APL and Perl are known for capable of producing short but cryptic programs).  However, I do believe my version contains less low-level details and is thus easier to understand – given that you are willing to learn a little about Haskell.

 

3.     Source code

 

The complete Haskell source code is here:

 

import Data.Set

import Char

import List

import IO

 

------------------------------------------------------------

-- Some friendly type synonyms

 

type Digit   = Int

type Word    = String

type Phrase  = [Word]

type WordMap = [Digit] -> Set Word

type Phraser = WordMap -> [Digit] -> [Phrase]

 

------------------------------------------------------------

-- Hash utilities

 

-- The characters on each key in a telephone keypad

keypad = [ "0",     "1",     "2abc",  "3def",  "4ghi"

         , "5jkl",  "6mno",  "7pqrs", "8tuv",  "9wxyz" ]

 

-- Converts a character to its corresponding digit in the keypad.

charHash :: Char -> Digit

charHash ch = case findIndex (elem (toLower ch)) keypad of

                Just i  -> i

                Nothing -> -1

 

-- Converts a String to its corresponding digit sequence.

strHash :: String -> [Digit]

strHash str = map charHash str

 

------------------------------------------------------------

-- Constructing a WordMap

 

-- Reads a list of Words from the word list file.

readWords :: IO [Word]

readWords = do h <- openFile "words.txt" ReadMode

               contents <- hGetContents h

               return (words contents)

 

-- Inserts a Word into a WordMap.  Returns the updated WordMap.

insertWord :: Word -> WordMap -> WordMap

insertWord word wordMap ds =

  let oldWords = wordMap ds in

    if ds == strHash word

         then addToSet oldWords (map toLower word)

         else oldWords

 

-- Converts a list of Words to a WordMap.

wordsToMap :: [Word] -> WordMap

wordsToMap words = foldr insertWord emptyWordMap (digitWords ++ words)

  where emptyWordMap :: WordMap

        emptyWordMap ds = emptySet

 

        digitWords :: [Word]

        digitWords = [show i | i <- [0..9]]

 

-- Reads a WordMap from the word list file.

readWordMap :: IO WordMap

readWordMap = do words <- readWords

                 return (wordsToMap words)

 

------------------------------------------------------------

-- Pretty printer

 

-- Capitalizes the first letter in a word

cap1 :: Word -> Word

cap1 "" = ""

cap1 (x:xs) = toUpper x : map toLower xs

 

-- Prints a Phrase

showPhrase :: Phrase -> String

showPhrase p = concat (map cap1 p)

 

-- Prints a list of Phrases

showPhrases :: [Phrase] -> String

showPhrases ps = concat (intersperse "\t" (map showPhrase ps))

 

------------------------------------------------------------

-- Core algorithm

 

-- Finds all possible ways to phrase a digit sequence

allPhrases :: Phraser

allPhrases wordMap [] = [[]]

allPhrases wordMap ds = [ w : ph | i  <- [1..length ds]

                                 , w  <- setToList (wordMap (take i ds))

                                 , ph <- allPhrases wordMap (drop i ds) ]

 

-- Runs a Phraser with a phone number

run :: Phraser -> String -> IO ()

run phraser num = do wordMap <- readWordMap

                     let ps = phraser wordMap (strHash num)

                     putStrLn ("There are " ++ show (length ps) ++ " solutions:")

                     putStrLn (showPhrases ps)

 

As can be seen from the in-code comments, the code is divided into the following sections:

 

  • Type definitions
  • Utilities for calculating the corresponding digits (I took the liberty of calling it the Hash, abusing the term) of a text string
  • Input: constructing a WordMap from the word list file
  • Output: a pretty printer for phrases
  • The core algorithm: calculating and printing the result

 

Since I anticipate most of the readers are not familiar with Haskell, I’ll give an almost line-by-line explanation on the code.

 

Let’s start with the type definitions.

 

3.1             Type definitions

 

type Digit   = Int

type Word    = String

type Phrase  = [Word]

type WordMap = [Digit] -> Set Word

type Phraser = WordMap -> [Digit] -> [Phrase]

 

By giving friendly and informative synonyms to types, we can make the code more self-documenting – the reader can tell the purpose of a variable by just looking at its type.

 

The first couple of them are simple: we represent a Digit by an Int, and a Word is just a String.

 

A Phrase is a sequence of Words.  In Haskell, [] is the list type constructor, and hence [Word] means “a list of Words”.  It’s like list< Word > in C++.

 

The only interesting operation we want to do with the vocabulary list (other than constructing it) is to look up which words match a given digit sequence.  Hence we define WordMap as a function from [Digit] to a set of Words.  You may have figured out that “->” means function, and Set Word is like set< Word > in C++.

 

Finally, a Phraser is something capable of generating all possible phrases for a given phone number, using a WordMap as reference.  Hence it’s defined as a function from a WordMap and a digit sequence (the phone number) to a list of Phrases.  Note that in Haskell two arrows are used for a function type that has two parameters.

 

3.2             Hash utilities

 

keypad defines which letters fall on which keys.  It is a list of Strings:

 

-- The characters on each key in a telephone keypad

keypad = [ "0",     "1",     "2abc",  "3def",  "4ghi"

         , "5jkl",  "6mno",  "7pqrs", "8tuv",  "9wxyz" ]

 

charHash finds the Hash (i.e. corresponding digit) of a character.  It does this by finding the index of the element of keypad that contains this character.  If no index is found, -1 is returned, meaning that this character is not in the keypad.

 

-- Converts a character to its corresponding digit in the keypad.

charHash :: Char -> Digit

charHash ch = case findIndex (elem (toLower ch)) keypad of

                Just i  -> i

                Nothing -> -1

 

:: is used to declare the type of an identifier.  Is this case, we are saying that charHash is a function from Char to Digit.  Type declaration is usually not necessary in Haskell, as the compiler can infer the type for you most of the time.  However, it is good documentation to provide your types.

 

Note that in Haskell function applications do not need the parentheses.  So instead of charHash( ch ), you just say charHash ch.

 

strHash finds the Hash of a String (i.e. the list of digits corresponding to that String) by calculating the Hash of each character in the String and putting the result in a list.  Note in Haskell we don’t need an iterator or a loop to do that: map takes a function and applies it to every element of a list (What happens to the original list?  Nothing.  It is untouched and map will return a new list to hold the result).  It’s kind of like foreach in C#, but more abstract.

 

-- Converts a String to its corresponding digit sequence.

strHash :: String -> [Digit]

strHash str = map charHash str

 

3.3             Input

 

readWords opens the word list file, reads its contents, and splits them into a list of Words (consecutive non-blank characters).  The IO in the type just means readWords needs to do some I/O action.  This is Haskell’s way of reminding you that this function might have side effects.

 

readWords :: IO [Word]

readWords = do h <- openFile "words.txt" ReadMode

               contents <- hGetContents h

               return (words contents)

 

We construct the WordMap by inserting Words into it, one at a time.  Hence the following function:

 

-- Inserts a Word into a WordMap.  Returns the updated WordMap.

insertWord :: Word -> WordMap -> WordMap

insertWord word wordMap ds =

  let oldWords = wordMap ds in

    if ds == strHash word

         then addToSet oldWords (map toLower word)

         else oldWords

 

Remember that WordMap is a function from [Digit] to Set Word?  insertWord is actually accepting a function as parameter and returns another.  This is called higher-order functions.  As C# version 2 makes delegates and anonymous methods easier to use, you can expect to see C# programmers starting to use higher-order functions (at least good C# programmers :-) ).

 

Then we can construct the entire WordMap by adding a whole list of Words into it:

 

-- Converts a list of Words to a WordMap.

wordsToMap :: [Word] -> WordMap

wordsToMap words = foldr insertWord emptyWordMap (digitWords ++ words)

  where emptyWordMap :: WordMap

        emptyWordMap ds = emptySet

 

        digitWords :: [Word]

        digitWords = [show i | i <- [0..9]]

 

Again there is no loop here: foldr does that for you and hides the details.  This is what I was talking about: (unnecessary) low-level details don’t belong in a program!

 

The where clause was used to introduce local definitions.

 

3.4             Output

 

I wrote a mini pretty printer for Phrases.  Instead of inserting “-” between two words, I decide to just capitalize the first letter of each word.  This way, all entries are printed with the same width, and are much easier on the eyes (to me at least).

 

-- Capitalizes the first letter in a word

cap1 :: Word -> Word

cap1 "" = ""

cap1 (x:xs) = toUpper x : map toLower xs

 

cap1 is defined by pattern matching: If the input is empty, then the output is also empty.  Otherwise suppose the first character in the input is x, and the rest of the input is a String xs, we just turn x into upper case and everything in xs into lower case.  x:y means a list whose head is x and the remainder is y.

 

Given a Phrase (a list of Words) p, we show it by properly capitalizing each Word in p (that’s what map cap1 p does) and concatenating the results:

 

-- Prints a Phrase

showPhrase :: Phrase -> String

showPhrase p = concat (map cap1 p)

 

Given a list of Phrases, we show it by separating the elements with TAB:

 

-- Prints a list of Phrases

showPhrases :: [Phrase] -> String

showPhrases ps = concat (intersperse "\t" (map showPhrase ps))

 

3.5             Core algorithm

 

Now comes the exciting stuff.  allPhrases is the function for calculating all possible ways to phrase a digit sequence (remember that Phraser is a synonym of (WordMap -> [Digit] -> [Phrase]).

 

-- Finds all possible ways to phrase a digit sequence

allPhrases :: Phraser

allPhrases wordMap [] = [[]]

allPhrases wordMap ds = [ w : ph | i  <- [1..length ds]

                                 , w  <- setToList (wordMap (take i ds))

                                 , ph <- allPhrases wordMap (drop i ds) ]

 

Compare this piece of code with our informal definition of P( s ) shown earlier:

 

P( empty sequence ) = { empty sequence }

P( s ) = { w++p | s1 is non-empty, s1++s2 == s, w is in P1( s1 ) and p is in P( s2 ) }

 

Do we see the correspondence?  It’s pretty clear to me.  This is what I love about Haskell most: being able to produce high-level code close to your algorithm description!

 

The last thing is to hook up I/O with the core algorithm:

 

-- Runs a Phraser with a phone number

run :: Phraser -> String -> IO ()

run phraser num = do wordMap <- readWordMap

                     let ps = phraser wordMap (strHash num)

                     putStrLn ("There are " ++ show (length ps) ++ " solutions:")

                     putStrLn (showPhrases ps)

 

4.     Sample runs

 

To phrase a phone # foo, just execute run allPhrases “foo.  For example,

 

run allPhrases "6423946369"

 

gives you:

 

There are 160 solutions:

6423946369      6423946Do9      6423946Fox      642394Of69      64239I6369

64239I6Do9      64239I6Fox      64239IOf69      64239Go369      64239GoDo9

64239GoFox      64239In369      64239InDo9      64239InFox      6423Who369

6423WhoDo9      6423WhoFox      6423Wind69      6423Wine69      6423Window

64A3946369      64A3946Do9      64A3946Fox      64A394Of69      64A39I6369

64A39I6Do9      64A39I6Fox      64A39IOf69      64A39Go369      64A39GoDo9

64A39GoFox      64A39In369      64A39InDo9      64A39InFox      64A3Who369

64A3WhoDo9      64A3WhoFox      64A3Wind69      64A3Wine69      64A3Window

64Be946369      64Be946Do9      64Be946Fox      64Be94Of69      64Be9I6369

64Be9I6Do9      64Be9I6Fox      64Be9IOf69      64Be9Go369      64Be9GoDo9

64Be9GoFox      64Be9In369      64Be9InDo9      64Be9InFox      64BeWho369

64BeWhoDo9      64BeWhoFox      64BeWind69      64BeWine69      64BeWindow

6I23946369      6I23946Do9      6I23946Fox      6I2394Of69      6I239I6369

6I239I6Do9      6I239I6Fox      6I239IOf69      6I239Go369      6I239GoDo9

6I239GoFox      6I239In369      6I239InDo9      6I239InFox      6I23Who369

6I23WhoDo9      6I23WhoFox      6I23Wind69      6I23Wine69      6I23Window

6IA3946369      6IA3946Do9      6IA3946Fox      6IA394Of69      6IA39I6369

6IA39I6Do9      6IA39I6Fox      6IA39IOf69      6IA39Go369      6IA39GoDo9

6IA39GoFox      6IA39In369      6IA39InDo9      6IA39InFox      6IA3Who369

6IA3WhoDo9      6IA3WhoFox      6IA3Wind69      6IA3Wine69      6IA3Window

6IBe946369      6IBe946Do9      6IBe946Fox      6IBe94Of69      6IBe9I6369

6IBe9I6Do9      6IBe9I6Fox      6IBe9IOf69      6IBe9Go369      6IBe9GoDo9

6IBe9GoFox      6IBe9In369      6IBe9InDo9      6IBe9InFox      6IBeWho369

6IBeWhoDo9      6IBeWhoFox      6IBeWind69      6IBeWine69      6IBeWindow

6Ice946369      6Ice946Do9      6Ice946Fox      6Ice94Of69      6Ice9I6369

6Ice9I6Do9      6Ice9I6Fox      6Ice9IOf69      6Ice9Go369      6Ice9GoDo9

6Ice9GoFox      6Ice9In369      6Ice9InDo9      6Ice9InFox      6IceWho369

6IceWhoDo9      6IceWhoFox      6IceWind69      6IceWine69      6IceWindow

Nice946369      Nice946Do9      Nice946Fox      Nice94Of69      Nice9I6369

Nice9I6Do9      Nice9I6Fox      Nice9IOf69      Nice9Go369      Nice9GoDo9

Nice9GoFox      Nice9In369      Nice9InDo9      Nice9InFox      NiceWho369

NiceWhoDo9      NiceWhoFox      NiceWind69      NiceWine69      NiceWindow

 

This is all cool, except that the list contains so many entries with many numbers in it.  No problem, given an arbitrary Phraser, we can easily restrict it by filtering the result it produces.  Behold the power of higher-order functions (in C#, these are functions that take delegates as parameters or return delegates):

 

-- Restricts a Phraser by a predicate

restrict :: (Phrase -> Bool) -> Phraser -> Phraser

restrict pred phraser = \wordMap ds ->

    filter pred (phraser wordMap ds)

 

Now suppose we are only interested in phrases that contain no more than 2 digits.  We just define a predicate that tells us if a phrase satisfies this test:

 

atMost2Digits :: Phrase -> Bool

atMost2Digits ph = length (filter isDigit (showPhrase ph)) <= 2

 

Then we can use this predicate to restrict the original Phraser.  For example,

 

run (restrict atMost2Digits allPhrases) "6423946369"

 

gives us:

 

There are 24 solutions:

64BeWhoFox      64BeWindow      6IA3WhoFox      6IA3Window      6IBe9GoFox

6IBe9InFox      6IBeWhoDo9      6IBeWhoFox      6IBeWindow      6Ice9GoFox

6Ice9InFox      6IceWhoDo9      6IceWhoFox      6IceWindow      Nice9I6Fox

Nice9GoDo9      Nice9GoFox      Nice9InDo9      Nice9InFox      NiceWhoDo9

NiceWhoFox      NiceWind69      NiceWine69      NiceWindow

 

Isn’t this modular?

 

5.     Ways to optimize

 

How would I go about optimizing my program?  First let’s see where the time is spent.  In this algorithm, most of the time the program is either updating the word map or looking up from it.  In this simple implementation, inserting to the word map is an O(1) operation, which is good.  However, looking up takes O(n) time, where n is the number of keys in the map.  This seriously impedes the performance.

 

I have two ideas for reducing the complexity, both not difficult to implement.  The first is to change the implementation of WordMap from a function to a Hash table, that will make both inserting and looking-up nearly O(1) (assuming a good Hash function).  This alone should dramatically speed things up.

 

My second idea goes further and uses a trie instead of a Hash.  This would yield guaranteed O(1) access time.  It will also cut down the space footprint because keys share storage in a trie.  (To find out the details, read more about the trie data structure here.)

 

Both optimizations will make the code look more complex, but not very much.

 

6.     What has Microsoft got to do with functional programming?

 

Well, there are some eminent functional programmers at Microsoft, including Eric Meijer and Wolfram Schulte, who designed the much anticipated Xen programming language together.  More to the point, Xen (rumors are that it’s called X omega now) incorporates a lot of cool ideas from functional programming to C# in order to support seamless programming of XML, SQL, and objects.

 

The next version of C# (the one in Whidbey) was also influenced by functional programming.  One example is the addition of anonymous methods.

 

And, the most widely used Haskell compiler is called GHC, which is freely available and supported (among others) by researchers at Microsoft Research, Cambridge.