Thursday, February 11, 2010

Sunday, July 12, 2009

Some code golf

Stumbled into the Code Golf site through a reddit-link yesterday. I had a look around and decided to have a go at the Saving Time challenge. Here's a run-through of my attempt at solving it.

I really recommend that you have a go at it yourself first, it is much more rewarding to solve it on your own! My solution is in no way the optimal one, but still: Here be spoilers, etc! With that out of the way, here is a short description of the problem.

In this challenge you must draw an analogue clock face, using the time provided to you in 24-hour digital format.

Example time (given on stdin):

21:35

Expected result:

        o
  o o

 o o

h o

 o o

  m o
  o

The code golf site allows entries in perl, python, ruby or php. I settled on perl, partly for traditional reasons, but also it's the one I'm most familiar with of the four, even if I don't do much programming in it any more.

First things first, parse the in-data. The obvious way would be to use a regexp in this fashion:
($h,$m)=(<>=~/(\d+)/g);

but since I don't care about readability here I pull a perl-trick out of the tool chest:

<>=~/:/;

This matches the ':' and leaves me with the left hand side/hours in $` and the right hand side/minutes in $'. (Yeah, I kept the 'perlvar' man-page up in a window for the entire session.)

Now I want to place the "hands" in an array @c with 12 positions. Each position should contain 0 for no hand, 1 for the hour, 2 for the minute and 3 if both are overlapping:
$c[$`%12]++;
$c[$'/5]+=2;
Simple enough. All that is left now is the tricky business of drawing the face.

After a couple of false starts I went with a template.
$_="hAxdLgBxxaKmCxxJoDxxaImExxdHgFxhG"
I put it into $_ so I don't have to specify which variable I want to do the operations on. Starting with this I first insert newlines:
s/x/\n/g;
Then convert small-caps to spaces (a=1 space, b=2 spaces ...):
s/[a-o]/' 'x(ord($&)-96)/ge;
the 'e' flag at the end of the regexp lets the replace-part be evaluated as code. $& contains the latest match, ord gives the ascii-value of the character, and ' 'x value, gives value repetitions of the ' ' string.

And finally, the capital letters are replaced with the hands from @c, and output:

/[A-L]/(o,h,'m',x)[$c[ord($&)-65]]/ge; print
In the same manner as the previous line, the replace is evaluated. (o,h,'m'x)[value] is just an array-lookup that converts 0,1,2,3 to 'o','h','m' or 'x'. I discovered that only 'm' need to be in quotes (it's a match operator), the other characters got interpreted as strings by themselves.

All put together it looks like this:
<>=~/:/;
$c[$`%12]++;
$c[$'/5]+=2;
$_="hAxdLgBxxaKmCxxJoDxxaImExxdHgFxhG";
s/x/\n/g;
s/[a-o]/' 'x(ord($&)-96)/ge;
s/[A-L]/(o,h,'m',x)[$c[ord($&)-65]]/ge;
print
The newlines should of course be removed to save a couple of bytes, but I've kept them here for readability.

Success, 154 bytes. Short enough for an SMS, but not quite short enough to fit in a twitter-message.

The #1 spot on the Code Golf-site had solved it in 101 bytes, so I was motivated to at least try to get it twitter-sized.

First thing I realized was that I didn't have to write '\n' for newlines, I could just simple use newlines in the code, which made that replacement unnessary. So I ended up with a template looking like this:
$_="hA
dLgB

aKmC

JoD

aImE

dHgF
hG";
Also, I could shave some bytes off by merging the two replace-operations into one:
s/\S/($t=ord($&)-96)>0?' 'x$t:(o,h,'m',x)[$c[$t+31]]/ge;
This got me down to 133 bytes. And something looking like this:

<>=~/:/;$c[$`%12]++;$c[$'/5]+=2;$_="hA
dLgB

aKmC

JoD

aImE

dHgF
hG";s/\S/($t=ord($&)-96)>0?' 'x$t:(o,h,'m',x)[$c[$t+31]]/ge;print
Good enough for my 140-byte "twitter-limit". I was about to quit there for the evening when I realized I could remove the capital letters from the template completely:
<>=~/:/;$c[$`%12]++;$c[$'/5]+=2;$_="h
dg

am

`o

am

dg
h";s|\S|' 'x(ord($&)-96).(o,h,'m',x)[$c[abs$t++%2*12-$t/2]]|ge;print
Not completely satisfied with the algorithm "abs( ($t++ %2)*12 - $t/2)"that supplies the sequence (0, 11, 1, 10, 2, 9, 3, 8, 4, 7, 5, 6) for the index to the hands, but it got me down to a total of 126 bytes.

And that was that! Now all I have to do is remove another 25 characters from that and I'm in the #1 spot...

I've done another one of the code golf challenges, I'll see if I'll do a write up on it later.