Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
PerlMonks  

Compression in Golf: Part II

by eyepopslikeamosquito (Archbishop)
on Oct 06, 2012 at 07:18 UTC ( [id://997591]=perlmeditation: print w/replies, xml ) Need Help??

Preparing our Saving Time solution for a "pack u" makeover, as we performed last time in Compression in Golf: Part I, proved straightforward:

  • "}" was replaced with v125. Cost: one stroke.
  • Hard newline replaced with \n. Cost: one stroke.
  • for loop replaced with map. Cost: one stroke.
  • <>!~/:/..11 replaced with 0..s//<>/e./:/. Cost: three strokes.
In summary, our original 96-stroke solution was transformed into a 102-stroke pack-friendly one like so:
# original 96-stroke solution $c[$_*=.52,5.5-4.7*cos][8+7.4*sin]=($_^$`%12?o:x)&($_^$'/5?o:'}')for<> +!~/:/..11;print"@$_ "for@c # 102-stroke pack-friendly makeover map$c[$_*=.52,5.5-4.7*cos][8+7.4*sin]=($`%12^$_?o:x)&($'/5^$_ ?o:v125),0..s//<>/e./:/;print"@$_\n"for@c#```
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:

@c=(@b=(++$n,bottle.'s'x@-,of,beer),on,the,wall),s//Take one down and +pass it around, @c. @c, @b. /until/, 99\D+/;print$'."Go to the store and buy some more$&"
apart from being significantly longer, has an entirely different set of pack-hostile bytes to deal with, namely:
  • Sixteen spaces.
  • Three hard newlines.
  • Three uppercase characters: T, D and G.
Sixteen spaces. Sixteen spaces! Sixteen spaces!! Aargh! Oh well, I suppose it could have been worse. At least there are no pesky ord 123-126 ({ | } ~) characters to trouble us this time. Yet dealing with those sixteen spaces proved to be an utter pest, as we shall see.

How to deal with the sixteen spaces?

I could see only three possibilities:

  1. Use $" instead of space; for example, replace Take one with Take$"one. Though perhaps the simplest solution, this comes at a horrendous cost of 16 strokes.
  2. Use v (say) instead of space; for example, replace Take one with Takevone. Then later translate via y/v/\40/ or s/v/$"/g. This looks more promising, costing only nine strokes: eight for the translation expression, one for a separating comma. The \40 is unfortunate yet I couldn't find anything shorter.
  3. Use a list and exploit the space automatically inserted between each element when a list is stringified as we already do with @b and @c above. Though this approach has perhaps the greatest potential, there are awkward tactical problems to solve.
If you can think of other approaches, I'm all ears.

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:

  1. Focus on shortness. Seek out the shortest restricted pack-friendly character set solution you can find. Don't worry about formatting the thing.
  2. Focus on formatting. Seek out algorithms that fit the required shape like a glove. Don't stress about shortness.

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):

@m=(@z=(++$n,bottle.$&,of,beer),on,the,wall),s/^/,$"@m.\n\n@m,$"@z.\n\ +u@j/until@j=/s/?(take,one,down,an.d,pass,it,around):(go,to,the,store, +an.d,buy,some,more),/^99/m;print$&.$'.$`
and 180 strokes, replacing spaces with "v" then translating them later (i.e. approach 2 above):
s//\utakevonevdownvandvpassvitvaround,v@s.__/until@s=(@b=++$s.vbottle. +"s"x@b.vofvbeer,onvthevwall),s//@s,v@b._/,/99/;s/$/\ugovtovthevstorev +andvbuyvsomevmore,v@s./;y/v_/\40\n/;print
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:

$_=v71.ovtovthevstorevandvbuyvsomevmore;@z=($b=++$n.vbottle."s"x@+.vof +vbeer,onvthevwall),s;^;\utakevonevdownvandvpassvitvaround,v@z.\n\n@z, +v$b.\n;,y/v/\40/until/,.99[^9]*/;print$'.$&
into this "pack u54" shape:
# 1 2 3 4 5 6 7 #234567890123456789012345678901234567890123456789012345678901234567890 +123 v;$_=v71.ovtovthevstorevandvbuyvsomevmore;@z=($b=++$n.vbottle."s"x@+.v +of. vbeer,onvthevwall),s;^;\utakevonevdownvandvpassvitvaround,v@z.\n\n@z,v +$b. ;,y/v/\40/until/,.99[^9]*/;print$'.$& #234567890123456789012345678901234567 # 1 2 3

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:

s;^;\utakevonevdownvandvpassvitvaround,v@z.\n\n@z,v$b. ;
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:

my $source = <<'PERSEVEROUS'; v;$_=v71.ovtovthevstorevandvbuyvsomevmore;@z=($b=++$n.vbottle."s"x@+.v +of. vbeer,onvthevwall),s;^;\utakevonevdownvandvpassvitvaround,v@z.\n\n@z,v +$b. ;,y/v/\40/until/,.99[^9]*/;print$'.$& PERSEVEROUS my $out = unpack 'u54', uc($source); open my $fh, '>', 'b.pl' or die "error: open b.pl: $!"; binmode $fh; print $fh "eval lc pack u54,'" . $out . "'";

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.

References

Acknowledgement: I'd like to thank mtve and hallvabo for their help in preparing this series.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlmeditation [id://997591]
Approved by Athanasius
Front-paged by Athanasius
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others chanting in the Monastery: (4)
As of 2024-03-28 21:07 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found