http://www.perlmonks.org?node_id=594299

Any problem in computer science can be solved with another layer of indirection.

-- David Wheeler

Whee, $$$_=$_

-- Juho Snellman celebrates finding that extra layer during the Fonality Golf Challenge

Perl Golf is a hard and cruel game. In this report on the recent Christmas 2006 Fonality Golf Challenge, I hope to not only lay bare the secrets of the golfing masters but also tell some personal stories of triumph and despair that occurred during this fascinating competition.

The Problem

You must read a line of roman numerals from the standard input, for example:

II plus III minus I
and write the result to the standard output:

IV
for this example. Fonality provided a more detailed and precise problem statement.

A Simple Solution

Here's a simple solution to the problem:

#!perl -lp 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]
This easy to understand solution hopefully makes clear some of the important strategic ideas used by the top golfers, namely:
  • Rather than attempting to calculate a running total, $_ is transformed in place. For example, II plus III is transformed into 2 + 3. With that done, eval is employed 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.
  • It turns out that symbolic references are crucial in this game because they are shorter than other lookup techniques, such as hashes. In the simple solution above, a symbolic reference is created for each roman numeral whose value is the corresponding arabic number.

HART: The Hospelian Arabic to Roman Transform

During a Polish Golf Tournament played in March 2004, Ton Hospel rocked the Polish golf community by unleashing his miraculous magical formula to convert an arabic number to a roman numeral.

I've decided to honour this magic formula with a name: HART (Hospelian Arabic to Roman Transform). This name was inspired by the ST (Schwartzian Transform) and the GRT (Advanced Sorting - GRT - Guttman Rosler Transform). Acknowledging Ton's rumoured alien origins, an alternative name is Earthman (Eye-popping Alien Roman Ton Hospelian Magical Algorithm for Numerals). If you can think of a better name, please respond away. :-)

As you might expect, Ton's Polish hosts were astonished by his ingenuity, Grizzley remarking:

You should see some of Golfers after reading your explanation... eyes big like cups of tea, heart attacks, etc.
Curiously, though he competed in this historic original Polish roman game, Grizzley did not employ HART himself in the Fonality challenge, preferring his own clever (and quite short) algorithm that was only seven strokes longer.

Converting plus and minus

This was an interesting little sub-problem featuring the versatile tr/// (aka y///) operator.

If your goal is to transform, for example, II plus III, into 2 + 3, you might dispatch the plus and minus with y/mpislun/-+/d. Of course, if you cared more about jokes than strokes, you'd rearrange the letters to form y/linus.pm/      +-/ instead. Which can be easily shortened, using character ranges, to y/mpa-z/-+/d or even y/il-z/-+/d.

What next? Well, if you are later using something like s/\w+/${$&}/g to convert roman numerals to arabic numbers via symbolic references, a serendipitous side effect of that s/// expression is that any lower case letters remaining in plus and minus will be eliminated! You can therefore shorten to simply y/mp/-+/. As a final flourish, you can shave one further stroke by employing y/m/-/ in harness with s/\w+/+${$&}/g.

Rather than converting, for example, II plus III, into 2 + 3, the leading golfers transformed it into $II +$  III instead. If you're doing that, you can employ y/isl-z/-$+/d to transform the plus and minus, and s''$' to prepend the leading $. An interesting alternative, attempted early in the game by Ton, is to eschew the beloved y/// operator in favour of s///, namely s'^| '+$'g and s/nus/-/g, though that turns out to be one stroke longer.

Putting it All Together

The strategy used by the top golfers in this competition is essentially a three step process:

  1. Convert, for example, II plus III, into $II +$  III.
  2. Build two sets of symbolic references: one mapping roman numerals to their corresponding arabic number, the other mapping (negative) numbers back to the roman numerals. Notice that you must use negative numbers because positive ones (e.g. $3) are read-only variables used by perl's regex engine. The building of this second set is easily recognized by the surreal construct: $$$_=$_.
  3. Eval the expression built in step one and put the result back into $_ for printing, courtesy of the -p option.

As is often the case in golf, one insight leads to another: if symbolic references proved useful for converting one way, why not try to exploit them to convert the other way also? And, in so doing, remove the need for the @R array seen in the first simple solution above.

To clarify this three step process, I've prepared a commented version with the arabic to roman numeral step abstracted into a subroutine and without any arcane golfing tricks.

