PHP Competition Results - Second Place

July 20th, 2007 • Related • Filed Under

If you're new here, you may want to subscribe to my RSS feed. Thanks for visiting!

Second Place - To Evan Chiu

I write this with slight trepidation after the minor dispute from yesterday’s result for third place. And yet onwards and upwards. So second place, more drum rolls.. goes to Evan Chiu.

Evan’s solution revolved around a well implemented breadth first search which was wrapped up in a neat class. It was also quite well presented and the HTML was all w3c compliant.

Entry Nick Stuart Cal Evans Total
1st. ????? 4 6 6 16
2nd. Evan Chiu 1 3 4 8
3rd. Karol Grecki 6 1 1 8
4th. JB 2 2 3 7
5th. Maurice Fonk 3 4 0 7
6th. Rob Haynes 0 0 2 2


Below is the heart of the solution the ’solve’ method which was part of the overall solver class. For those of you unfamiliar with BFS (Breadth First Search) there is a good article over on wikipedia. (As with previous code samples I have removed the commenting from the code)

function solve()
{
	$neighbors = array();
	foreach($this->_list as $one){
		$neighbors[$one] = array();
		foreach($this->_list as $two){
			$diff = $this->similar($one, $two);
			if($diff){
				array_push($neighbors[$one], $two);
			}
		}
	}
 
	while(count($queue) > 0){
		$current = array_shift($queue);
		foreach($neighbors[$current] as $neighbor){
			if(!isset($color[$neighbor])) {	
				$color[$neighbor] = 'g';	
				$this->_pi[$neighbor] = $current;
				array_push($queue, $neighbor);
			}
			if($neighbor == $this->_end){
				break 2;
			}
		}
		$color[$current] = 'b';	
	}
 
	return isset($this->_pi[$this->_end]);
}

Notes from the Judges

Clean, elegant code. Well documented and formatted. The only negatives I have on this one are this.
a) I would have liked to seen more OO code. Only Solver.php was OO and while it was the heart of the process, I believe the rest could have easily been OO.
b) It, like others, requires me to procedure the entire word list. While I know that the rules said I had to be able to enter a list, I expect the program to operate on a default dictionary if I don’t enter one.

  • Worked out of the box
  • Simple interface
  • Poor support for custom dictionaries (textarea)
  • Well-documented, possibly excessively so
  • Clean implementation of BFS
  • Minimal separation of code and presentation
  • No errors, warnings or notices seen until attempting to go between two words of differing lengths - reports no solution possible rather than an input error

Overall I liked Evan’s solution which was simple yet effective. Although it did lack separation of code and presentation it well deserves its second place.

If you wish to try out Evan’s solution he has it hosted here and if you wish to take a look at the code you can download it here.

