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:
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:
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:
(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:
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
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:
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.
:: 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.
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.
We construct the WordMap by inserting Words into it, one at a time. Hence the following function:
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:
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.
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).
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:
Given a list of Phrases, we show it by separating the elements with TAB:
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]).
Compare this piece of code with our informal definition of P( s ) shown earlier:
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:
4. Sample runs
To phrase a phone # foo, just execute run allPhrases “foo”. For example,
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):
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,
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,