There Are 24 Responses So Far. »

1. Pingback by University Update - AJAX - Competition Update on 10 July 2007:

   […] Link to Article ajax Competition Update » Posted at The Programming and Management Blog on […]
2. 

   Comment by Paul on 10 July 2007:

   “The code is nicely formatted and mostly OO although he does have more procedural than I think is necessary.�

   Is there a right and wrong to using OO or procedural?? OO isn’t the holy grail, I just find that to be a biased remark towards their own preferences.
3. 

   Comment by Scott Nelly on 10 July 2007:

   Any hint on when you will announce the winner?
4. 

   Comment by Nick Halstead on 10 July 2007:

   Paul, I have to agree on that one. OO & procedural both have their time and place in my view. But it is up to each Judge to judge how they want to.

   Scott, because the Judges are being very thorough, I may end up annoucing the top 3 in seperate posts, as the final top 3 are all very good entries and I think deserve coverage in their own rights. But am waiting to see what the Judges think.
5. 

   Comment by Mike Malone on 10 July 2007:

   The size of the entries (code only) also varied from 6 files (20kb of code) to 30 files and (130kb of code).

   I guess that rules out my entry since it was only one file and less than 4KB including code and HTML (here’s the source if you’re interested).
6. 

   Comment by Scott Nelly on 10 July 2007:

   Any hint on *when* (not how) you will announce the winner?

7. Pingback by developercast.com » Nick Halstead’s Blog: (PHP) Competition Update on 10 July 2007:

   […] of the PHP programming competition put on by The Programming and Management blog, Nick Halstead has posted an update to help keep you up to date. The judging of the PHP competition is taking a lot longer than I […]
8. 

   Comment by antych on 12 July 2007:

   Where are the results???
9. 

   Comment by Nick Halstead on 13 July 2007:

   Anytch, am really sorry! it will without fail be out by Monday.
10. 

    Comment by John Campbell on 15 July 2007:

    I missed the competition announcement, but I decided to code up a solution for fun.
    My goals were pure speed and low memory usage on a very large word list. You can see the result here. It will find the shortest possible solution in less than .1 seconds with a 174,000 word dictionary.

    My algorithm is A* with precomputed “islands”. Building the map is O(nlogn), but it still takes about 60 seconds to import a large dictionary file. I’ll post the source after I do some cleanup.
11. 

    Comment by Nick Halstead on 15 July 2007:

    John, wow that is a blindingly fast solution! Good work. Shame you missed the deadline as I am sure it would have been in contention.
12. 

    Comment by Stuart Dallas on 15 July 2007:

    @John: Very nice, and very fast. Unfortunately one of the pairs of words I used when judging the entries causes yours to crash - purple to orange. There is no solution that I am aware of. I get a memory allocation error when I try it on your solution. Other than that it’s excellent.
13. 

    Comment by John Campbell on 16 July 2007:

    The solution to purple to orange is here

    Cheers,
    John
14. 

    Comment by Todd Pinel on 16 July 2007:

    Hey John I couldn’t find sorels in the dictionary. I’m not sure if that’s a problem or not. I figured I’d post my solution here too seeing as it performs pretty similar to yours, but I have a whole bunch more words for purple to orange. I’d like to know if anyone has a shorter path for this combo? Here’s my link Word Morph.
15. 

    Comment by Todd Pinel on 16 July 2007:

    Lol, I guess it totally relies on your word list because I just checked the path my program found going from purple to orange just to make sure all the words were legit and I found that holely was not coming up on dictionary.com. I used the Jazzy Java Spell Check API projects dictionary files found on sourceforge here. I thought it was a pretty robust dictionary. It’s pretty big too 1.6MB’s and roughly 159000 words but holely, just like sorely is apparently not a word according to dictionary.com I guess we’re in the same boat John!
16. 

    Comment by John Campbell on 16 July 2007:

    Todd,

    Wow, your solution is really impressive. I uploaded my word list to your system, and I got a solution with the same length as mine. You are processing the word list file, MUCH more efficiently than I am. Are your even pre-computing the graph? I hope you win so I can see your source.

    I do think mine is a little faster for stuff like adobes -> answer (there is no solution). by pre-computing the “islands”, my solution instantaneously knows it is impossible.
17. 

    Comment by Todd Pinel on 16 July 2007:

    Ahh very cool John! I think the time you see mine taking is due to the processing of the dictionary file I do before the search, and then the search sees right away that it’s not going to be linked but still it takes a few seconds to load the dictionary to memory and manipulate it. I’ll post the code tomorrow night as I have to get to bed right now for work tomorrow! You should write something about your “islands” I’d like to see how you did yours as well and what you mean by that. I’d also like to work that enhancement into mine so it would return as quick as yours if the link did not exist. Nice work:) Cheers, Todd.
18. 

    Comment by antych on 16 July 2007:

    The speed is impressive but the application doesn’t meet even a simple requirement like “user may supply an arbitrary list of words which makes up a limited dictionary”. I don’t think the point of the contest was to come up with a fastest algorithm but show your web building skill and focus on robustness and usability. - Nick correct me if I’m wrong.
    Still it’s nice to see that some people remember their CS classes and can do things very efficiently in the PHP world.
19. 

    Comment by Nick Halstead on 16 July 2007:

    The speed is certainly a factor but is one of many factors including the robustness and usability. I cannot comment any further as I have not seen the code to John’s solution.

    When I scored each of the entries I created a spreadsheet of 8 different factors (cant remember them all) but they included documentation, interface, security, standards, implementation. Each had a factor on how important they were towards the overall score (overly complex perhaps?) and the result was that my final orderin g matched my overall impression, which showed that building spreadsheets can sometime be a waste of time!

    Just to keep you all up to date, I still have one Judge who has not handed in the results so I cannot post it yet
20. 

    Comment by John Campbell on 16 July 2007:

    Todd,

    I think we are using the same search algorithm, but I am preprocessing the dictionary and storing it in a database. I am storing it so that querying for ‘hello’ returns ‘cello’,'hells’,'helio’ etc. Along with each word in the dictionary, I am storing an island_id, such that two words have the same island_id if and only if they can be linked together. Below is sudo php that will assign island id’s
    $i=1
foreach($dictionary as $word) {
assign_island($word,$i);
$i++;
}
function assign_island($word,$id) {
if( $word->hasIslandId() ) return;
$word->setIslandId($id);
foreach($word->getChildren() as $child_word)
assign_island($child_word,$id);
}


    The reason I call it islands, is because finding these word links is very similar to driving directions algorithms. Imagine someone requests driving directions from NY, to HI. A simple A* implementation will explore the entire North American road network before realizing it is impossible to drive to HI. Google doesn’t make this mistake.

    My source code is posted online.

21. Pingback by Working Too Many Hours at Home? An Easy Way to Stop… | The Marketing Technology Blog on 17 July 2007:

    […] judging a PHP contest that was due […]
22. 

    Comment by Scott Nelly on 18 July 2007:

    Any update on the competition update?
23. 

    Comment by Nick Halstead on 18 July 2007:

    Results will be posted tomorrow without fail.
24. 

    Comment by mod rewrite on 19 July 2007:

    Oh, I see results now.

Post a Response