Programming Challenge: Phraser

  • Article

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++.)

 

Enjoy!

Comments

  • Anonymous
    March 29, 2004
    This is pretty similar to the programming problem that was used to compare Java to C/C++ (and later to Lisp) a few years ago:

    http://www.norvig.com/java-lisp.html

  • Anonymous
    March 29, 2004
    I didn't see you mentioning payment or a prize? Do you expect someone doing your job for free? :-)

  • Anonymous
    March 29, 2004
    Dear Joe,

    Thanks for the pointer! I wasn't aware that there was a similar contest. But we shouldn't let that take away the fun, should we? Let's try to beat Norvig!

    Dear Anonymous,

    By winning the contest, you gain unlimited bragging right. Didn't I also mention your boss's reaction? Come on, there is no excuse for not doing it. :-)

  • Anonymous
    March 30, 2004
    The comment has been removed

  • Anonymous
    March 30, 2004
    Dear Senkwe,

    Let's keep it simple. For now I don't care how many numbers you use in the phrase. The idea is to get ALL different ways to phrase your phone number. Additional constraints (e.g. 3 digits allowed at most) can aways be added later to filter the result. The principle of modular programming says we should do only ONE thing (and do it well) in one module.

  • Anonymous
    March 30, 2004
    OK, I have a question. When you say "how clear the code is", does the word code mean code only, or code and comment ? If I have the following two entries:

    *entry A: simple code without comment.
    *entry B: slightly more complex code than A, but it has a ton of comments to make it easier to understand.

    which entry is considered better in this contest ?



  • Anonymous
    March 30, 2004
    Dear B.Y.,

    You are really serious about this. :-) This is a contest for clear code. While good comments are important, they are not the focus. (Actually often I don't trust comments, because I've seen so many cases when they are out of sync with what the code really does -- programmers always update the code and forget to change the comments accordingly).

    Good code should be clear on itself and require few comments. Bad comments are worse than no comments at all. I hate people writing comments just for comments' sake, e.g.

    a++; // increase the value of a by 1

    In your example, A will be preferred -- as long as it can be easily understood without comment.

    Finally, I don't want to pretend being an authority on code clarity. There is no judge for this contest. :-) The whole purpose of this chanllenge is to have some fun and learn from each others' different angles of solving problems. (OK, I lied about the big raise, but if we learn something from this, it can be applied to get us closer to the raise.)

  • Anonymous
    March 30, 2004
    Here are some thoughts on comments: http://weblogs.asp.net/jaybaz_ms/archive/2004/03/22/94066.aspx

    If your code can't be understood without comments, then either add them or simplify. (Doing neither is bad!)

  • Anonymous
    March 31, 2004
    The comment has been removed

  • Anonymous
    March 31, 2004
    Dear Calvin,

    Wow, the first entry! Congratulations!

    You can either post the code here, or put it on your own blog (if you have one or want to create one) and provide a link.

    If you post it here, the format and indentation will be lost. :-( Let's see how it looks, and if necessary, you can email me (Zhanyong Wan) the code and I'll post it in its original format.

    Also, can you provide a link to your dictionary so others can also use it? Thanks!

  • Anonymous
    March 31, 2004
    Here's a link to the programming challenge solution on my blog. It also includes a link to the dictionary I used.

    http://blogs.msdn.com/vsdata/archive/2004/03/31/105159.aspx

  • Anonymous
    April 01, 2004
    The comment has been removed

  • Anonymous
    April 01, 2004
    And my algorithm isn't properly convergent either, so I'm not yet completed.

  • Anonymous
    April 06, 2004
    "Nice" isn't in the dictionary list that you provided.

  • Anonymous
    April 07, 2004
    The comment has been removed

  • Anonymous
    April 07, 2004
    The comment has been removed

  • Anonymous
    April 07, 2004
    Oh one more thing. In you original post you mentioned that there was 160 solutions for the number 6423946369 but my program returns 228 possible solutions. I have verified all the data am I missing something in my program? Anybody see an error, or was there an error with the original dataset?

  • Anonymous
    April 07, 2004
    Nick,

    Your result list is bigger because your word list contains "ox", which mine doesn't have.

  • Anonymous
    April 07, 2004
    Here is my entry to the challenge:

    http://zert.net/blog/2004/04/07/programming_challenge_phraser.html

  • Anonymous
    April 08, 2004
    Ah..

    That makes more sense, I had to add that to get one of the 4 results you had listed above.

  • Anonymous
    April 08, 2004
    Hey Mike,

    Nice easy solution to look at. But what dictionary did you use. Because the one I got off the site above doesn't seem to work. Well at least there seems to be a loop that never ends?

  • Anonymous
    April 09, 2004
    The comment has been removed

  • Anonymous
    September 11, 2007
    historic black colleges in atlanta ga

  • Anonymous
    November 11, 2007
    PingBack from http://foxpro.ntsl119.com/scr/archives/129

  • Anonymous
    June 01, 2009
    PingBack from http://paidsurveyshub.info/story.php?id=28338

  • Anonymous
    June 15, 2009
    PingBack from http://debtsolutionsnow.info/story.php?id=9789

  • Anonymous
    June 16, 2009
    PingBack from http://lowcostcarinsurances.info/story.php?id=5292