Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw

The golf course looks great, my swing feels good, I like my chances (Part IV)

by eyepopslikeamosquito (Archbishop)
on May 10, 2009 at 06:39 UTC ( [id://763105]=perlmeditation: print w/replies, xml ) Need Help??

To top the program, someone else might try to do the same thing with fewer instructions--a worthy endeavor, since there was so little room in the small "memory" of the computers of those days that not many instructions could fit into them. John McCarthy had once noticed how his graduate students who loitered around the 704 would work over their computer programs to get the most out of the fewest instructions, and get the program compressed so that fewer cards would need to be fed to the machine. Shaving off an instruction or two was almost an obsession with them. McCarthy compared these students to ski bums. They got the same kind of primal thrill from "maximizing code" as fanatic skiers got from swooshing frantically down a hill. So the practice of taking a computer program and trying to cut off instructions without affecting the outcome came to be called "program bumming", and you would often hear people mumbling things like "Maybe I can bum a few instructions out and get the octal correction card loader down to three cards instead of four".

-- John McCarthy notices golf being played by his grad students in machine language in 1959 (from Hackers, Heroes of the Computer Revolution)

The competent programmer is fully aware of the strictly limited size of his own skull; therefore he approaches the programming task in full humility, and among other things he avoids clever tricks like the plague. In the case of a well-known conversational programming language I have been told from various sides that as soon as a programming community is equipped with a terminal for it, a specific phenomenon occurs that even has a well-established name: it is called "the one-liners". It takes one of two different forms: one programmer places a one-line program on the desk of another and either he proudly tells what it does and adds the question, "Can you code this in less symbols?"---as if this were of any conceptual relevance!---or he just says, "Guess what it does!". From this observation we must conclude that this language as a tool is an open invitation for clever tricks; and while exactly this may be the explanation for some of its appeal, viz., to those who like to show how clever they are, I am sorry, but I must regard this as one of the most damning things that can be said about a programming language.

-- Edsger Dijkstra notices golf being played in APL in 1972 (from The Humble Programmer)

As the above quotes indicate, code golf has been played informally for many years and in many different languages -- long before Perl, Ruby, Python or PHP were even dreamt of.

As far as I'm aware, however, the modern form of the game, defined by:

  • All entries must pass a strict test program before being accepted
  • Solutions are kept secret and not shared among the players
  • A leaderboard is continuously updated during play
has been with us only since the Christmas of 2001, courtesy of The Santa Claus Golf Apocalypse. (Update: you can see the original test program from 2001, along with all of Eugene's winning solutions (which all still work unchanged today!) at Re: What does your old Perl code look like?).

I had the privilege of refereeing this historic contest, which was brilliantly won by Eugene van der Pijll. Eugene invented the classic $\ golfing trick to win this competition. This trick is nowadays so well known that I'd speculate that every golfer in the top twenty of the Roman to Decimal game employed it.

Eugene further demonstrated the danger of golfic complacency, for everyone else in the field had assumed that you "obviously" couldn't improve on:

print reverse<>
Only Eugene unearthed the truly sick:
-p $\=$_.$\}{
to win by two strokes.

How codegolf Compares to Traditional Perl Golf

Eight years on, the game played at the codegolf web site is clearly recognizable to this Perl Golf oldbie. Indeed, it felt very similar to the original Santa game. The only significant differences I noticed were:

  • The human referee has been replaced by a robot, to allow the game to proceed automatically, without human intervention, 24 x 7.
  • There is (so far) no time limit. The original Perl Golf tournaments had a time limit of one week.
We'll analyse in the following sections how these two changes have affected the game of golf.

Outsmarting the Robot Referee

Milk holes in the tests as much as you want

-- codegolf founder carldr (Carl Drinkwater) answers a question on the codegolf forums

I can see now that a Robot Referee is essential if the golf tournament organiser wants to have a life. That said, I intensely dislike this aspect of the modern game. Let me give some examples from the Roman to Decimal game to show why.

I might add that the robot ref proved less of a problem in this game than many others because the Roman to Decimal test program, written by golf master flagitious, was a very good one, most unlikely to be subverted. Still, subvert it I did.

My first subversion came with the following 59 stroke Ruby "solution":

n=1;$.+=n.*1+n<=>n=2627%C/8%8*10**(3&C^C%3)while C=getc;p$.
Because I'd already written an exhaustive test program, I knew that, of the 3999 possible inputs, this "solution" failed only on I, II, III, IV, and IX. And since these weren't part of the fixed set of test cases, and were most unlikely to crop up in the randomly generated eight, I was highly confident that this "solution" would be accepted. So now I faced an ethical dilemma: to submit or not to submit? I was on 60 at the time, with Python golfing god Mark Byers and "bearstearns" (a team from the failed investment bank?) taunting me on 59. It wasn't even close: the site's founder had clarified the "milk holes in the tests" rule and Mark Byers had the gall to smash me by six strokes, snatching the Ruby lead from my clenched fists, which were now shaking in fury in his general direction. I just had to take my revenge on Mr Byers. Submit. "Your solution passed all tests". Yay. There was no punching the air with my fist this time though. It just didn't feel right.

That was only a minor cheat, and, luckily, after later finding an improved magic formula, my final 53 stroke solution was correct on all 3999 inputs.

The really outrageous cheat was yet to come. And it came in Perl.

While porting my Python/Ruby-improved magic formulae back to Perl, I found this alternative, and legitimate, 58 stroker:

Having exhausted all normal numbers, and desperate to go lower, I started trying numbers in scientific notation, 123E4 for example. Note, by the way, that this scientific notation works fine in this game for Perl and PHP, but not Python and Ruby, the latter two languages interpreting numbers in this format as floating point, not the required integers. My search program for this desperate chore was hacked together in Python because I found that Python handles very large integers transparently, plus I didn't need the speed of C and couldn't be bothered messing with Perl's BigInt module. The Python searcher found a hit all right yet I was dismayed when the corresponding 57 stroker, namely:
failed my test program. What's going on? After some debugging, I realised the 32-bit perl I was using was mangling the 5045e8. When I tried it on a 64-bit perl, I was pleasantly surprised to discover that all tests passed. So I ran a simple test on the codegolf site and determined they were running a 64-bit perl. Submit. "Your solution passed all tests". In the old Perl golf days, I'm pretty sure this 64-bit only solution would have been disqualified. Doesn't matter. I'm leading and happy once again.

Now we come to the outrageous cheat. I was racking my brains trying to find a shorter way of encoding these very large numbers that were popping up in the magic formulae when it occurred to me that Perl's two stroke $^T "current time" variable is indeed a very large number. And I can make it be whatever I want so long as I wait long enough and submit my solution so that the test program on the codegolf server runs when $^T has just the right value. I quickly calculated that a 53 stroke Perl "solution":

should "work" some time in 2011, but, not wanting to wait that long, I further noticed that the following 55 stroker:
would be available that very night! And not available again for some months. Spooky. Not only that, but the division by seven made the "submission window" a relaxed several minutes, rather than a frantic several seconds for the original 53 stroker. Synchronize watches now ... 1, 2, 3, submit! (Update: Much later, I found a non-cheating 53-stroke solution).

A win by an unsound combination, however showy, fills me with artistic horror

-- Wilhelm Steinitz, first World Chess Champion (1886-1894)

Well, that was fun, but is it golf? I don't think so. I felt dirty. This is what makes codegolf such a cruel game. Someone passes you on the leaderboard and you have no way of knowing if they've beaten you legitimately or cheated. And, because the games never close, you'll never know. This is unspeakably cruel, in my view.

Update: In compressing 99 bottles of beer, dmd found a rare cheat assuming a specific value for the pid $$. Though this can work in 99 bottles of beer because the test program is run once only, it is unlikely to work for other games where the test program is run multiple times, presumably with different pids for each run.

No Time Limit

This definitely worked in my favour. In all the Perl one week golf games, I had never finished higher than fifth. Had Roman to Decimal been a one week game, I probably would have finished fifth or so with my 64 stroke Perl solution.

Just as chess has five minute "blitz" tournaments, 25 minute "rapid" tournaments, five hour traditional tournaments, and correspondence tournaments played over months or years, I feel there is certainly room for different time limits in code golf also. I've got no problem with trying out many different time limits. What I object to is no time limit. As indicated in the previous section, I feel it's just too cruel.

Not only that, but if the game never closes, you miss out on what was always a highlight for me: the traditional post mortem analysis, usually written by the winner.

Which is the Most Enjoyable Golfing Language?

I found all of them enjoyable and feel it would be unfair to single any one out. Overall, Perl and PHP "felt" similar. So did Ruby and Python. I suspect this is mainly because Perl and PHP are much freer and easier in allowing strings to be used in arithmetic operations without explicit conversion. For example, you couldn't just write md5(SomeString)%1858, as I did in my PHP solution, in Python: you'd instead need the longer int(md5("SomeString"))%1858. Ditto for Ruby. Actually, thinking about it further, Python would give a run time error, because, unlike Ruby, its string to int conversion requires the string to consist only of digits. Overall, Python definitely felt the strictest of the four languages. And variables, of course, typically start with $ in Perl and PHP, making them twice as long, and therefore much less attractive, than they are in Ruby and Python. Finally, strings often don't require quoting in Perl and PHP, while they always do in Ruby and Python.

For me, the biggest Python annoyance was being unable to use assignment as part of larger expressions. Oh, and the lack of a short ?: operator. And the lack of built-in regex. And the need, unlike Perl and PHP, to initialize variables before use. For Ruby, it was being unable to use a boolean in arithmetic expressions, very common in golf. For example, Python is perfectly happy with n-2*p*(p<n), while Ruby chokes with "false can't be coerced into Fixnum (TypeError)". For PHP, its lack of basic operators was a chronic pest. For example, PHP alone among the four languages, lacks both an exponentiation ** operator and a string multiply operator (x in Perl, * in Ruby and Python), very handy in golf. I also missed concise regex and arrays when golfing in PHP. When golfing in Perl, I missed Python's powerful and concise string slice operator; though Perl's substr function provides similar functionality, it's usually too long for golf. I was also infuriated, especially in this game, by Perl's need for parens when using the ord function. For example, this magic formula 7&5045e8/ord cannot be equivalently expressed as 5045e8/ord%8 due to perl parsing quirks; instead you must write it as 5045e8/ord()%8, costing two precious strokes. Which is why only power of two modulo operators were competitive in this particular formula.

How Important is Language Knowledge in Golf?

Based on my codegolf experiences, not very. I got my only perfect score, three victories from three games, in PHP, the language I know least well. Curiously, it's also a language I dislike. On the other hand, I think Perl, Python and Ruby are all wonderful languages. As you might expect, I found golfing in Perl the easiest of the four and consistently finished in the Perl top five in the five games in which I took part -- though I was drunk under the table by 0xF and shinh in the 99 Bottles of Beer game (update: though I later sobered up, see Drunk on golf: 99 Bottles of Beer). Overall, despite this game, I performed least well in Ruby, failing utterly to make any impression on those damned beer bottles (update: though I later sobered up in Ruby also with Re^3: Drunk on golf: 99 Bottles of Beer my best ever Ruby golf performance). In summary, I don't think general language knowledge matters much. Knowing the golfing tricks for each language matters, of course, but you can pick those up for each language easily enough by googling and from the codegolf forums.

The main reason for my PHP result in this game is simply the relative lack of strong PHP golfers. There is really only one very strong PHP golfer, namely ToastyX, and he didn't play in the Roman to Decimal game. In contrast, the other three languages all have a large group of strong golfers: Python has "golfing god" Mark Byers, along with many other strong and enthusiastic golfers, such as Norwegian friends, hallvabo and tryeng; Ruby also has a "golfing god", flagitious, author of the golfscript language and one time codegolf leader across all languages, even though he usually only submits Ruby code; Perl has ySas, kounoike, 0xF and many others including occasional golfers from the golden era of Perl golf, tybalt89 (aka Rick Klement), mtve and Jasper -- oh, and not including `/anick ;-). Incidentally, many of the top golfers nowadays seem to hail from Japan.

More important than language knowledge is deeply understanding the problem and its algorithms, plus, of course, personal qualities, such as competitiveness, deviousness, and tenacity.

Who is the Best Golfer You've Ever Seen?

Without question, Ton Hospel. The complete golfer. Without a weakness. (Update 2020: incredibly primo is now better!!!). On one occasion, four expert golfers composed a problem, golfed it for a month, and concluded that the limit was around 120 strokes. Within hours of the game starting, Ton had embarrassed them by golfing it down to around 100! On another occasion, Mark Byers shortest Sudoku Solver was agonizingly whittled by five different golfers: 187, 186, 181, 179, and finally 178 strokes. These golfers were no doubt quite proud of their combined effort ... until Ton came along and reduced it to 121 strokes at his first attempt.

Like good tennis players (e.g. Australia in the 1960s), good golfers often come in groups; competing with each other sharpens their skills. That was certainly true in 2002-2003, and I would back a golfing dream team from that era of Ton Hospel, Eugene van der Pijll, Mtv Europe, and Rick Klement against all comers, from any era.

The best Ruby golfer I have seen is flagitious; the best Python golfer, Mark Byers (Jan 2013 update: now hallvabo); and the best PHP golfer, ToastyX (Jan 2013 update: now primo). The current top-rated all languages golfer at codegolf is shinh, who also runs a golf website

Which Language Produced the Shortest codegolf Code?

Perl. Closely followed by Ruby. Then a big gap to Python, closely followed by PHP. Of the 27 codegolf games, Perl produced the shortest solution 18 times, Ruby 9. PHP produced the longest solution 16 times, Python 11. Perl and Ruby produced the shortest two solutions in every game save two: the classic 99 Bottles of Beer, in which PHP (172 strokes) edged Ruby (173 strokes) by a single stroke for second place behind Perl on 165 strokes; and the 1000 Digits of Pi game, where Perl was left far behind (I didn't play that one, so don't know why).

Here are the shortest entries, by language, in all 27 codegolf games, as at early May 2009.
Lowest ScoresPerlRubyPythonPHP
99 Bottles of Beer165*173183172
Numeric Diamonds93*102118151
Home on the Range50*6710191
Pascal's Triangle39*436361
SHA-256 Hashing396338*537738
Total Triangles59*639985
Prime Factors76*8210095
Vigenere Cipher45*497388
1000 Digits of Pi10254*62112
Oblongular Number Spirals114112*139184
Paint by Numbers197*205294403
Conway's Game of Life151*186269306
Dancing Queens65*7510096
Seven Segment Displays111107*131137
Polynomial Division152138*176349
The Joy of Ascii Art50*6812191
Roman to Decimal5553*7270
Musical Score78*102115134
Tower of Hanoi110104*142163
Grid Computing43*637367
Saving Time101*112127132

Which is the Most Popular Golfing Language?

Perl Golf? You must be after the other P language. You see, Perl golf died around five years ago. The Perl community moved on, matured, and today much prefers clean, elegant code to cryptic golfic line noise. Reformed Perl golfers nowadays enthusiastically endorse Perl Best Practices. If you want TMTOWTDI and cryptic golfic line noise, I suggest you try Python. It has a thriving golf community.

Ahem. To prove my point about the recent rise in popularity of Python golf, notice that, in the past two years, codegolf has hosted three golf games. Here are the total number of golfers in these games by language:

LanguageNumber of Players

Update: As noted in Drunk on golf: 99 Bottles of Beer, the growth in number of golfers competing in the popular 99 Bottles of Beer challenge over the past two years further supports the claim that Python is now the most popular golfing language:

LanguageBottles of Beer growth, May 2009-May 2011

And here are the number of entries, by language, in all 27 codegolf games, as at early May 2009.
Number of EntriesPerlRubyPythonPHP
99 Bottles of Beer205279*267207
Numeric Diamonds4676*6431
Home on the Range117*10710560
Pascal's Triangle99108*10661
SHA-256 Hashing926*136
Total Triangles3758*3817
Prime Factors6970*5327
Vigenere Cipher5175*5630
1000 Digits of Pi3385*5337
Oblongular Number Spirals2560*3617
Paint by Numbers716*75
Conway's Game of Life1128*248
Dancing Queens2224*2117
Seven Segment Displays434954*22
Polynomial Division817*145
The Joy of Ascii Art78*716650
Roman to Decimal698687*62
Musical Score2532*3117
Tower of Hanoi1821*205
Grid Computing10393112*73
Saving Time8057106*58

Golfer Burn Out

We've learnt from history that too many golf events cannot be sustained: the 2002 TPR season lasted just one year; terje's golf site lasted only two seasons; and codegolf had 24 challenges in the first year, yet just three more in the following two years. Too many games burn golfers out.

Accordingly, I suggest a schedule of between one and four serious golf games per year -- all opened in January and all closed in December. That way, you can chip away during the year when you have time. Any more than four serious games per year is not sustainable IMHO.

Golf would be more attractive if a tournament sponsor could be found, with decent prizes for the top place getters, as Fonality did. And I think shinh is on the right track with over 50 languages on offer; more languages may broaden the appeal and make the post mortem more interesting -- though perhaps impossibly difficult to write, covering four languages here being hard enough :-).

I won't be involved though because I'm burnt out. Just as I took a four year break from golf in 2003, it's time for me to take another extended break.

I hope you enjoyed my long journey through this game. I'll continue this series in a year or so with a Saving Time post mortem. See you then.


References Added Later

Replies are listed 'Best First'.
Re: The golf course looks great, my swing feels good, I like my chances (Part IV)
by Your Mother (Archbishop) on May 10, 2009 at 07:49 UTC

    1) Don't feel dirty. There's no such thing as cheating in a real fight.

    2) You totally rule.

