Entries to my programming challenge


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 (3)

  1. 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