Re: Drunk on golf: 99 Bottles of Beer

[eyepopslikeamosquito]

Python Update

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:

x = "012345"
s = x[0:3]       # s contains "012"
s = x[:3]        # same thing (using default)
s = x[4:]        # s contains "45"
s = x[1:4]       # s contains "123"
s = x[-5:-2]     # same thing using negative indices
s = x[-2:99]     # s contains "45" - negative index from end of
                 # string allowed, as is index outside string (99)
s = x[::2]       # s contains "024"
s = x[1::2]      # s contains "135"
s = x[1:4:2]     # s contains "13"
s = x[1:5:2]     # s contains "13"
s = x[1:6:2]     # s contains "135"
s = x[-1::-2]    # s contains "531"
s = x[::-2]      # same thing (using default)
s = x[::-1]      # s contains "543210" (i.e. string reverse)
s = x[::0]       # "ValueError: slice step cannot be zero"

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:

n=99
z=lambda:`n or 99`+" bottle"+"s of beer on the wall"[n==1:]
while n:y=z();n-=1;print"%s, %s.\n"*2%(y,y[:-12],n and"Take one down a
+nd pass it around"or"Go to the store and buy some more",z())

notice the expression:

n and"Take one down and pass it around"or"Go to the store and buy some
+ more"

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):

"Take"if n else"Go to"
(n>0)*"Take"or"Go to"
["Go to","Take"][n>0]
("Go to","Take")[n>0]
n and"Take"or"Go to"
"GToa kteo"[n>0::2]          # "Slice and Dice" wins this golf!

As you can see, I missed the winning Python "Slice and Dice" tactical trick in this game.

Good Things Come in Threes

Three quarks for Muster Mark!
Sure he hasn't got much of a bark
And sure any he has it's all beside the mark.

-- James Joyce in Finnegans Wake (inspiration for naming the quark)

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:

99 bottles of beer on the wall,<space>
99 bottles of beer.\nTake one down and pass it around,<space>
98 bottles of beer on the wall.\n\n

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:

i=298
while~-i:print i/3or 99,'bottle'+'s of beer on the wall.\n\n'[2<i<6:9+
+i%3*12]+'..\n\nGToa kteo  otnhee  dsotwonr ea nadn dp absusy  isto ma
+er omuonrde,,'[(i>3)+i%3*68::2],;i-=1

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:

i	i%3	i/3	Part of song
298	1	99	bottles of beer on the wall,
297	0	99	bottles of beer. Take one down and pass it around,
296	2	98	bottles of beer on the wall.
295	1	98	bottles of beer on the wall,
294	0	98	bottles of beer. Take one down and pass it around,
293	2	97	bottles of beer on the wall.
...	...	...	...
...	...	...	...
...	...	...	...
7	1	2	bottles of beer on the wall,
6	0	2	bottles of beer. Take one down and pass it around,
5	2	1	bottle of beer on the wall.
4	1	1	bottle of beer on the wall,
3	0	1	bottle of beer. Go to the store and buy some more,
2	2	0 => 99	bottles of beer on the wall.

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.

Update: As noted in the "Inchworm on a stick" section at perlsecret, the high precedence decrement ~-$x inchworm-on-a-stick only works for positive $x while the high precedence increment -~$x inchworm-on-a-stick only works for negative $x ... though with use integer they work for all $x (as they do in Ruby and Python golf).

The hardest part of hallvabo's masterwork to understand is probably the odd-looking string slice at the end:

'..\n\nGToa kteo  otnhee  dsotwonr ea nadn dp absusy  isto maer omuonr
+de,,'[(i>3)+i%3*68::2]

This complex "slice and dice" serves a dual purpose:

• To switch from "Take one down and pass it around" to "Go to the store and buy some more" at the end of the song.
• To deal with the (fiddly) song punctuation. Note, by the way, that the (quirky) Python print statement thoughtfully does exactly what we wish for: a space is obligingly inserted after each comma, even the trailing one, yet is suppressed if what is printed already ends in a newline (as our i%3==2 case does).

Instructively, notice that hallvabo's earlier (longer) submissions used a number of different strings; he found that reducing the number of strings lowered his golf score. To illustrate, here is his earlier 187-stroke entry:

