Beefy Boxes and Bandwidth Generously Provided by pair Networks
Think about Loose Coupling

Comment on

( #3333=superdoc: print w/replies, xml ) Need Help??

Just like the Roman game, analysed to death in previous episodes of this long-running series, I'll unveil here, for the first time, the shortest known solutions in all four languages (Perl, Python, Ruby and PHP) to the more recent Saving Time challenge.

Apart from gaping (or glaring) at this parade of abbreviated-in-the-extreme code, you'll get to look over my shoulder as I describe the circumstances and thought processes behind these depraved creations. I hope you'll find my journey through this competition both interesting and instructive, especially so for the serious, aspiring golfer.

Now to work.

Rules of the Game

In this Saving Time challenge, your program must draw an analogue clock face, using the 24 hour digital time provided on stdin. The format of the input time is HH:MM followed by a single newline.

An input time of 21:35, for example, is displayed as:

o o o o o h o o o m o o
If the hour and minute happen to fall on the same mark, they must be drawn with an 'x'. For example, 01:06 is rendered as:
o o x o o o o o o o o o

To more precisely clarify the required behaviour of a passing entry, see the test program provided in this node.

Getting Started

To get on the scoreboard as quickly as possible, I began this game with a straightforward printf-based approach:

<>=~/:/; $h=$`%12; $m=$'/5; printf'%9s %5s%8s %2s%14s %s%16s %2s%14s %5s%8s %9s',map$_^$h?$_^$m?o:'m':$h^$m?h:x,0,11,1,10,2,9,3,8,4,7,5,6
Weighing in at around 140 strokes I knew, from peering at the leaderboard, that this solution was around 40 strokes too fat. Doesn't matter. Find a working solution, any working solution. Then relentlessly whittle it. Then explore alternative approaches.

Regexes always win (Mtv's law of golf)

Notice how the hours and minutes are extracted from stdin with the <>=~/:/ regular expression via the side-effect of setting the $` and $' special variables. Yet another routine application of Mtv's Law. I wrote this regex down in about four nanoseconds and never contemplated changing it thereafter. I'm sure all the other experienced golfers in the field did likewise and I'd be flabbergasted if someone now concocted a shorter way to do it.

Next we come to the conversion of $h and $m to the 0..11 range, so as to easily compare to each mark on the clock face. Numbering the twelve clock face marks 0..11 seemed the most natural numbering scheme at the time and I never found anything better. A simple and obvious way to perform the conversion is:

$h=$`%12; # converts 0..23 hours to 0..11 clock face mark $m=$'/5; # converts 0..59 minutes to 0..11 clock face mark
The $`%12 and $'/5 expressions are another aspect of my solutions that were found in a few seconds and not changed thereafter.

Of tactical interest here is the annoyance that $'/5 produces a floating point result rather than the desired integer. To achieve the integer truncation, you might try int($'/5) or, shorter, $'/5|0. Shorter still though is to simply ignore it and later use $_^$m -- rather than the essentially equivalent $_-$m -- for the clock face mark test. This works because the integer bitwise xor ^ operator implicitly truncates the floating point $m to an integer value.

A final point to note in this first approach is the curious 0,11,1,10,2,9,3,8,4,7,5,6 sequence. I found this characteristic ordering intensely annoying during this game. Yet if you want to print the clock face on the fly there is no avoiding it, as indicated below:

0 11 1 10 2 9 3 8 4 7 5 6

printf: Getting to Know You Better

General golfing tip: spend hours studying the gory details of all internal functions

I stopped here to pore over the documentation of Perl's printf function. In particular, I was desperate to eliminate the dreaded 0,11,1,10,2,9,3,8,4,7,5,6 sequence.

Hmmm: perldoc -f sprintf. Hang on, what's this? A bizarre "$ placeholder" printf format string syntax, where you can replace %5s, for example, with %8$5s to print the eighth printf argument rather than the next one. You must be joking! No, this ungainly POSIX feature was added to Perl 5.8 in 2002 ... though curiously, it was not added to ANSI C99, presumably because the ANSI C committee found it ungainly. Notice too that this syntax doesn't play particularly well with Perl, where $ is already heavily used for string interpolation. Doesn't matter. Does it reduce my golf score? Yes! You see, the tortuously long 0,11,1,10,2,9,3,8,4,7,5,6 sequence can now be replaced with the much shorter 0..11 like so:

<>=~/:/; $h=$`%12; $m=$'/5; printf'%9s %12$5s%8s %11$2s%14s %10$s%16s %9$2s%14s %8$5s%8s %9s',map$_^$h?$_^$m?o:'m':$h^$m?h:x,0..11
If you're looking for some benefits of playing golf, to negate its many drawbacks, this is a common example of a didactic benefit: being provoked by a golf game into learning more about the language and its core libraries.

Jasper's "god-awful ternary"

The god-awful ternary is where I thought the flab was -- Jasper

The ternary that so displeased Jasper was:

which is essentially identical to my original ternary above, though without storing intermediate values in the $h and $m variables. Note that 'm' requires quoting here due to ambiguity with Perl's m// pattern match operator.

Now I certainly shared Jasper's view that this eyesore had to go. But how?

Being obsessed with magic formulae after the Roman game, and remembering the eccentric string bitwise operations employed by my Acme::EyeDrops module, I wrote a program to search for string bitwise magic formulae. After exhaustively searching all the bitwise string operators, the two shortest magic formulae found by my searcher were:

($_^$h?o:x)&($_^$m?o:'}') H|($_^$h?g:p)&($_^$m?g:u)

Plugging this into my original solution produced:

<>=~/:/; $h=$`%12; $m=$'/5; printf'%9s %12$5s%8s %11$2s%14s %10$s%16s %9$2s%14s %8$5s%8s %9s',map{($_^$h?o:x)&($_^$m?o:'}')}0..11
Much prettier now! Just need to routinely apply some tactical tricks to see how low we can go.
printf'%9s %12$5s%8s o%14s %10$s%16s o%14s %8$5s%8s %9s',map{($_^$`%12?o:x)&($_^$'/5?o:'}')}<>!~/:/..11
109 strokes! Second place already! Woo hoo! My excitement was dampened, however, by the gaping seven stroke chasm separating me from Japan's leading Perl golfer, ySas, on 102 strokes. Worse, this isn't even a valid solution -- it cheats by exploiting the (poor) set of test data provided for this game. I further noticed that none of the other leading golfers were submitting cheating solutions (indicated by a number of fails on the codegolf activity log before being accepted), so it was clear to me that a shorter, non-cheating approach was available. How to find it?

Back to the Drawing Board

The odd looking printf "$ placeholder" syntax had clearly run out of steam. I had to find a new approach. Back to that damned 0,11,1,10,2,9,3,8,4,7,5,6 sequence again. Sigh.

I did find a reasonably short way to generate this dreaded ordering via map:

which, in the context of this game, naturally became:
leading to the following 112 stroker:
$:="s %s%14s %";printf"%9s %5s%8$:s%16$:5s%8s %9s",map{map{($_^$`%12?o:x)&($_^$'/5?o:'}')}$_,11-$_}<>!~/:/..5
Three strokes worse, admittedly. But no cheating this time. How to shorten?

Desperate for some sort of new breakthrough idea, I crawled back to printf again, playing around with little test programs, searching, desperately searching, for something, anything, something new. After some random fiddling, I noticed that running this little test program:

printf "%10.2s", "o\n\n"; printf "%5.1s", "o\n\n"; printf "%10.3s", "o\n\n"; printf "%2.1s", "o\n\n"; printf "%16.3s", "o\n\n"; printf "%1.1s", "o\n\n"; printf "%18.3s", "o\n\n"; printf "%2.1s", "o\n\n"; printf "%16.3s", "o\n\n"; printf "%5.1s", "o\n\n"; printf "%9.2s", "o\n\n"; printf "%10.2s", "o\n\n";
produced the required clock face:
o o o o o o o o o o o o
Fascinating. And if you multiply each of the printf format strings above by 10, you get:
Hmmm, all these numbers are in the byte range 0-255. Whoa, all these numbers are in the byte range 0-255! All these numbers are in the byte range 0-255!! I felt elated at this stroke of luck for it means these numbers can be easily encoded in a twelve byte string. And I can derive the required printf format string simply by dividing each byte's ord value by ten.

Actually, there is a considerable range of magic printf format strings that will produce the required clock face, as shown in the table below:

Indexprintf format

This little printf distraction led directly to the following 102 stroker:

printf"%@{[.1*vec'XXXXXXXXXXXX',$_,8]}s",($_^$`%12?g:p)&($_^$'/5?g:u)| +"H "for map{$_,11-$_}<>!~/:/..5
where XXXXXXXXXXXX above is a string with ord values from the table above, for example: 102, 109, 169, 189, 169, 92, 119, 51, 21, 11, 21, 51.

Caught ySas at last! Tied for the lead on 102!

Of note in this solution is the use of the famous Baby Cart @{[]} secret operator. Though usually too long for golf, baby cart wins here because a lone 's' requires quoting to disambiguate it from Perl's s/// substitution operator.

Return of the Magic Formulae

Around this time, I was also composing a Python solution. While conducting my Python research, I was playing around with some weird magic formulae encoding three separate values in a single byte. That is, I was searching for some magic to allow me to encode the dreaded ordering, the number of leading spaces, and the number of trailing newlines in a single byte, as illustrated in the table below:

Indexdreaded orderingleading spacestrailing newlines

I was surprised and delighted to find a competitively short magic formula that did just that, as shown in the table below:

Indexmagic byte (m)m%12318%m/9m/85
012008.67 -> 81.41 -> 1
147114.00 -> 40.55 -> 0
225317.22 -> 72.98 -> 2
322101.11 -> 10.26 -> 0
4194213.78 -> 132.28 -> 2
5990.33 -> 00.11 -> 0
6183315.00 -> 152.15 -> 2
74481.11 -> 10.51 -> 0
8196413.55 -> 132.31 -> 2
95574.78 -> 40.65 -> 0
1012557.56 -> 71.47 -> 1
1124668.00 -> 82.89 -> 2

This new, and most weird, magic formula produced the desired single stroke improvement:

print$"x(318%$_/9),(($_-$`)%12?o:x)&($_%12^$'/5?o:'}'),$/x($_/85)for u +npack<>!~/:/.C12,'XXXXXXXXXXXX'
where XXXXXXXXXXXX above is a string with ord values: 120, 47, 253, 22, 194, 9, 183, 44, 196, 55, 125, 246. Which enabled me to sneak one stroke ahead of ySas and take the outright lead on 101 strokes!

Jasper Appears in my Rear View Mirror

After a few months, the overall leaderboard read:

1st 101 eyepopslikeamosquito Perl 2nd 102 ySas Perl 3rd 111 shinh Perl 4th 112 flagitious Ruby 5th 114 Mr.Rm Perl 6th 115 ozy4dm Perl 7th 115 0xF Perl 8th 116 edenc Perl 9th 116 smokemachine Perl 10th 116 ksk Ruby 11th 118 Jasper Perl

Satisfied at having finally wrested the lead, and all out of fresh ideas to try, I stopped playing this golf for a while. Note the innocuous golfer lying in 11th place.

Several months drifted by, like a dream, relaxing, basking. Then a most disturbing sight in my rear view mirror. It was that innocuous 11th placed golfer!

Jasper and I go back a long way, having competed against each other from the earliest Perl golf days eight years ago; our most recent battle was in the Fonality Christmas golf challenge where I luckily overtook him in the dying minutes of the game. Maybe Jasper wanted to take revenge for that, I don't know. What I do know is that every week or so, he would, Zen-like, trim a single stroke from his lovingly crafted solution. No rush, no hurry. Maybe he had his 101 all along, and wanted to torture me slowly. Who knows? But he kept on coming, relentlessly whittling, one stroke at a time, until, finally, he caught me on 101 strokes. During what was perhaps the longest whittle in golfing history he even found time to taunt me by sending cheery messages to my Perl Monks inbox.

I naturally assumed he'd found the same magic formula approach I had, and the slow stroke by stroke progression was explained by having to wait for various runs of his magic formula searcher to complete ... until his last incomprehensible (to me) message to my inbox where he remarked that his final triumphant whittle was simply changing .523 to .52. WTF? It then became clear that we had totally different 101 stroke solutions!

The Odd Couple

Ah... you assumed. My dear, you should never assume. You see, when you assume, you make an "ass" out of "u" and "me".

-- Felix Unger in the Odd Couple

In addition to assuming we had similar solutions, Jasper and I formed an odd couple in this game.

When I first sighted Jasper's 101 stroker, I knew, after picking myself up off the floor, that combining our two 101 strokers would allow us to finally smash the magical 100 stroke barrier. Even though I was bruised and it was three in the morning, I felt so happy. Of course, I kicked myself at missing two key insights easily noticed by Jasper. But it didn't matter. I was too amused that we had totally different solutions!

Two Dimensional Arrays