Re: The golf course looks great, my swing feels good, I like my chances (Part IV)
by wazoox (Prior) on May 11, 2009 at 13:27 UTC

    Tenacious as a Moray eel. Strong as a pitbull. Astute as a fox. Eye pops like a mosquito, he is.

Re: The golf course looks great, my swing feels good, I like my chances (Part IV)
by primo (Scribe) on Jun 07, 2013 at 12:26 UTC
    the 1000 Digits of Pi game, where Perl was left far behind (I didn't play that one, so don't know why)

    Both the Ruby and Python solutions rely on native support for arbitrary integer precision, essentially calculating π * 101000, and then hacking in the decimal place at the end. While Perl does have libraries for this, unfortunately all types of import statements have been disallowed for all languages. Had bignum been available, the following would have been fairly competitive at 59 strokes:

    use bignum a,1001;$c=6x4;$_=$_/$c*--$c/2+2while$c-->2;print

    which is basically identical to the shortest Ruby and Python solutions.

    And this would have taken the lead at 40 strokes, utilizing the built-in atan2 function:

    use bignum a,997;print atan2(1,1)*4,1989

    The final 1989 is unfortunately necessary, because the last few digits don't quite converge.

    As of Math::BigFloat v1.87, this would also be valid for 29 strokes:

    use bignum bpi;print bpi 1001

    although Perl 5.8.8 seems to be packaged with Math::BigFloat v1.60, so this wouldn't have worked anyway.

    The formula used is this:

    pi = 2 + 1/3*(2 + 2/5*(2 + 3/7*(2 + 4/9*(2 + 5/11*(2 + ...)))))

    When doing this challenge, I spent a long time comparing formulas for calculating π (of which there are dozens), but this seems to be the only one to converge in any reasonable amount of time (and after conversing with several golfing maestros (specifically flagitious, hallvabo and leonid), they all came to use the same formula). In order to compute this without support for arbitrary precision, each division needs to be broken into stages, storing the modulo in an array, and continuing down until the desired precision is reached. I originally submitted in PHP before Perl, but the general algorithm I ended up with is this:

    for($c=3429;$b=$c-=27;$e=$d%1e8){ for(;--$b;){ $d=$d*$b+($e?$f[$b]:2)*1e8; $f[$b]=$d%($g=2*$b-1); $d=0|$d/$g } printf$e?'%08d':'%d.',$e+$d/1e8 }

    which calculates 8 digits at a time, and then carries on to the next chunk. It's also quite fast. After literally years of on-and-off golfing, my final Perl revision looked like this:


    102 bytes, nearly twice as long as the best Ruby solution. Fortunately, this can be adjusted to a suitable pack u format with very little effort (but at the cost of 4 (3 packed) bytes):

    # 1 2 3 4 5 6 #234567890123456789012345678901234567890123456789012345678901 m_;--$h?$%=($f[$h]=$h--/2*$%+$f[$h%=7875]%$h*1e8)/$h:+printf$ a?"%08d":"3.",$a%1e8+($a=$%)/1e8for@f=(2)x5e5

    resulting in a code length of 95 bytes, which is where it currently stands.

    Wait a minute, wasn't there a Perlgolf digits of Pi post-mortem?

    Why yes, yes there was. PCLP #5.2, which can be found in the perlgolf history book. The winning solutions were submitted by (no surprise) Rick Klement and Ton Hospel, both at 78 bytes. Their solutions were as follows:

    78, Rick Klement
    ($c,@0)=map P|($c=$c%($d=20*$?+10).0+$_*$?)/$d,@0while@0[0,1e3]=3,--$?;print@0

    78, Ton Hospel

    Ton later reduced Rick's solution to 77 strokes post-mortem:

    ($c,@0)=map P|($c=$c%($d=10+20*$?).0+$_*$?)/$d,@0while$?-=@0[0,1e3]=3;print@0

    I'm going to focus on Rick's solution for two reasons. First, because he uses the same algorithm I do, and second, because I have no idea how Ton's solution works. I suspect he might be using the same algorithm, but I honestly can't be sure (2*$?||239 seems rather bizarre, for example). If these two solutions do have anything in common, however, it's that they're both horrendously slow. Ricks solution takes approximately 47s on my computer, while Ton's clocks in at 136s. In my experience, anything that takes more than ~1.3s locally will timeout on the codegolf server.

    But not all hope is lost. Both solutions abuse the fact that $? is stored internally as an unsigned short, meaning that decrementing it will result in 65535, eliminating the need for initialization. However, only ~3322 iterations are necessary (each deeper iteration produces one more binary bit of π. Crazy, I know). There's also a lot of unnecessary string -> int conversion going on, which slows things down a bit as well. Rick's solution is also particularly nice to work with, because the decimal place can be hacked in simply by changing the literal 3 with '3.'.

    A re-work of Rick's solution, 12 bytes heavier, but 28 times as fast:

    $a=3322;($c,@0)=map 0|($c=$c%($d=10+20*$a)*10+$_*$a)/$d,@0while$a-=@0[0,1001]='3.';print@0

    and... it times out. Almost fast enough at 1.67s locally, but not quite fast enough. Still fairly impressive though, considering that it calculates 1 digit at a time, instead of 8. If this could somehow be made ~25% faster, it could take the lead.

    And finally, my own post mortem to PCLP #5.2:

    56, primo ((very) post-mortem)
    use bigint;$c=6x4;$_=$_/$c*--$c/2+2e999while$c-->2;print

    As far as I can tell this should be entirely compliant with the rules, with a very acceptable run time as well at ~1.15s.

      I have no idea how Ton's solution works
      Ha ha! This was a common problem back in the good old days. Eugene van der Pijll, even after defeating Ton with his Mad Dutch algorithm to win the TPR(0,5a) infix-to-postfix tournament, never did understand Ton's third-placed solution. Ton was by far the most inventive golfer of that era, often unearthing astonishing hacks from deep study of perl's C implementation.

      That was terrifically interesting primo, thanks!

      You can save two more strokes by using for instead of while:

      54 strokes
      use bigint;$p=$p/~(2*$_)*~$_+2e999for-3333..-2;print$p

        And two more by using $\

        use bigint;$\=$\/~(2*$_)*~$_+2e999for-3319..-2;print


Log In?

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlmeditation [id://763105]
Approved by Corion
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others romping around the Monastery: (4)
As of 2024-04-18 20:07 GMT
Find Nodes?
    Voting Booth?

    No recent polls found