There Are 18 Responses So Far. »

  1. Comment by Karol on 20 July 2007:

    No input filtering and output escaping, this should disqualify every web application on the start.
    I really don’t like including functions into global scope, this produces unmaintainable mess. The same goes for extract(). Generating html from php doesn’t help either.
    And you really should add some filtering in source.php before you include a file from _GET.

    I’m not gonna go into details and complain about small things, good effort anyway and congratulations.

  2. Comment by Rob Haynes on 20 July 2007:

    Congratulations, Evan. Great solution, with clean code and a clean interface.

    Can’t wait to see #1.

  3. Comment by Evan on 20 July 2007:

    Hey Nick, thanks so much! This competition was a lot of fun for me and it’s been great to see the results. I had forgotten how much fun it was to stay up late programming.

    Is there any way this could segue into a job offer? :D I graduate college in May 08.

  4. Comment by El Barto on 20 July 2007:

    I agree with comments of the jury and Karol. It would have been nicer to see it fully OO, but it wasn’t a must so I guess we can’t blame him for doing it the way he felt more confortable.

    I think it is very important, as Karol points out, the input filtering. Actually, with the kind of parameters he is working with it does not need that much amount of validations (he is not working against any database and is not allowing to upload files), but I think it would have been nice if you could upload a dictionary file.

    The code seems nice, clean, well-documented and I think it makes good use of some php functions (many programmers who come from other languages tend to forget about built-in array functions and code everything up). However, I agree with Karol that it would be better to keep the (x)html somewhere else. Although the core of the solution is a class, it doesn’t seem very OO and it looks more like a bunch of functions put all together in a class.
    I would have tried to separate the logical solution from the output to the user.

    Anyway, the solution to the problem is right, it works, the code is clean and I think those are the most important things. The rest is complementary. Good work, Evan.

  5. Comment by Karol on 20 July 2007:

    He’s not working with a database, but he accepts any input including client side javascript which is then outputed to the browser. And we all *should* know how bad it is. These are the fundamentals of PHP security.

    http://devzone.zend.com/article/2092-PHP-Abstract-Podcast-Episode-1—PHP-Security-Tips
    How ironic Cal.

  6. Comment by Nick Halstead on 20 July 2007:

    Karol,

    The rules did not mention ’security’ although you may argue that it could come under ‘robustness’ but frankly the criteria were for us to judge and not you. I will be running a Poll after the overall competition finishes so others may vote on the Top 6 and we will see what the ‘popular vote is’. Perhaps then you will get the result you so obviously crave.

  7. Comment by Rob Haynes on 20 July 2007:

    Wow, I’m starting to become indescribably grateful that I got last place. ;-)

    Karol, I liked your approach, too. Your interface was step-by-step, making things pretty simple for the client. And you included a few options here and there for convenience. Like probably every solution, it had its problems, but it’s what worked that earned you placing. Be proud of that! Each of the other solutions posted thus far have been pretty widely varied in approach and style, and I like that. Take the opportunity to see what better coders did differently, and try those things next time.

    It’s really easy to rip at each other’s code, but let’s take it in the spirit of friendly competition. Decision’s made, no lives or huge bucks on the line. The judges are humans, just like the contestants, so if a competition like this went off perfectly the first time around, I’d be amazed. It was a fun challenge, and I really hope it doesn’t end up being the last one.

    Nick, you mentioned putting the code up, but is that only for the first three entries? I don’t have a convenient site to throw mine up on, so I wanted to ask now so I could start hunting one down if necessary. Thanks.

    BTW, it’d be great to see an end-of-contest wrap-up about how the entries may have differed from what you expected. Anything that just took you by surprise (good or bad), besides what you mentioned already. Those wrap-ups are always kind of fun, and informative, too. My two cents.

  8. Comment by Karol on 20 July 2007:

    I don’t need to argue that, it should be common sense that the code should first adhere to best practices and programming standards. Especially in security as it’s a really major issue in PHP.
    But it’s just my opinion about Evan’s code, I already accepted judges’ decision and I believe they did their best.

  9. Comment by Nick Halstead on 20 July 2007:

    Rob,

    A very good point!

    To download:

    And yes I will definitely be doing a general roundup (that includes links to all the hosted versions and the downloads), and the rest of the entries will also give me a lot of source material for ‘what was done right’, ‘what was done wrong’.

  10. Pingback by developercast.com » Nick Halstead’s Blog: PHP Competition Results - Second Place (Evan Chui) on 20 July 2007:

    [...] place has been revealed in Nick Halstead’s programming competition - and the 2nd place mark goes to Evan Chiu. So [...]

  11. Comment by Rob Haynes on 20 July 2007:

    Nick,

    Thanks, that’s much appreciated. I’m really looking forward to final entry, especially with the high marks across the the board. Congrats in advance to the first-place contestant!

    Evan,

    Sorry, don’t mean to hijack your moment. Great job, and I doubt you’ll run short of job opportunities come graduation. =)

  12. Comment by Evan on 20 July 2007:

    Note to all:

    Rob emailed me before these results were posted showing how my source viewer could be exploited, so I changed it for the version that is hosted on my server. Thanks again, Rob!

    I know that I’m deficient in my understanding and awareness of security concerns, so thank you all for opening my eyes and pointing me to some great resources. I hadn’t even heard of XSS before today, nor did I understand how easy javascript injections were.

    I’m also really excited for first place, especially because that score stands out from the rest of ours.

  13. Comment by Tyler on 20 July 2007:

    If you’ll humor me for taking a page from John Gruber’s playbook I’d like to present . . .

    Translation From Troll-Speak to English of Selected Portions of Karol’s Latest Comment

    I really don’t like including functions into global scope, this produces unmaintainable mess.

    I don’t know how to write maintainable code if I don’t wrap everything in an object.

    Generating html from php doesn’t help either.

    I’m jealous of people who can think for themselves and write code quickly without resorting to a full framework or templating system.

    And you really should add some filtering in source.php before you include a file from _GET.

    Did I mention that I’ve read every Digg story titled “Top 10 PHP Security Gotchas”?

    I’m not gonna go into details and complain about small things, good effort anyway and congratulations.

    Now that I’ve gone into detail and complained about the little things, you suck, Evan.

  14. Comment by Karol on 20 July 2007:

    Tyler that’s a very constructive comment. I bet you made a thorough analysis of our code. Some people… and you call me a troll.
    Can we please not continue this?

  15. Comment by Mgccl on 21 July 2007:

    Congrat to Evan~

    Wow… BFS
    Now I know the name of the algorithm I was using xD
    even though my one was a variation and runs in O(n^2) time and use a LOT less memory…(with a 400kb dictionary, the memory never run over 1 MB and find linen to sheet in less than 25 seconds )

    Evan, your entry does have a problem when the dictionary is too big.
    I used the dictionary for my source (download my code and look at it) for your wordlist and try to find linen and sheet, and soon, it eats up more than 32 MB memory so I changed the memory limit for PHP to 256 MB. then it run for more than 60 seconds, so I increase the time limit to 5 minutes… but still runs to a time limit fatal error
    Fatal error: Maximum execution time of 300 seconds exceeded in F:\mgccl\xampp\htdocs\doublets\solver.php on line 194
    I don’t have more time to test on it so I stopped..
    it would be much faster if you rule out all the words have different word length… So I did a small modification and rule out all the words that don’t have the same length as the start word, but it still exceeded 300 seconds.
    -.-
    Other than that. your entry was great, work out of the box is pretty important to me… xD

    all the contest entires I have seen so far have scalability problem… wish No.1 could do it better.

  16. Comment by Mgccl on 21 July 2007:

    btw JB have a decent speed, the same times it uses
    Execution Time:45.147765
    Peak Memory Usage:7.649 MB
    nice

    @Rob Haynes. Your code kills me cause it don’t even take my dictionary -.-

    Maurice Fonk’s one might be fast since it have a 760kb dictionary, but I can’t get it to work.(I’m a noob… I use Windows)

  17. Comment by Rob Haynes on 21 July 2007:

    Mgccl,

    To use a custom dictionary, you can submit a wordlist with whichever words you want between the first and last. (For any of the three input methods, but upload or URL would probably be more efficient than typing all the words in. )

    The dictionary in the advanced options is only for validating the as being part of a standard language.

  18. Comment by John H on 22 July 2007:

    Nice effort although it’s unable to solve ‘hand’ to ‘foot’.

    All the criticisms make me laugh though and reminds me of why I stopped entering photography contests years ago. It doesn’t matter how creative or abstract one tries to be, the cute baby in the bonnet is going to win every time.

Post a Response