Code golf

03.01.2011 22:54

One of the more fun activities at the 27C3 was the code golf challenge organized by the <<</>>. It's a competition where you are given a simple task and the winner is whoever writes the shortest program that can complete that task (either overall or in a particular programming language).

Just about any language was valid, from Postscript to Z80 assembly. What convinced me to join was when I saw that the current Python leader had less bytes than the current Perl leader. As a seasoned Perl programmer I found that offensive - if anything, Perl is known for its ability to parse short, incomprehensible strings of line noise. How could the there-is-only-one-way-to-do-it Python win? So I used a couple of hours to correct that injustice.

The given task was to make a program that reads an integer in ASCII from standard input and outputs an ASCII art of a string of that many Cs:

$ echo 3 | perl x.pl
   ##  ##  ##
 #   #   #
#   #   #
#   #   #
#   #   #
 #   #   #
   ##  ##  ##

My best solution with 67 bytes came in at the 10th place at the end. The first place was taken by a program of just 26 bytes.

It was cheating, of course. What did you expect on an event like this? My first idea was to fetch the solution from a remote server, but I soon gave up when I realized the execution environment was closed more tightly than I thought. I'm sure just about everyone else tried something like that before starting work on a real solution.

However ySas' program that took the second place with 50 bytes is a legitimate solution and very interesting to pick apart. Here it is in its entirety:

print$\=($_='   #'x<>)|" $_
 "x/ +/,"$'
"x4," $'
"

Here's a sample output when 3 is given on the standard input (the colored parts of the code produce the parts of the output in the same color). Note that all white space (including new lines) is significant:

   ##  ##  ##
 #   #   #
#   #   #
#   #   #
#   #   #
 #   #   #
   ##  ##  ##
 

There are three tricks worth noting here:

First, all strings are made out of a basic building block constructed in the parenthesized part and assigned to the special variable $_ ("   #" repeated by the number read from standard input). The red part is made by binary ORing $_ with itself, shifted by one space. Space is ASCII 0x20 and "#" is 0x28 so space OR "#" equals "#". Also it appears that Perl zero-pads strings when performing binary OR.

The right-hand side of the OR operator is multiplied by "/ +/". This regular expression operator finds the three leading spaces in $_ and returns 1 in scalar context (so multiplication doesn't have any effect). However it also sets the special variable $' to the rest of the string ($_ without the leading white space). $' is then used in the green and blue part of the output.

Finally, the first part of the string also sets the $\ special - the output record separator. Setting it causes an implicit repetition of the red part of the string at the end of the print statement.

So, here it is - 50 bytes of Perl code which take an hour to understand. First valid solution in Python came in at 67 bytes (is it easier to understand?) and PHP in 91 bytes. In the end, my 10th place did in fact get me a bottle of Club Mate, because I was the only 27C3 Perl coder that showed up on the final code golf meet-up. But I guess sharing the tricks learnt also counts as something.

Posted by Tomaž | Categories: Code

Add a new comment


(No HTML tags allowed. Separate paragraphs with a blank line.)