#!perl -lp # r() converts an arabic number (1..3999 or -3999..-1) to a roman nume +ral # using a non-destructive variation of Ton's magic formula (HART). sub r{my$s;($s.=5x$_*8%29628)=~y$IVCXL426(-:$XLMCDIVX$dfor/./g;$s} y/iul-z/-$+/d; # Step 1: convert plus and minus to +$ +and -$ s''$'; # Step 1: prepend $ $$_=r(),$$$_=$_ for-3999..-1; # Step 2: build two sets of symbolic re +ferences $_=${+eval}; # Step 3: eval the expression

Of interest here is the final line above. Remarkably, ton changed it to *_=eval, with the wry comment "More fun with globs", in only one minute twenty seconds! If Juho, who played brilliantly throughout, had found this final trick he would have tied ton for first prize.

Tactical Tricks

In addition to the overall strategies discussed above, tactics also play a vital role.

As pointed out to me by thospel, constructing the table backwards, from 3999 down to 1, also allows you to safely place the $$$_=$_ inside the s///eg expression, since wrong entries for partial roman strings during the build get fixed later (see Ton's winning 99.56 solution below).

It's also worth noting that counting downwards allows you to safely extend the range from 3999 to 4e3 thus avoiding the nasty edge case bugs that plagued the solutions of TedYoung, szeryf, Sec and Jasper, where the (invalid) 4e3 case tramples on a previously correct entry.

Dueling Flamingos: The Battle of the Last T-Shirt 🦩

Late in this game, there was a gripping duel, silently fought between two gritty characters pounding away on their keyboards in Ottawa and New York. This was the titanic Battle of the Last T-Shirt.

Yanick Champoux is professor of psycho-sexual research at the University of St Andrews

The lead see-sawed back and forth between `/anick Champoux and Michael Wrenn right up until the final bell, with Michael emerging the exhausted victor by a single stroke.

Here is what `/anick had to say after it was all over:

But nevermind that blunderific overlook of the Great Thome of Golfic Knowledge. Nevermind an obscenely tumefied forehead, caused by repeated percussions against my desk during the ever-excruciating quest for the next shaved stroke. What really make me wail like a tax-audited banshee is that the referee just went through the last of the pending entries, allowing m.wrenn to sneak one stroke ahead of me and bump me off the top 20, literally yanking the prized t-shirt off my clenched fists.

m.wrenn, if you are on this list, consider my fist -- yes, that same fist that you so fiendishly robbed from its prize -- shaked in barely suppressed fury in your general direction. And mark my words: one day, I shall have my revenge upon thee!

And here is his final 170.51:

#!perl -lp040 $s=/m/ if/u/;($y=I1V5X10L50C100D500M1000IV4IX9XL40XC90CD400CM900)=~/$&/,$i=$t ++=$s^"$;">($;=$')?-$;:$;while s/.$//}{1while$y=~/(\D+)$i/&&$t>=$i?($_.=$1,$t-=$i):$i--

