27 Mar

code golf

I came across a new (to me) game yesterday – Code Golf.

The game involves coming up with an algorithm to solve a programming problem, and trying to condense the code for the algorithm into the smallest number of bytes possible.

The first one I tried was this. It was a fascinating problem, and took me a day of musing on it (in the back of my head as I did other things) before I had a solid solution.

After writing the solution, which took 1380 bytes, it was time to start “golfing” it.

At first, I thought I’d try my compressor on it. This shrank it to 825 bytes, but after compression, it couldn’t be worked with anymore, so I thought I’d try compressing it manually.

This resource was fascinating, and gave me a load of pointers.

There were a few small points I came up with myself while working on it:

I prefer to use “\n” instead of “;” for command endings, as it makes code more readable. (the game is about shrinking the code, not obfuscating it)

A saving can be had by combining nested loops:

// before
for(i=5;i--;)for(j=5;j--;)M[i][j]=0
// after
for(i=25;i--;)M[0|i/5][j%5]=0

If you need to push into an array on multiple lines, make a shortcut for the push method:

// before (example)
a=[]
cond1()&&a.push(1)
cond2()&&a.push(2)
cond3()&&a.push(3)
cond4()&&a.push(4)
// after
a=[]
P=a.push
cond1()&&P(1)
cond2()&&P(2)
cond3()&&P(3)
cond4()&&P(4)

If possible, find a maths way of identifying interesting points, instead of comparisons.

// before
if((x==4&&y==4&&z==3)||(x==4&&y==3&&z==4)||(x==3&&y==4&&z==4))dosomething()
// after
if(x*y*z==48)dosomething()

I think this game is really interesting, and it will sharpen my own skills as a programmer, as it taxes the mind not only to find the solution to a problem, but also to express that solution as concisely as possible.

In the end, I was able to solve the problem in 668 characters – that’s 142 characters less than my compressor was able to manage.

Leave a Reply