|Keep It Simple, Stupid|
Compression in Golf: Part IIby eyepopslikeamosquito (Canon)
|on Oct 06, 2012 at 07:18 UTC||Need Help??|
That six stroke investment was returned with interest, the compressed solution being three strokes shorter than the original.
Well, that seemed pretty easy. So let's apply the same trick to the classic 99 Bottles of Beer.
That chore turned out to be more laborious than expected, and of a completely different character. You see, the shortest (160-stroke) 99 Bottles of Beer solution:
apart from being significantly longer, has an entirely different set of pack-hostile bytes to deal with, namely:
How to deal with the sixteen spaces?
I could see only three possibilities:
How to deal with the three newlines?
You can simply replace a hard newline with \n or $/, at a cost of three strokes, one per hard newline.
Alternatively, if you are already using y/v/\40/ to convert spaces, you can sneak in a newline conversion too via y/v_/\40\n/, say, where underscore is used in place of hard newline. This also has a three-stroke penalty.
How to deal with G, T and D?
G can be replaced with \ug or v71, at a cost of two strokes. Similarly, T can be replaced with \ut or v84. That's all I got. Suggestions welcome.
The /, 99\D+/ regex can be replaced with /,.99[^9]*/ or /,.99.*\n+/ at a cost of two strokes.
Back to the game
I really thought I was done with those damned beer bottles. For good. And then Ruby specialist "dmd" goes and posts a (presumably compressed) 157-stroke Perl solution. Well, I could hardly ignore this provocation. Besides, due to dmd's (presumed) lack of Perl experience, I felt quietly confident that I could overtake him without too much effort. Little did I know.
The two (complementary) strategies I tried in this game are:
I quickly discovered that I could make no headway with a mechanical translation of the shortest 160-stroke solution to the "pack u" restricted character set. A different approach was required. So I kept trying different bottle golf algorithms until I found approaches that seemed better suited to the restricted character set environment.
At this early stage, the two shortest solutions I had found were 179 strokes, using a list to get rid of the wretched spaces (i.e. approach 3 above):
and 180 strokes, replacing spaces with "v" then translating them later (i.e. approach 2 above):
Many variations of these two solutions are available.
Disturbingly, that's nineteen strokes longer than the original 160 stroker. In percentage terms, 160/179 = 0.89 is considerably worse than the 96/102 = 0.94 ratio achieved with Saving Time. And, to rub salt into the wounds, I couldn't make either of these solutions fit snugly into any "pack u" shape.
So I reluctantly switched to strategy two above (i.e. focus on shape-fitting) and finally managed to wrest the lead from "dmd" at 154 strokes by shoehorning this longer 182-stroker:
into this "pack u54" shape:
The extra length of this solution is more than compensated for by the perfect fit for the "pack u54" shape, notably the s;;; substitution near the end:
This is a miraculous fit: two strokes are saved by replacing \n with pack's hard newline and another is shaved by hijacking pack's ";" length byte for use as the s;;; substitution delimiter.
After punching the air with my fist, I hastily generated and submitted a 154-stroke solution by running this little program:
Three strokes ahead now. Yay! That should put Ruby upstart "dmd" in his place! Or so I thought. Within a few days however, the tenacious "dmd" struck back by posting a 151 stroke Perl solution. Drat. Back to the drawing board.
Acknowledgement: I'd like to thank mtve and hallvabo for their help in preparing this series.