As a first step towards classifying the solutions, I have timed
them, just as I did for Rick's Troppo Sort game.
The winner of this month's Tortoise-crawlin' Hall of Shame
award is Amir Karger. It seems that Perl's Recursive Regex
is rather slow.
I have tried to classify some of the solutions below.
If I have made any mistakes, please let me know.
And please feel free to classify your own solutions (that
will definitely be more accurate than my feeble guesses;-).
Score Seconds Method
----- ------- ------
1. Ala Qumsieh 210.77 0.95 Stack (operator)
2. Mtv Europe 125.38 1.02 Stack (operator)
3. Alma Media Golf Team 119.62 1.05 Stack (all)
4. GONZO 322.75 1.06 Stack (operator)
5. Constantin M 292.43 1.38
6. Michiel van Leeuwen 144.65 1.44
7. Andrew Savige 133.69 1.46 Stack (operator)
8. Qingning Huo 116.27 1.48
9. Andre Savigne 1666.36 1.48 Stack (operator)
10. Peter Haworth 316.87 1.84
11. Kuang-che Wu 143.72 1.98
12. Jeff Moore 116.48 2.15 Overload
13. Jed Davis 177.58 2.34 Overload
14. Markus Laire 127.65 2.60
15. Adam Antonik 120.8 2.65 Overload
16. TheodoreYoung 131.82 2.76 Overload
17. Mykola Zubach 121.6 2.79
18. Jasvir Nagra 132.8 2.85 Overload
19. Ton Hospel 103.33 3.11 Parse (top down[2])
20. Eugene van der Pijll 98.22 3.26 Mad Dutch[1]
21. nashdj 209.69 3.43 Recursive Regex
22. Stephen Turner 116.65 3.72 Overload
23. Mark Hillebrand 121.6 3.81
24. Chris Dolan 153.48 4.31
25. Jonathan Wang 176.64 4.92
26. Keith Calvert Ivey 133.62 5.05
27. Michael Thelen 112.63 5.96 Stack (operator)
28. me ELOISE 206.7 6.20
29. John Williams 142.58 6.47
30. Prakash Kailasa 162.7 6.77
31. Jasper McCrea 172.39 7.99
32. Alain "TopMach" Dupuis 118.57 12.45
33. Chia-chi Yeh 121.62 13.45
34. Greg Allen 206.56 14.24 Parse (hybrid)
35. Honza Pazdziora 267.25 15.27
36. pom 109.51 18.49 Mad Dutch[1]
37. tinzo (berlin.pm) 165.45 41.36 Stack (with a hint
of Mad Dutch[1])
38. Alexey Rudenko 109.51 48.34 Recursive Regex
39. Jukka Suomela 149.25 49.87
40. Rick Klement 102.3 69.65
41. Eike Grote 203.63 92.12
42. Amir Karger 140.46 110.90 Recursive Regex
[1] finite state transducer (?)
[2] aka recursive descent
Why is Ala the fastest? Probably because of all that push'n'pop'n.
Notice that Ala is the only golfer who used 'reverse'.
Now, push/pop are pretty fast, faster than shift/unshift.
However, the golfing price for all that push'n'pop'n is that
butt-ugly 'reverse' adorning the end of Ala's solution.
To avoid the reverse, you might create the operator stack
with shift/unshift (as I tried in my first submission).
To eliminate the unshift eyesore, I soon switched to a
string-based stack manipulated by Regexes. To see push'n'pop'n
done well, see Alma Media's 119.62 (where they push both numbers
and operators onto the stack, I think).
/-\ndrew
