|No such thing as a small change|
Re: Drunk on golf: 99 Bottles of Beerby eyepopslikeamosquito (Chancellor)
|on Feb 16, 2012 at 12:09 UTC||Need Help??|
I contacted experienced Polish golfer 0xF mentioning my article and asking if he'd like to share his original 165-stroke solution -- which led this competition for over a year in its early stages.
Instead of sharing, however, he wanted to keep on competing! Divulging nothing, he snatched the lead once again by posting a 160-stroker.
What on earth was 0xF up to? Had he shortened his original 165-stroker? Or my 161-stroker? Or found a completely new approach? I had no way of knowing yet could hardly ignore this provocation.
Exploring All Possible Variations
I'd been quite lazy with my 161-stroker in that I had neglected to explore all possible variations. Laziness may be one of the three virtues of the Perl programmer but definitely not of the Perl golfer. No, you have to work hard, exploring every possible variation, just in case one of them allows a surprising tactical trick.
So I started by reorganizing my 161-stroke solution like so:
This is nothing more than a simple rearrangement. However, on seeing it written that way I immediately noticed that the /, 99\D+/ regex was false all the time within the loop, becoming true only after loop termination ... which means that the default regex (i.e. //) is not affected within the loop because that very short // notation represents the last successful match.
Hmmm. That means if I can eliminate the annoying /s/, I can shorten s/^// by one stroke to s///. Yet if I eliminate the /s/ I must also delete the ridiculously short $&. That is like losing an old friend. And what are the chances of finding a short enough replacement? Looks impossible, but I have to try at least.
Without the /s/, all we have left to distinguish the first time through the loop from subsequent iterations is the s/// expression. What changes after this expression is executed for the first time? Well, as far as I can tell only $_ and the regex "side-effect" variables $&, $', $`, @+, @-. So we need to find a short expression using one of those six. Since $_, $&, $' and $` all look hopeless, that only leaves @+ and @-.
I remember some very happy golfing moments with good ol' @-: I used it in my winning Roman to Decimal solution and fondly remember a marvellous stunt pulled by ySas where he used @- as a multiplier in s/(M)|D/4x@-x5/eg thus distinguishing a matching M from a matching D.
Can I mimic ySas here? Yes! You see, there are zero elements in @- before the first s/// and one element thereafter (corresponding to the offset of the start of the (always) successful match, there being no sub-patterns). So @-, somewhat flukily, has exactly the right values for a multiplier -- 's'x@- -- which shortens my solution by a single stroke:
What next? Well, I can't see anything more. However, if 0xF found a different improvement, and reads this node, we may finally see the magical 160-stroke barrier broken.
Update: The 160-stroke barrier was shattered down to 149 by utilising "pack u" compression, as detailed in this series of nodes.