Syntactic Confectionery Delight | |
PerlMonks |
The golf course looks great, my swing feels good, I like my chances (Part V)by eyepopslikeamosquito (Archbishop) |
on Dec 09, 2009 at 13:24 UTC ( [id://811919]=perlmeditation: 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: 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:
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: 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: 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:
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: 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:
Plugging this into my original solution produced: Much prettier now! Just need to routinely apply some tactical tricks to see how low we can go. 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: 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: produced the required clock face: 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:
This little printf distraction led directly to the following 102 stroker: 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:
I was surprised and delighted to find a competitively short magic formula that did just that, as shown in the table below:
This new, and most weird, magic formula produced the desired single stroke improvement: 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:
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
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
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: 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 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: 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: 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:
High School Trigonometry
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: 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!
... which leads to a five stroke shortening: 96 strokes! Mathematics trumps magic formulae. For the record, Jasper's original 101 stroker was: which does not at all resemble mine:
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 93-stroke solution, based on the odd couple's 96-stroke algorithm above, is derived using compression techniques, as described in Compression in Golf: Part I. Leaderboards, December 2009 All languages (342 entries):
Perl (91 entries):
Ruby (67 entries):
Python (124 entries):
PHP (74 entries):
References
Updated 20-dec: Added secret operator reference.
Back to
Meditations
|
|