My own solution to my programming challenge


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.

Comments (19)

  1. senkwe says:

    VERY nice. I was halfway with my own C++ based solution just now but since I’ve looked at your algorithm and code, I’m too tainted to even continue 🙂

  2. Tene says:

    Functional language are cool, but can you give us any idea about actual performance?

  3. the1 says:

    Dear Tene,

    The performance is not bad at all. It took a couple of seconds to find the 160 solutions in my example. What matters is the complexity of the algorithm. With the optimization I proposed, the performance can still be drastically improved.

  4. Tene says:

    Thanks for your reply, is there a chance to get a more precise idea of what give haskell against C++ or C#?

    I mean "a couple of seconds" on an unknown system is a bit short to get an idea of the perf 😉

    Another interresting aspect is how "unreadable" become optimized code?

  5. the1 says:

    Dear Tene,

    It’s not easy to give a short answer to your questions. I suggest you check out this guide: http://homepages.inf.ed.ac.uk/wadler/guide.html.

  6. Jake Good says:

    I came up with a similar (divide and conquer) algorithm… but with a few different optimizations (sort-of)…

    Using regular expressions , I created a small lookup table… of the word – word in numbers – weight (length of word).. At the same time, I also checked to see if the word as a number was in the original number.. this created an incredibly smaller set of words to check. A filter basically. Take care of the larger O(n) sequence FIRST and then you only have to iterate an O(n) on a considerably smaller set. THEN I divided into

    (head) (found sequence) (tail) recursion route.. and by ALSO filtering the small table by weight, it created an even smaller subset, and in a lot of cases, eliminated the candidates completely…

    I havent compiled this as I am OOF and dont have a compiler handy (:: sigh ::)

    The trick is dealing with the head and tail having multiple matches that converge on the found sequence. But I think it lends to an efficient algorithm.. especially if you want to run several numbers over the same word set.

    Is there something wrong with my crazy thinking? 🙂 I welcome suggestions…

    jake *(@)* developstuff.com

    Jake

  7. CalvinH [MS] says:

    I’ve posted my optimized version of the solution <a href=http://blogs.msdn.com/vsdata/archive/2004/04/05/107986.aspx&gt; here</a> and I’ve also made <a href=http://calvinh6/PhoneNumber.asp>a web page</a> from which you can enter a phone number or sequence of letters to run the algorithm and see the results.

  8. CalvinH [MS] says:

    (fixed urls)

    I’ve posted my optimized version of the solution http://blogs.msdn.com/vsdata/archive/2004/04/05/107986.aspx and I’ve also made a web page http://calvinh6/PhoneNumber.asp from which you can enter a phone number or sequence of letters to run the algorithm.

  9. Nicholas Allen says:

    I was reading over the solutions today and found the variety interesting. The Haskell method was very well done and really showed off the language well. Some of the great features of functional languages like lambda and apply are starting to appear in C-like languages so maybe one day everyone will be able to solve problems like this so pithily 🙂

    Since I had a JavaScript solution written previously I thought I’d share it. It’s amazing how many languages JS borrowed from in addition to Java. My solution uses a trie which I think was done fairly simply. It’s a bit shorter than even the Haskell.

    http://gnida.cs.vt.edu/~nallen/phone_number.js.txt

    Note: to actually run this you’ll need a JS interpreter that can handle files, such as Rhino.

  10. Just to give some background, the C# implementation takes on the order of 200 ms to find all 160 solutions (actually more because I expanded my dictionary, the original contest had nice-win-fox as a result, so I added win to the dictionary and another I believe), and only a slightly longer amount of time to parse the results down based on the maxDigits calculation.