Want to prove that you are the best programmer money can buy? (OK, I know you are not for sale, but your boss may need a friendly reminder that it’s time for your next big raise.) Here’s your chance:
On a telephone keypad, the number keys 2 — 9 also carry letters on them (see the picture below). Your task is to write a program that finds all possible ways to phrase a phone number. By “phrase” I mean using a mixture of numbers and English words to spell out the number. For example, the number 642-394-6369 can be phrased as nice-window, nice-wind-ox, nice-win-fox, nice-9-in-fox, etc.
Your input includes a list of English words, as well as the phone number as a sequence of digits. For testing your program, you can use a basic English word list I found here.
The merit of an entry will be judged mainly by how clear the code is, not necessarily the efficiency. You can choose your favorite programming language, as long as it gets the job done (If it’s not a widely known language, you probably want to make sure the code is self-documenting, so other people can understand why your code is so cool).
I will post my own solution in several days. (In case you are wondering, it is not in C++.)