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:
- 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” )
- 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
- 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>