|Perl: the Markov chain saw|
Golf: Magic Formula for Roman Numeralsby eyepopslikeamosquito (Chancellor)
|on Feb 18, 2007 at 07:50 UTC||Need Help??|
During the recent follow-up codegolf Roman to Decimal game, I explored the other side of this Roman coin, experimenting with a number of different magic formulae to convert a Roman letter to its corresponding arabic number.
This meditation describes my first attempt at cooking up a golfic magic formula, then further offers, for your enjoyment, a simple golf challenge drawn from that experience.
In many golf games, some of the more alluring approaches turn out to be too long to be competitive. During the recent Fonality game, for instance, Daniel Tuijnman's 135.51 and tybalt89's 155.32 were among the most fascinating of the solutions, yet they proved too lengthy to be serious contenders.
So it proved for me during the codegolf Roman to Decimal game where all my shortest solutions were fairly boring, not employing any magic formulae at all. I doubt, therefore, that the magic formulae presented below would be of much practical use in that game ... unless, of course, you find a dramatic improvement on what I've done.
The mapping of each Roman letter to its corresponding arabic number is shown in the table below:
The challenge is to write a subroutine that takes a single valid Roman letter (I,V,X,L,C,D,M) in $_ and returns the corresponding Arabic (or Scientific) representation.
An example solution is:
The score is the number of characters in the subroutine body, 35 for this example.
There are at least two fundamental approaches to this problem:
The Magic Formula Approach
In the example solution above, notice that the last bit, namely:
maps each Roman letter to a digit as follows:
How to shorten this code? Since a %4 modulo operation always produces a digit in the required 0-3 range, an obvious approach is to concoct some sort of magic formula ending in %4.
Brute Force Search Programs
To find such a formula requires a program to search for the elusive magic formula from the vast number of possible ones. Here was my first such program:
These sort of brute force search programs tend to be a bit slow in Perl. And they're not hard to write in C. Accordingly, I rewrote this Perl program in C as follows:
Becoming aware that you've stopped playing Perl golf and are now instead writing little C programs to search for magic formulae is an odd experience. :-) Anyway, running either of these programs produces:
which tells you that there are three magic formulae, the shortest of which is the shortest line above, corresponding to Perl code of:
Thankfully, this is 3 strokes shorter than the original non-magic:
Now that was the first magic formula that popped into my head. There are many, many other possible formulae. How to find the shortest one? I have no idea, but, much to my annoyance, I've now found five others the same length as the original above ... but none shorter. Here are the six shortest I've found so far:
Update: Found three that are one stroke shorter:
and two that are three strokes shorter:
Notice that the solutions ending in >>y/VLD// above divide by two rather than multiply by five and therefore have a slightly different mapping, namely:
Can you find a shorter magic formula?
References Added Later