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