develooper Front page | perl.golf | Postings from September 2002

Tortoise-crawlin' Hall of Shame (tpr05a)

Thread Next
From:
Andrew.Savige
Date:
September 10, 2002 03:59
Subject:
Tortoise-crawlin' Hall of Shame (tpr05a)
Message ID:
694BB7191495D51183A9005004C0B05452DF75@ir-exchange-srv.ir.com.au
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


Thread Next


nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About