Golfing 101

Adrien Kunysz, Thu, 01 Mar 2012 16:14:45 GMT

Some months ago I somehow ended up at a NoSQL/BigData meeting (whatever that means) supposedly full of technical people. In reality it was filled with web developers. This was somewhat compensated by the fact drinks were free and there was a football table. There was also an unattended laptop connected to a live projector and logged into a root shell.

I am not sure exactly what they were thinking but two drinks later I was obviously obliged to type this at the prompt:

# :(){ :|:& };:

However I did not press the "Enter" key. I then went on to explain to my colleague what the above line were to do if it was to be interpreted by a Bourne shell. I don't think he understood (he is a marketing guy) but he did press "Enter" and I was banned from approaching the laptop for the time being (still not sure why; I didn't execute the code after all, I only wrote it).

A few more drinks later someone decided a coding challenge was in order (or possibly that was what the laptop had been there for all along). The specification that was given was something like this:

Print numbers from 1 to max excluding numbers that have duplicate digits.

I don't quite remember the PHP and Python solutions but they each involved a dozen lines of code containing hash tables and some people monopolising the laptop for upwards of twenty minutes. After queuing for all that time I finally get to the keyboard and I announce I could do it in three lines.

#!/usr/bin/perl -w

for (my $_ = 0; $_ <= $max; $_++) {
    print "$i\n" unless /(.).*$1/;

# Acunu ftw

The comment was added after the marketing guy insisted. If you know some Perl and are familiar with golfing this looks like crap but I was drunk. Someone then proceeded to claim it was inefficient (and the backreference makes it indeed O(n^2) for n the number of digits) and I agreed with him. There was also some kind of syntactic mistake (I rewrote the above from memory) but by the time someone tried to run it I had let go of the keyboard and was back to drinking.

Anyway, an hour later I was home, a bit more sober and I realised that:

My "final" implementation would be something like this;

$ perl -E'/(.).*\1/||say for 1..10**10'

A few minutes after telling my story on IRC twisla came up with something even shorter using sed:

$ seq 1 $max|sed -e'/\(.\).*\1/d'

Meanwhile the best Ruby and Python fanboys could think of were things like

("1"..max).each { |x| puts x if x.split("").uniq ==  x.split("") }


[x for x in range(max) if len(set(str(x))) == len(str(x))]

I would be curious to see a Caml or Haskell implementation.

Fri, 02 Mar 2012 08:59:47 GMT: Regarding the Ruby solution kyzh claims that you cannot do a split("") on a fixnum. The following is supposed to work:

(1..10**10).each {|x| p x if x.to_s.split("").uniq == x.to_s.split("")}

Back to all articles.