Code Golf: My Thought Process on “Saving Time”

Posted on August 25, 2008
Filed Under Programming, Programming Languages |

My week was going so well. I moved into a new apartment that cut my commute time by 2/3, and I found an unsecured network accessible from within the confines of my apartment. Nothing else to do, I was expecting to get some good work done on one of my Lisp projects. My friend Steve ruined it by sending out the following mass-email:

http://codegolf.com/saving-time I dare you to beat my score!

I go to the site and see that it gives you a problem definition, some examples, and ranks you on Perl, Ruby, Python, and PHP.

Saving Time

Input

A single 24-hour time into STDIN, such as 21:37 or 09:03.

Output

A clock laid out like the following:

        o
    o       o

 o             o

h               o

 o             o

    m       o
        o

This would be the associated output for 21:37. Minutes get rounded down to the nearest 5, and if the ‘h’ and ‘m’ fall on the same element of the clock, an ‘x’ appears instead.

First approach: Calculate each clock position

Here is the end result of my first attempt. This may have been my second or third submission: (Note: I now know that there are optimizations I could have used)

I=raw_input()
T=[0]*12
T[int(I[0:2])%12]+=1
T[int(I[3:5])/5]+=2
L=['o','h','m','x']
F=lambda i:L[T[i]]
print "%9s\n%5s%8s\n\n%2s%14s\n\n%s%16s\n\n%2s%14s\n\n%5s%8s\n%9s"%(F(0),F(11),F(1),F(10),F(2),F(9),F(3),F(8),F(4),F(7),F(5),F(6))

This baby clocked in at 234 bytes.

I coded using the algorithm that I’d use if I had to write the program “for real” (for some value of real.)

We have a list that represents the following clock positions:

T=[12:00, 1:00, 2:00, ... , 11:00]

We then add 1 in the proper position for the hours, and 2 for the minutes. When we’re printing, we print the proper character from L=['o','h','m','x']. Easy, huh?

When I came home from work the next day, I saw that my friends’ scores were significantly lower than mine.

Second Approach: Optimizations and Tricks

Every byte counts. I talked to two of my friends, Rob (who now holds the lead in Python with 143), and Steve (who has 148 in Perl, tied with my current score), and started comparing tricks for small parts of the program. I got hints for newlines and list slices, and found an awesome ternary hack for Python.

I also did some work to combine steps. Python’s good support of functional programming building blocks (lambda, apply, map, etc) played a big part in this. The algorithm is still basically the same, but more happens “on-the-fly.”

My code is now as follows:

I=raw_input()
h=int(I[:2])%12
m=int(I[3:])/5
print'''%9s
%5s%8s
 
%2s%14s
 
%s%16s
 
%2s%14s
 
%5s%8s
 
%9s'''%tuple(map(lambda c:[['o','m'][c==m],['h','x'][h==m]][c==h],(0,11,1,10,2,9,3,8,4,7,5,6)))

This puts me at 194 bytes. I have broken the 200 mark! Note that this program could still be a lot shorter as-is! I just didn’t know this when I submitted it. I was almost certain I was bottoming out for this method.

A conversation I had with Rob gave him the insight to cut his Python program down from a bytecount in the 160s to a bytecount in the 140s. My program is still a bloated cow in comparison.

Third Approach: One-liner

I decided to write a one-liner to see if I could gain any insight into the problem. It didn’t end up helping, but it is at least an example of functional programming in Python:

print"%9s\n%5s%8s\n\n%2s%14s\n\n%s%16s\n\n%2s%14s\n\n%5s%8s\n%9s"%apply(lambda h,m:tuple(map(lambda c:[['o','m'][c==m],['h','x'][h==m]][c==h],(0,11,1,10,2,9,3,8,4,7,5,6))),apply(lambda a,b:(a%12,b/5),map(int,raw_input().split(':'))))

It is the equivalent to this (commented and slightly better spaced) program:

# Reads input, splits on ':', casts to int, and
# processes hour and minute
hour,minute=apply(lambda a,b:(a%12,b/5), map(int, raw_input().split(':')))
 
# Based on hour/minute, returns a list of the proper
# character for each location on the clock face
clockChars=map(lambda currentNum:[['o','m'][currentNum==minute],['h','x'][currentNum==minute]][currentNum==hour],(0,11,1,10,2,9,3,8,4,7,5,6))
 
# Prints out the clock face
print"%9s\n%5s%8s\n\n%2s%14s\n\n%s%16s\n\n%2s%14s\n\n%5s%8s\n%9s"%tuple(clockChars)

Fourth Approach: I’m Not Telling!

In the end, I changed my line of attack completely and developed a version of my program that got me 2nd place for Python (20th overall as of 10:00 Sunday, August 24th, tied with Steve’s Perl program).

I will have to bow down and pledge my allegiance to Rob, as I just can’t get the last 5 bytes.

General Approach

I had a few guidelines that got me down to this program length:

Popularity: 13% [?]

Comments

Leave a Reply