|No such thing as a small change|
The golf course looks great, my swing feels good, I like my chances (Part IV)by eyepopslikeamosquito (Canon)
|on May 10, 2009 at 06:39 UTC||Need Help??|
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:
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:
Only Eugene unearthed the truly sick:
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:
Outsmarting the Robot Referee
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":
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!
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. 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. 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 golf.shinh.org.
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.
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:
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:
And here are the number of entries, by language, in all 27 codegolf games, as at early May 2009.
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.