in reply to
Re^2: Perl Golf Ethics
in thread Perl Golf Ethics
To do well at Perl golf, perhaps the most important thing is
to unearth the "fundamental insights" into the problem.
Some of the fundamental insights of this golf were:
- Rather than calculating a running total, it's shorter and simpler to convert $_ in place; for example, transform II plus III into 2 + 3. With that done, simply use eval to compute the total.
- The y/IVXLC/XLCDM/ transliteration is a short and sneaky way to multiply by ten.
- You don't need to write two converters: it is sufficient to write an arabic_to_roman() converter. To convert the other way, simply convert 1..3999 into a table or something and do a lookup. I didn't appreciate this at first and foolishly wrote two converters. When I became aware of my blunderific overlook, my score dropped by 40 strokes.
- The shortest way to lookup the number corresponding to a roman numeral is to create a symbolic reference for each roman numeral whose value is the corresponding arabic number. For more fun, a la ton and others, transform, for example, II plus III into $II +$ III and eval that. This is the insight I missed, only trying a hash and a grep lookup.
- You can further eliminate the array of roman numerals by creating a second set of symbolic references mapping negative numbers to roman numerals. Note that for this to work you must use negative numbers, since positive ones (e.g. $3) are read-only variables used by perl's regex engine. As you might expect, not many of the contestants hit upon this final insight, only ton, Juho, and jojo managing it.
Notice that none of these insights depends on knowing Ton's
magic formula.
Golfers like Ton have a knack for finding these insights quickly
and easily, while I struggle; once I find them, it is a simple
matter of golfing technique to whittle down the solution.
For me, the hard part is to find them.
Using the above insights, a simple solution like this:
#!perl -pl
map{$_.=(!y/IVXLC/XLCDM/,I,II,III,IV,V,VI,VII,VIII,IX)[$&]while s/\d//
+;$$_=$n++}@R=0..3999;
y/mp/-+/;s/\w+/${$&}/g;$_=$R[eval]
comes in at around 130. You could get down to around 120, again without knowing
Ton's magic formula, by whittling the arabic-to-roman converter:
#!perl -pl
map{y/IVXLC/XLCDM//s//$&-9?$&-4?I x$&:IV:IX/e&s/I{5}/V/while/\d/;$$_=$
+n++}@R=0..3999;
y/m/-/;s/\w+/+${$&}/g;$_=$R[eval]
To go lower, you'll need to sneak in
y/iul-}/-$+ / somewhere to transform $_ directly into symrefs (e.g.
$II +$ III) that can be directly eval'ed. Doing that allows you to eliminate the
s/\w+/${$&}/g above.
Still further savings are available by replacing the
@R array above with a second set of symbolic references, this time mapping negative numbers back to roman numerals.
While I don't fully understand your shortest 186 solution:
#!perl -pla
%n=I1V5X10L50C100D500M1000=~/(.)(\d+)/g;sub
d{$#_-=$z*2*(@_&&$z<$_)-($z=$_)for@n{/./g};@_}$t+=($.=/p/-/n/||$.)*d
for@F;map{$s.=$_ x($t/d),$t%=d}M,CM,D,CD,C,XC,L,XL,X,IX,V,IV,I;$_=$s
it seems like sour grapes to claim that:
this contest was effectively written for a few people who were in the know, who had seen your magic algorithm, shutting out the rest of us.
As shown above, without knowing Ton's magic algorithm, you could have easily
trimmed 60 strokes off your solution by unearthing the fundamental
insights into the problem.
Update: oops, changed 4e3 to 3999 (4e3 fails test case "MD plus I") plus minor code improvements. Added extra symbolic reference insight.