i=298
while~-i:print i/3or 99,'bottle'+'s of beer on the wall'[2<i<6:9+i%3*1
+4]+('.\n'+'GToa kteo  otnhee  dsotwonr ea nadn dp absusy  isto maer o
+muonrde,,'[i>3::2],',','.\n\n')[i%3],;i-=1

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:

i=298
while~-i:print i/3or 99,'bottle'+'s of beer on the wall.\n\n'[2<i<6:9+
+i%3*12]+'.X\n.G\noT atkoe  tohnee  sdtoowrne  aanndd  pbausys  siotm 
+ea rmoourned,,'[3%i+i%3*68::2],;i-=1

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:

i=297
while i:print-~i/3or 99,'bottle'+'s of beer on the wall.\n\n'[1<i<5:i%
+3*14^21]+'..\n\nGToa kteo  otnhee  dsotwonr ea nadn dp absusy  isto m
+aer omuonrde,,'[i%3-2^-72|2%i::2],;i-=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:

print~$_/3|0||99," bottle",substr("s of beer on the wall.

X",6/$_%2,-4**($_%3)),(", ",$_<-4?".
Take one down and pass it around, ":".
Go to the store and buy some more, ")[$_%3-3]for-299..-3

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:

print-$_/3|0||99," bottle",("s"," of beer"," on the wall",".

")[5/$_%2..-$_%3+1],($_<-3?".
Take one down and pass it around, ":".
Go to the store and buy some more, ",", ")[-$_%3]for-298..-2

A Ruby Translation

I also wrote a couple of quick Ruby translations, a 183-stroke:

298.downto(2){|i|$><<i/3%-99+99<<" bottle"+"s of beer on the wall.

"[5/i%i..8+i%3*12]<<[i>3?".
Take one down and pass it around, ":".
Go to the store and buy some more, ",", "][i%3]}

and a 184-stroke:

298.downto(2){|i|$><<i/3%-99+99<<" bottle"+"s of beer on the wall.

"[5/i%i..8+i%3*12]<<".
Go to the store and buy some more, .
Take one down and pass it around, "[3%i*25/2+i%3*34,37]}

Though these two can surely be further reduced, 173 strokes looks out of reach.

Ruby Update

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:

eval"$><<%{#{a=b='#{n} bottl#{"es"[0,n]} of beer',' on the wall'}, #{b
+}.
\#{0<(n-=1)?'Take one down and pass it around':(n=99;'Go to the store 
+and buy some more')}, #{a}.

};"*n=99

while J-_-L's original 182-stroker was:

eval %{puts"#{a='#{n} bottle#{n>1?:s:p} of beer on the wall'}, #{a[0,3
+0]}.
\#{(n-=1)<1?(n=99;'Go to the store and buy some more'):'Take one down 
+and pass it around'}, #{a}.

"
}*n=99

So Ruby wins the TMTOWTDI prize in this game given that three completely different approaches all yield sub-180 solutions.

Regex (173)

$_="Take one down and pass it around, #{~/s/;c=4-$.-=1," bottle#$& of 
+beer"," on the wall"}.

#{c}, %s%s.
#$_"%c until/, 99\D+/;puts$'+"Go to the store and buy some more"+$&

Map (177)

"Go to the store and buy some more"+(-99..-1).map{|n|", #{b=-n," bottl
+es"[0,6-n]+" of beer"," on the wall"}.

#{b}, %s%s.
"%b}*"Take one down and pass it around"=~/

/;puts$'+$`

Eval (178)

# Based on emiltin.
eval"$><<%{#{a=b='#{n} bottl#{"es"[0,n]} of beer',' on the wall'}, #{b
+}.
\#{0<(n-=1)?'Take one down and pass it around':'Go to the store and bu
+y some more'%n=99}, #{a}.

};"*n=99

# Based on J-_-L.
eval"$><<%{#{a=b='#{n} bottle#{n>1?:s:p} of beer',' on the wall'}, #{b
+}.
\#{(n-=1)<1?'Go to the store and buy some more'%n=99:'Take one down an
+d pass it around'}, #{a}.

}
"*n=99

Shortest Perl, Ruby and Python Solutions

To sum up, as at June 2011, the shortest known solutions to this game are:

Perl (161 strokes):

/s/until@c=(@b=(++$n,bottle.$&,of,beer),on,the,wall),s/^/Take one down
+ and pass it around, @c.

@c, @b.
/,/, 99\D+/;print$'."Go to the store and buy some more$&"

Ruby (173 strokes):

$_="Take one down and pass it around, #{~/s/;c=4-$.-=1," bottle#$& of 
+beer"," on the wall"}.

#{c}, %s%s.
#$_"%c until/, 99\D+/;puts$'+"Go to the store and buy some more"+$&

Python (181 strokes):

i=298
while~-i:print i/3or 99,'bottle'+'s of beer on the wall.\n\n'[5/i%i:i%
+3*28^9]+'.X\n.G\noT atkoe  tohnee  sdtoowrne  aanndd  pbausys  siotm 
+ea rmoourned,,'[i%3*69^3%i::2],;i-=1

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.