|Perl: the Markov chain saw|
Re: The golf course looks great, my swing feels good, I like my chances (Part VI)by eyepopslikeamosquito (Chancellor)
|on Feb 28, 2010 at 20:10 UTC||Need Help??|
A few weeks after posting this node, I noticed that Korea's leading golfer, "leonid", had jumped from 118 strokes to 111 strokes, thus snatching the Ruby lead from flagitious and me.
To respond to this provocation, I began by staring at my 112 stroker:
The most obvious candidate for improvement here is the ungainly expression in 'ohmx'[expr], namely:
which can be clarified somewhat by writing as:
where h represents hours (0..23) and m minutes (0..11). How to shorten?
Though relying on inspiration in cases like these might work on a good day, a more dependable approach is to write a program to search for shorter solutions. Accordingly, I wrote the following Ruby brute force searcher:
As an aside, writing "eval" search programs like these seems to be a good way to unearth bugs in dusty corners of a language; at least, I had to remove '**' from the sym array above to workaround various random crashes and hangs of the Ruby interpreter.
Anyway, after dutifully chugging away for several hours, the above program did find a lucky hit, namely:
Further simple variations of this search program found new solutions for the "hours" portion of the expression also, such as:
Combining these two new expressions enabled me to shorten the overall expression as shown below:
and thus match leonid's 111 strokes via:
Of course, I have no idea if this is the same one stroke improvement that leonid found. If not, and he reads this post, I expect shortly to watch him move ahead to 110 strokes. :)
My main point is that relying on inspiration alone, I doubt I would ever have thought of this new shortened solution. That is, writing and running little search programs like these is part and parcel of being a serious golfer.
Update: Some time later, I discovered an easier way to get to 111 by changing the way hours and minutes are extracted from stdin, as shown below:
By way of explanation, note that the Ruby gets function automatically sets $_. And, like Perl, ~/:/ automatically sets $'. Unlike Perl though, ~/:/ returns the (zero-based) index of the match. In this game therefore, ~/:/ always returns two (the index of : in, for example, 12:34).
At first glance, the new method looks like a step backwards because it consumes one more stroke than the original. As is often the case in golf though, a tactical trick is available to shorten it. By pure luck, you see, the original 2&2<<i%12-m expression contains two twos! So we can replace one of them with the return value of ~/:/ thus transforming the new approach from one stroke longer to one stroke shorter:
Alas, this new tactical trick cannot be similarly applied to my shortened ~m%i%12/11 expression because, unluckily, it does not contain a two.
Inspired by this new Ruby magic formula, I was later able to shave a stroke from my 127-stroke Python solution by shortening the last part of the magic formula from:
This (cheating) 126-stroke Python "solution" is not correct for all possible inputs but has a good chance of passing the (poor) set of test data provided for this game. To clarify, I chose 42 in the original magic formula for artistic effect only; any number greater than eleven will do. Replacing 42 with i therefore works for eleven of the twelve string ord values, namely 48, 23, 85, 22, 86, 87, 20, 88, 31, 77, 78 ... but fails for the single ord value that is less than eleven, namely the 9 that forms the string's sixth character.
Hallvabo was kind enough to send me his two best solutions to this game. Here is his (second-placed) 128 stroke Python entry:
where XXXXXXXXXXXX above is a string with ord values 130, 180, 92, 75, 197, 48, 185, 138, 134, 228, 148, 188. And here is an alternate hallvabo 128-stroker:
where XXXXXXXXXXXX above is a string with ord values 72, 71, 205, 34, 158, 9, 147, 20, 160, 43, 101, 186. Note that both these solutions require a leading 3-character BOM (0xef, 0xbb, 0xbf). Note too that hallvabo employed his favourite "slice and dice" trick once again, just as he did in 99 Bottles of Beer.
It never occurred to me to use "slice and dice" in this game. As it turns out, the two different techniques produce similar lengths, as indicated below: