Dirk-Jan reminded me of the Perl Golf and Code Golf contests, both of which have the aim of solving a simple programming task in as few characters of source code as possible. See his post for a stunning example.

One of the open challenges is to work out the prime factors of a given number. To make things a little more difficult, the output must be printed in a specific format:

7000: 2^3 5^3 7
123456789: 3^2 3607 3803

Here is one of my attempts at a Ruby implementation, which is 97 bytes after removing the final trailing newline:

print”#{n=gets.to_i}: ”
(2..n).each{|x|i=0;n,i=n/x,i+1while n%x<1
print x,i<2?’ ‘:”^#{i} “if i>0}

Then we switched to Perl, and together Dirk-Jan and I managed to come up with a version which is just 82 bytes after removing all the newlines (just pipe it through “perl -pe chomp“).

print$n=pop,’:';for(2..$n){
$i=0;$n/=$_,$i++until$n%$_;
print” $_”.”^$i”x($i>1)if$i}

(Be aware that the Ruby version takes its input from stdin, while the Perl program looks at its first command-line argument.)

That’s pretty compact, right? Algorithmically, the code is actually fairly straightforward; probably the most evil trick we use is to employ the ‘x‘ operator, which does string concatenation a given number of times, in combination with the fact that any Boolean expression can be treated as a numeric value of either 0 or 1, as in C (but not in Ruby).

Unfortunately, both of the versions given above are horrendously slow. They have a running time of O(n), while any self-respecting factorization algorithm should be at most proportional with the largest prime factor of n. It took my Pentium-4 system almost 45 minutes to calculate the factors of 2,000,000,000, which a reasonably intelligent high school student could probably have done in half a minute or so. Here is a version which can do it in a fraction of a second, but at the cost of being a whole 10 bytes larger:

print$n=pop,’:';
for($x=2;$n>1;$x++){
$i=0;$n/=$x,$i++until$n%$x;
print” $x”.”^$i”x($i>1)if$i}

So, how are we doing in the contest? Well, we’re not even competing. The leader is currently at an astonishing 76 bytes! I have no idea how they do that. The winning programs are all in Perl, which tends to do very well in this type of contest despite the fact that all variable names are at least two characters. The best Ruby program is 82 bytes, with Python coming in at 100 and PHP at 122.

Another task in Code Golf is to write a program which can solve the famous Towers of Hanoi puzzle, given a random starting position with up to nine disks. The input consists of three lines of text, each giving the sequence of disks for one of the three pegs. For example:

975
864
321

The goal is to print the series of moves needed to get all disks together on peg C, the third one, following the usual rule that at no time may a larger disk be on top of (to the right of) a smaller one. Here is a very simple example run with only three disks:

$ cat simple.txt
31

2

$ ruby hanoi.rb simple.txt
2 to B
1 to B
3 to C
1 to A
2 to C
1 to C

We haven’t spent as much time yet on this one as on the prime factorization problem. Here is my best effort so far:

T,D=[],[:A,:B,:C]
D.each{|t|gets.chomp.each_byte{|x|T[x-48]=t}}
def m s,t
if s>0
m s-1,(D-[t,T[s]])[0]
puts”#{s} to #{t}”
m s-1,T[s]=t
end
end
m T.size-1,:C

This is an embarassing 157 bytes. In the actual contest participants, Ruby is leading the pack this time, with 104 bytes, while the best Perl entry so far is a whole six bytes larger. Go Ruby!

The Code Golf contest is open to participants using Ruby, Perl, Python and PHP. Nonetheless, Jeroen, Jeroen and Raimond, I look forward to you trying to beat the above programs in Java or C#.. 

Tags: code golf, factoring, hanoi, perl, perl golf, prime factors, prime numbers, ruby, towers of hanoi

This entry was posted on Sunday, June 14th, 2009 at 14:57 and is filed under hacks, me. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.