Oh, and remember that Perl has two dimensional arrays (I use them so rarely in real code that I tend to forget they exist).

-- eyepopslikeamosquito offers advice on the Joy of Ascii Art golf

Having already used two dimensional arrays in the Joy of Ascii Art golf game -- and even having the temerity to offer advice on their use -- I still can't believe I didn't think to try them in this game. This is the hardest part of golf: having that lightbulb go off in your head, thinking of an idea in the first place. After that, it's just a matter of technique as to how far you can push the idea.

Had I thought to try them in this game, I probably would have started out with a simple test program, something like:

$z[ 0][ 8] = 'o'; $z[ 1][11] = 'o'; $z[ 3][14] = 'o'; $z[ 5][15] = 'o'; $z[ 7][14] = 'o'; $z[ 9][11] = 'o'; $z[10][ 8] = 'o'; $z[ 9][ 4] = 'o'; $z[ 7][ 1] = 'o'; $z[ 5][ 0] = 'o'; $z[ 3][ 1] = 'o'; $z[ 1][ 4] = 'o'; print"@$_\n"for@z;
Running this little test program produces exactly the right shaped clock face. I often use little test programs like this when playing golf to explore techniques and make sure I fully understand them before attempting to apply them to a working solution.

Autovivification is the automatic creation of a variable reference when an undefined value is dereferenced.

-- wikipedia Autovivification

Autovivification is unique to Perl. And it's so compact that it's often a winner at golf. To help me better understand it, I tried to emulate the Perl test program above in Ruby, coming up with:

z=[] (z[ 0]||=[])[ 8] = 'o' (z[ 1]||=[])[11] = 'o' (z[ 3]||=[])[14] = 'o' (z[ 5]||=[])[15] = 'o' (z[ 7]||=[])[14] = 'o' (z[ 9]||=[])[11] = 'o' (z[10]||=[])[ 8] = 'o' (z[ 9]||=[])[ 4] = 'o' (z[ 7]||=[])[ 1] = 'o' (z[ 5]||=[])[ 0] = 'o' (z[ 3]||=[])[ 1] = 'o' (z[ 1]||=[])[ 4] = 'o' puts{|i|(i||[]).join" "}
Because Ruby does not autovivify, you must manually create the empty lists -- using the || operator in the test program above. Notice, by the way, that 0 and "" evaluate to true in Ruby, so the Ruby || operator is closer to Perl 5.10's // "defined or" operator than its venerable cousin, the || "or" operator.

The other feature unique to Perl that makes two dimensional arrays a winner here is the automatic insertion of a single space between array elements when interpolated into a string, as in:


The X and Y coordinates of the two dimensional array representing the clock face marks are shown below:


Once more we are in luck, for they are all less than 16, allowing two of them to be easily encoded in a single byte. So we can add to our long tradition of 12-byte encoded string solutions:

sub k{vec'XXXXXXXXXXXX',$i++,4}$c[k][k]=($_^$`%12?o:x)&($_^$'/5?o:'}') +for<>!~/:/..11;print"@$_ "for@c
where XXXXXXXXXXXX is a string with ord values: 128, 177, 227, 245, 231, 185, 138, 73, 23, 5, 19, 65. 101 strokes! And this one is just one stroke longer:
$c[$_%16][$_>>4]=($i^$`%12?o:x)&($i++^$'/5?o:'}')for unpack<>!~/:/.C12 +,'XXXXXXXXXXXX';print"@$_ "for@c

High School Trigonometry

There's just no sane regularity in this thing. But in "random" mappings with a very small result set like this, the shortest solution is often to make up some magic formula that has no particular meaning, but just happens to give the wanted result.

-- Ton Hospel explaining his original decimal-to-roman magic formula

I learnt golfing legend thospel's lesson too well in this game. You see, there is some sane regularity in this clock face thing ... if you open your eyes to it, as Jasper did.

A clock face is a circle! And, as described at wikipedia, the equation for a circle can be written in parametric form as:

x = a + r cos t y = b + r sin t
where t is a parametric variable, interpreted geometrically as the angle that the ray from the origin to (x,y) makes with the x-axis.

Can this equation be coerced into generating our clock face X and Y coordinates? Yes!

