|Perl: the Markov chain saw|
Re: Drunk on golf: 99 Bottles of Beerby eyepopslikeamosquito (Chancellor)
|on Jun 12, 2011 at 07:25 UTC||Need Help??|
It disturbed me that the 99 bottles of beer analysis in the root node was incomplete without a short Python solution. Unable to concoct one myself, I contacted hallvabo, who was delighted to share his winning solution and the circumstances behind it.
If I just reveal his solution now, however, you might just exclaim "What the f*#?! is that?" and move on. Armed with an understanding of Python string slices though, hallvabo's wacky-looking concoction becomes logical and comprehensible. So I'll start with an overview of Python slices so as to make his solution more accessible.
Introduction to Python Slices
"Regexes always win" -- Mtv's law of Perl golf
"String bitwise operators always win" -- ToastyX's law of PHP golf
"Slices always win" -- Hallvabo's law of Python golf
When playing golf, it's vital to know which language features tend to produce the shortest code. While the above "laws" are admittedly outrageous oversimplifications, they are catchy and easy to remember. Perl regexes frequently trump alternative approaches. As do Python slices.
The Python slicing operator s[i:j:stride] extracts subsequences, where [i,j) is a semi-open range of indices in sequence s. All slicing arguments are optional. Negative indices (relative to the end of the string) and negative strides (reverse direction) are supported. Some examples should clarify:
If you want to be competitive at Python golf, you must master all the intricacies and defaults of string slicing.
Ruby also supports complex and powerful string slicing, but not strides. Though Perl supports array and hash slices, when it comes to slicing and dicing strings, Perl's substr function is nowhere near as concise as Python and Ruby slices and, accordingly, is rarely sighted in a winning Perl golf entry. By the way, I'd love to see Perl support more concise string slicing.
The "Slice and Dice" Golfing Manoeuvre
From my early 195-stroke function-based Python solution:
notice the expression:
Shortening the two strings above to "Take" and "Go to" for clarity, let's consider the many and varied ways of doing this in Python (TMTOWTDI):
As you can see, I missed the winning Python "Slice and Dice" tactical trick in this game.
Good Things Come in Threes
In addition to missing the "Slice and Dice" tactical trick, I overlooked a crucial strategic idea, namely to break up each verse into threes, like so:
Yet again in golf, uniformity pays dividends. Notice that each and every print statement now begins in the same way, with "n bottles of beer". Not only do you avoid the dreaded function call, but you can now print the "n bottles of beer" refrain on the fly, without needing to store it in a variable. There is a price to pay however. Instead of looping 99 times, you must now loop three times longer, 297 times. In turns out in Python that this is a bargain, as demonstrated by hallvabo's winning entry.
Dissecting Hallvabo's 182 Stroke Python Solution
With the key tactical and strategic ideas explained, I hope you'll find hallvabo's winning Python entry easier to follow:
To generate the required numeric beer bottle sequence, notice that hallvabo employed a while loop, very common in Python golf, counting down from 298 to 2, as illustrated in the table below:
As you can see, his 2<i<6 boolean expression is used as the starting offset in a "s of beer..." string slice thus ensuring "bottle" rather than "bottles" is displayed when i has the values 3, 4 and 5 (corresponding to one bottle). The 9+i%3*12 ending offset concisely trims the "s of beer on the wall.\n\n" string to the required length.
The odd-looking ~-i while loop expression is just the Inchworm-On-A-Stick "secret operator", first employed by Perl golfer Ton Hospel in 2002, and nowadays routine in code golf across all languages. It's effectively the same as i-1 but with different precedence. Here it's employed simply to avoid a space after the while keyword. By the way, the converse inchwormy -~i secret operator for i+1 is routinely played in Python and Ruby golf ... but not Perl because it does not work for positive numbers -- for example, -~1 produces 2 in Ruby and Python, but -4,294,967,294 in Perl.
The hardest part of hallvabo's masterwork to understand is probably the odd-looking string slice at the end:
This complex "slice and dice" serves a dual purpose:
I have to give due credit here to "Logan", a remarkable golfing "beginner". Logan turned up on the codegolf IRC channel one day and the very experienced hallvabo gave him quite a bit of help to get him started. Within a few days, and much to hallvabo's surprise and chagrin, the pupil overtook the master, even stealing the outright Python lead from "uli"! To repay hallvabo, Logan gave him a slight hint to "stop being line oriented". As I well remember from the early Perl golfing days, giving even the slightest of hints to an expert golfer is fatal and so it proved here. Hallvabo fought back and eventually overtook his pupil Logan to win the game by a single stroke.
Reducing Hallvabo's 182 Stroke Python Solution
Of course, I tried to reduce hallvabo's winning entry further. When I first sighted his solution, I pulled a face the instant I caught sight of the ugly parentheses in (i>3)+i%3*68. Surely something can be done to eliminate them! Much to my surprise, I trimmed a stroke at my first attempt:
Notice that replacing (i>3) with 3%i saves two strokes, while costing only one, namely the wasted X above in the string being sliced and diced.
Alas, I couldn't shave any more, even after running some brute force search programs over hallvabo's string slice magic formulae. I uncovered some interesting new variations though. For example, 2<i<6 can equivalently be replaced by 5/i%2 or 5/i%i ... which is essential when translating to Ruby because, unlike Python, Ruby does not allow booleans in numeric expressions.
Update: It is just possible that changing hallvabo's 298..2 range to 297..1 or 299..3 or 296..0 or some such might produce a shorter solution. For example, here is a 184-stroker using 297..1:
Having said that, hallvabo's 298..2 does seem to be the most "natural" and I'd be surprised if a different range produced a shorter solution. Writing and running a program to exhaustively search all possible string slice magic formulae for a variety of ranges should settle this issue.
A Perl Translation
I didn't see much hope of adapting this approach to Perl due to the length of Perl's dreaded substr function, 191 strokes being the best I could find:
Because substr takes a length parameter, rather than a Python slice index, I was forced to concoct a different (negative) magic formula (-4**($_%3)) to count from the end of the string, which explains the wasted X above. Nasty.
Replacing substr with an array slice didn't help:
A Ruby Translation
I also wrote a couple of quick Ruby translations, a 183-stroke:
and a 184-stroke:
Though these two can surely be further reduced, 173 strokes looks out of reach.
Much later, I was surprised to learn that emiltin and J-_-L had both independently concocted an eval approach that never occurred to me. Emiltin's original 180-stroke solution was:
while J-_-L's original 182-stroker was:
So Ruby wins the TMTOWTDI prize in this game given that three completely different approaches all yield sub-180 solutions.
Shortest Perl, Ruby and Python Solutions
To sum up, as at June 2011, the shortest known solutions to this game are:
Perl (161 strokes):
Ruby (173 strokes):
Python (181 strokes):
Given that over a thousand golfers have hacked on this game for more than five years now, further reductions won't come easy, though they're certainly possible. So if you can further reduce any of these solutions ... well ... kudos. And please post them here. :)
Acknowledgement: I'd like to thank hallvabo for his help in preparing this node. Update: I'd like to thank emiltin and J-_-L for their help in preparing the Ruby update.