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