08.00 -> 80.80 -> 0
111.68 -> 111.42 -> 1
214.38 -> 143.12 -> 3
315.40 -> 155.45 -> 5
414.46 -> 147.79 -> 7
511.81 -> 119.53 -> 9
68.16 -> 810.20 -> 10
74.46 -> 49.63 -> 9
81.70 -> 17.97 -> 7
90.60 -> 05.65 -> 5
101.46 -> 13.30 -> 3
114.05 -> 41.53 -> 1

... which leads to a five stroke shortening:

$c[$_*=.52,5.5-4.7*cos][8+7.4*sin]=($_^$`%12?o:x)&($_^$'/5?o:'}')for<> +!~/:/..11;print"@$_ "for@c
96 strokes! Mathematics trumps magic formulae.

For the record, Jasper's original 101 stroker was:

$c[$_*=.52,5.5-4.7*cos][8+7.4*sin]=$`%12-$_?$_^$'/5?o:'m':$_^$'/5?h:x for<>!~/:/..11;print"@$_ "for@c
which does not at all resemble mine:
print$"x(318%$_/9),(($_-$`)%12?o:x)&($_%12^$'/5?o:'}'),$/x($_/85)for u +npack<>!~/:/.C12,'XXXXXXXXXXXX'

I hope you enjoyed the odd couple's Perl battle in this game. In the next and final installment, I'll describe how I golfed this problem in Ruby, Python and PHP.

Update 2012: As if this node were not already long enough, further analysis of this game can be found in Spending Time on Saving Time [golf]. Oh, and a compressed solution, based on the odd couple's 96-stroke algorithm above, is derived in Compression in Golf: Part I.

Leaderboards, December 2009

All languages (342 entries):

0th 96 The Odd Couple (eyepops + Jasper) Perl 1st 101 eyepopslikeamosquito Perl 2nd 101 Jasper Perl 3rd 102 ySas Perl 4th 111 shinh Perl 5th 112 flagitious Ruby 6th 114 Mr.Rm Perl 7th 115 ozy4dm Perl 8th 115 0xF Perl 9th 116 edenc Perl 10th 116 smokemachine Perl

Perl (91 entries):

0th 96 The Odd Couple (eyepops + Jasper) 1st 101 eyepopslikeamosquito 2nd 101 Jasper 3rd 102 ySas 4th 111 shinh 5th 114 Mr.Rm 6th 115 ozy4dm 7th 115 0xF 8th 116 edenc 9th 116 smokemachine 10th 118 kounoike 11th 122 szeryf 12th 124 techierob 13th 125 wendelscardua 14th 125 gabrielmad 15th 126 ugglan 16th 128 dsevil 17th 129 pung96 18th 131 alf 19th 132 sarehu 20th 133 twice11 21st 135 grizzley 22nd 135 scottholdren 23rd 137 semifor 24th 138 arpad 25th 141 bdg 26th 141 JuNe 27th 144 ac18rt 28th 145 ott 29th 147 yvl 30th 148 stephen 31st 149 ian 32nd 149 k12u 33rd 150 yanick 34th 150 ohcamacj 35th 154 4a6f656c 36th 156 Aidy 37th 158 Avenging Dentist 38th 159 amorette 39th 159 jshin 40th 159 spike

Ruby (67 entries):

1st 112 flagitious 2nd 112 eyepopslikeamosquito 3rd 116 shinh 4th 116 ksk 5th 118 leonid 6th 126 tryeng 7th 129 ozy4dm 8th 130 yvl 9th 133 tpope 10th 140 m-satyr

Python (124 entries):

1st 127 eyepopslikeamosquito 2nd 130 hallvabo 3rd 131 tryeng 4th 139 Shvegait 5th 139 jakevoytko 6th 139 recursive 7th 141 morus 8th 146 logan 9th 149 Mark Byers 10th 157 hendrik

PHP (74 entries):

1st 129 eyepopslikeamosquito 2nd 133 ToastyX 3rd 157 queball 4th 161 arpad 5th 167 waldz 6th 180 chikuwa 7th 186 Stormx 8th 191 zhato 9th 199 Kloopy 10th 208 phoe


Updated 20-dec: Added secret operator reference.

In reply to The golf course looks great, my swing feels good, I like my chances (Part V) by eyepopslikeamosquito

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?

    What's my password?
    Create A New User
    and all is quiet...

    How do I use this? | Other CB clients
    Other Users?
    Others avoiding work at the Monastery: (5)
    As of 2017-07-21 22:22 GMT
    Find Nodes?
      Voting Booth?
      I came, I saw, I ...

      Results (336 votes). Check out past polls.