`/anick was the only golfer imaginative enough to employ the command line switch 040 in harness with the }{ "eskimo greeting" secret operator. I'll refrain from commenting further on his creative masterwork because, frankly, I do not understand it.

Here is Michael's moving response, along with his final 169.51 solution:

I went out to get some dinner and returned to check on my solid 20th Place (securing a prized Fonality/trixbox T-shirt) ... when what to my wondering eyes should appear, but \'anick the Canuck who was now TWO STROKES CLEAR! I CURSEd and I SHOUTed and I called him some names| That Bastr/a//d! That foo|bird! That Flamingo again!!! I'll catch him! I'll pass him! I'll beat him this time! I'll punk him! I'll twizzle and addle his brain! To the top of the board! Past Juho and ton! Now slash away, slash away, slash away all!

When I came to, I was still one stroke back and all my hair had been yanked out and deposited on the floor next to me. That \'akinc! It was after 1AM and I needed inspiration. I went into my closet and tried on all of my T-shirts ... None of them fit! I needed a NEW one!

So, I had another beer (a nice Belgian one) and kept at it and just before 2AM, I saw the light! An extremely obvious 2 stroker that I had tried earlier in a slightly different form. I could feel that feeling of cotton ...

#!perl -lp @@{@@=map{$_,$_.0,$_*100}4,5,9,10}=qw(IV XL CD V L D IX XC CM X C M);f +or$~(@@){s/$@{$~}/"I "x$~/ge}s/I//while s/m\w* +I/m /;$~=y/I//cd;s/I{ +$~}/$@{$~}||$&/gewhile$~--

Top Ten Countdown

The top ten golfers at the close of play were:

PlaceScorePlayerCountry
199.56tonNetherlands
2102.54Juho SnellmanFinland
3108.53*TedYoungUSA
4111.49jojoFrance?
5115.52*szeryfPoland
6118.53pijllNetherlands
7120.51*SecGermany
8122.54eyepopslikeamosquitoAustralia
9126.46*JasperUK
10129.50UtilUSA

In writing this report I became aware that the solutions marked with an asterisk (*) above, though they passed the referee's test program, each contained a bug, failing on one or more of the following test cases:

{ in => "MD plus I\n", out => 'MDI' . "\n" }, { in => "MD minus I\n", out => 'MCDXCIX' . "\n" },
They can all be easily remedied by changing 4e3 to 3999, at the cost of a single stroke. Since I'm sure each of these golfers would have found this trivial fix had the referee's test program been more exhaustive, I've taken the liberty of adjusting their scores above and their solutions below. Please note that I am not the tournament referee and therefore do not have any authority to make a decision on this matter. I bring it to light here only in the interests of historical accuracy.

It is interesting to note that nine of the top 10 had previously competed in the strenuous TPR tournament circuit of 2002. And the only one who hadn't, jojo, had played 12 challenges previously at codegolf.

10. Util (129.50)

Util has limited previous golfing experience, having competed in two tournaments in the 2002 TPR season, finishing the season in 121st place, with winnings of $59,000. Accordingly, I expect he was well satisfied with a top ten finish.

#!perl -lp $==$_,s!.!y$IVCXL91-I0$XLMCDXVIII$dfor$_[$=].=4x$&%1859^7;5!egfor+0..3 +999;@&{@_}=0..@_;y/il-z/-+/d;s/\w+/$&{$&}/g;$_=$_[eval]

Though some strokes can be whittled from this lookup hash approach -- for example, this one:

#!perl -lp s!.!y$IVCXL91-I0$XLMCDXVIII$dfor$X[$_].=4x$&%1859^7!egfor+0..3999;@Y{@ +X}=0..@X;y/m/-/;s/\w+/+$Y{$&}/g;$_=$X[eval]
is 12 strokes less fat -- Util really needed to find the symbolic reference hack to join the leading pack.

9. Jasper (126.46)

Jasper is a very experienced golfer, having competed in ten tournaments in the 2002 TPR season, finishing the season in 13th place, with winnings of $719,600.

Jasper was the highest placed of those golfers who missed Ton's magic roman formula.

#!perl -lp map{y/IVXLC/XLCDM/,s!\d!$&^4?$&^9?V x($&>3).I x($&%5):IX:IV!ewhile//;$ +$_=$n++}@d=0..3999;y/m/-/;s/\w+/+${$&}/g;$_=$d[eval]

What was astonishing here is that Jasper had never heard of mtve's book of golf containing Ton's magic roman formula. This is despite playing in many, many golfs over the years and being mentioned many times in the book himself.

8. eyepopslikeamosquito (122.54)

eyepopslikeamosquito is an experienced golfer, having competed in eight tournaments in the 2002 TPR season, finishing the season in 17th place, with winnings of $652,400.

#!perl -lp sub'_{$;=0;($;.=5x$_*8%29628)=~y$IVCXL426.-X$XLMCDIVX$dfor/./g;$;}y;mp +;-+;;s>\w+>(grep$&eq&_,1..1e4)[0]>eg;$_=_$_=eval

Like Util, eyepopslikeamosquito wasn't really in the game because he failed to find the symbolic reference trick. While Util used a hash lookup, eyepopslikeamosquito tried grep in harness with a sub.

7. Sec (120.51)

Sec is an experienced golfer, having competed in eight tournaments in the 2002 TPR season, finishing the season in 57th place, with winnings of $179,467.

#!perl -lp @%=map{my$a;s/./y!IVCXL91-80!XLMCDXVIII!dfor$a.=4x$&%1859^7/eg;$$a=$/- +-;$a}0..3999;y/i/-/;s/\w+/${$&}/g;$_=$%[-eval]

Of note here, is that Sec only spent half a day on the entire tournament. Impressive.

6. pijll (118.53)

pijll is a champion golfer, having competed in ten tournaments in the 2002 TPR season, finishing the season in 3rd place, with winnings of $3,540,000. Notably, pijll has beaten ton in head-to-head matches on at least three occasions, winning the tournament each time.

#!perl -pl y/i-z/-+/s;for$a(1..4e3){$a=~s#.#($n[$a].=4x$&%1859^7)=~y$IVCXL91-I0$X +LMCDXVIII$d;s/\b$n[$a]\b/$a/g#ge}$_=$n[eval]

pijll is such a classy golfer that had you mentioned in passing, "Erm, (-ugene, why not try using a symbolic reference in this game?", I have no doubt that pijll would have been battling with ton and Juho for first prize a few hours later.

5. szeryf (115.52)

szeryf is an experienced golfer, having competed in one tournament in the 2002 TPR season, finishing the season in 123rd place, with winnings of $56,000. In his only tournament in that season, he thrillingly came from behind to snatch the Beginner's trophy.

Since then he has competed in a number of Polish golf tournaments.

#!perl -pl @;=map{$a=0;($a.=4x$_%1859^7)=~y!IVCXL91-80!XLMCDXVIII!dfor/./g;$$a=$_ +;$a}s''$'>y/isl-{/-$+ /..3999;$_=$;[eval]

4. jojo (111.49)

jojo is a mystery golfer. If anyone knows more about him/her, please let us know. jojo is an experienced golfer, having competed in 12 challenges at codegolf where he/she is currently in 15th place overall.

#!perl -pl s|.|y;CLXVI624.-=;MDCLXXVI;dfor$$_.=5x$&*8%29628;$&|ge,$$$_=$_^Kfor-4e +3..o;s;\w+;${$&}|$&&'-';ge;$_=${+eval}

3. TedYoung (108.53)

TedYoung is an experienced golfer, having competed in three tournaments in the 2002 TPR season (under the moniker Theodore Young), finishing the season in 82nd place, with winnings of $127,200.

#!perl -lp y,iul-~,-$+,d,$_=eval,${$@}=1..!s/./y@IVCXL91-:0@XLMCDXVIII@dfor$@.=4x +$&%1859^7/egfor$...3999,u.$_;$_=$@

TedYoung was the surprise packet of the tournament. He has clearly moved to a higher golfing plane since 2002.

2. Juho Snellman (102.54)

Juho Snellman is a brilliant golfer, having competed in six tournaments in the 2002 TPR season finishing the season in 6th place, with winnings of $1,264,000.

#!perl -pl $_=${s!.!y$XLIVC246,-:$CDXLMVIX$dfor$$_.=8x$&*5%29628;$$$_=$_!gefor-4e +3..s''$'/y/isl-~/-$+/d;eval}

Juho put in a really gutsy performance, gallantly leading the pack relentlessly pursuing ton during the last days. Indeed, only failing to unearth ton's little *_=eval "More fun with globs" trick prevented Juho from sharing first place in this competition.

1. ton (99.56)

ton (aka thospel) is a legendary golfer, having competed in ten tournaments in the 2002 TPR season finishing the season in 1st place, with winnings of $4,384,000 ($4,384,350 now ;-).

#!perl -pl s!.!y$IVCXL426(-:$XLMCDIVX$dfor$$_.=5x$&*8%29628;$$$_=$_!egfor-4e3..y/ +iul-}/-$+ /%s''$';*_=eval

In addition to breaking the magic 100 barrier, ton managed to concoct the first known functional smiley in a golf winner's solution. (-:

Since ton invented the magic formula in the first place, I feel he was a most worthy winner. Congratulations thospel!

References

Acknowledgements: I'd like to thank cog for writing the Acme::AsciiArt2HtmlTable module, which was used to generate the little pictures above. I'd also like to thank Samy Kamkar of LA.pm for refereeing the Fonality tournament on his own. Update: I seem to have hit the size limit of a meditation, anyway the last bit got chopped off, so I had to remove the little orange picture of pijll to get it to fit. :-( Update: Added new "Tactical Tricks" section (thanks thospel) and expanded "Top Ten Countdown" section a bit.