Partilhar via

Entries to my programming challenge

  • Artigo

Calvin submitted the first entry to my programming challenge. And (surprise!), it’s in Visual Fox Pro. I didn’t know Fox Pro can do that! It’s always nice to see unconventional ways to solve a problem.

Calvin’s post includes the source code, comments, and some anecdotes. I suggest you check it out.

After studying the code and comments, my conclusion is that his algorithm is a brute-force one. In summary, it:

  1. generates all possible ways to represent the phone number using a sequence of English letters (not necessarily words) and decimal digits, (e.g. “23hj6p8x” is a way to represent “23456789” )
  2. for each sequence from step 1, generates all possible ways to divide it into sections (by inserting dashes into the sequence, e.g. “23h-j-6p8-x” ), and
  3. filters out the entries from step 2 that contains illegitimate words (thus “23h-j-6p8-x” is out since “23h” is not a valid word).

This idea is a sound one, i.e. it does give all the result we want. However, I wish it could be more efficient, although efficiency is not the main concern for this competition. (Calvin mentioned he also has an optimized version but didn’t post that one.)

Now let’s come to the clarity. The code is about 100 lines of Fox Pro. I managed to understand it with the comments, even though I never programmed in Fox Pro before (You should be able to translate this code into any other procedural language like C++ or VB with little trouble). The EnumNum()procedure is still a little too big to my taste, and could benefit from refactoring.

You cannot talk about the clarity of the code without talking about the clarity of the algorithm and data structure. I saw many programmers trying hard to improve their code, while what needs to be improved is the algorithm. The leap from optimization-in-the-small to optimization-in-the-large can often make surprising difference.

For this contest, I believe there are algorithms that are both simpler and more efficient. Let’s work harder!

After writing the above, I got another entry by Justin Rogers. This one is about 140 lines of C# , and has basically no comments. In Justin’s own words:

“I made some changes to the algorithm by cutting out single character responses. I don't bother placing the dashes in since I don't think they are uber important, but I could put that feature back in if necessary.

I'm using the cheapo dictionary for now, and I've done 0 optimizations. The only true optimization is in the switch table.

One thing to note. You can really optimize the algorithm in the case that a 1 or 2 somehow bisects the numbers. When you do this, you only have to process two substrings, reinserting the splitting character where necessary. This can result in a huge performance gain. However, a good deal of the numbers you would process don't contain a 1 or a 0, and so the perf gain is lost.

 

And my algorithm isn't properly convergent either, so I'm not yet completed.”

Justin, I don’t know what you mean by “isn’t properly convergent”. Literally I think that means the program does not terminate (oh, BTW, in this case you don’t really have an algorithm. An algorithm by definition must terminate.). I’m sure you can fix that though.

I also spotted some suspicious lines that could a bug. Nice try. But please make sure you code runs when submitting. Some sample results can help convince us (and yourself) of that.

The competition is getting more interesting. Who’ll be the next?

<4/1/04, 4pm: edited to add Justin’s entry>

Comments

  • Anonymous
    April 06, 2004
    I got you. I've updated mine. Properly convergent meant that it only showed a subset of results. It both compiled and ran as it was. The new version is ever so slightly more complete. I wish I'd had more time to get this done earlier, but other matters came to take my time. Latest sample results from the sample dictionary for the given number.

    C:ProjectsCSharpSamplesNum2Words>Num2Words dictionary.txt 6423946369
    nice9infox
    6ice9godo9
    64bewhofox
    6423wine69
    6icewinfox
    64be94of69
    64bewhodo9
    6423window
    6icewindo9
    6423win369
    6ice9in369
    64be946369
    64be9infox
    64bewin369
    6ice94of69
    nicewhodo9
    6icewhofox
    nicewho369
    nice946369
    64239infox
    64239indo9
    6ice9indo9
    64bewho369
    6423946369
    64bewind69
    64239godo9
    64be9in369
    6icewin369
    nicewine69
    64239in369
    64bewinfox
    64bewindo9
    64bewine69
    nicewindo9
    6icewine69
    6423whodo9
    nicewind69
    6ice9infox
    nice9indo9
    nicewindow
    64239gofox
    6423whofox
    6ice9go369
    6423windo9
    64be9go369
    6icewhodo9
    6ice946369
    64be946fox
    nice9gofox
    nice94of69
    6ice946fox
    6icewho369
    64239go369
    6423946fox
    6423winfox
    nice946do9
    642394of69
    6423who369
    6icewind69
    6ice9gofox
    6ice946do9
    nicewinfox
    6icewindow
    nice9godo9
    nice9go369
    64be9godo9
    64be9gofox
    64bewindow
    nice9in369
    nicewhofox
    6423wind69
    64be946do9
    6423946do9
    64be9indo9
    nicewin369
    nice946fox