perlmeditation
eyepopslikeamosquito
<P>
The dark art of unearthing magic formulae to improve your
golf score was highlighted recently by [thospel] during
the [id://594299|Fonality Golf Challenge].
</P>
<P>
During the recent follow-up
<a href="http://codegolf.com/roman-to-decimal">codegolf Roman to Decimal game</a>,
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.
</P>
<P>
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.
</P>
<readmore>
<P>
In many golf games, some of the more alluring approaches
turn out to be too long to be competitive.
During the
<a href="http://www.fonality.com/golf/post_mortem.cgi?id=1">recent Fonality game</a>,
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.
</P>
<P>
So it proved for me during the
<a href="http://codegolf.com/roman-to-decimal">codegolf Roman to Decimal game</a>
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.
</P>
<P><B>The Challenge</B></P>
<P>
The mapping of each Roman letter to its corresponding arabic
number is shown in the table below:
</P>
<P>
<table border="1">
<tr><th>Roman</th><th>Arabic</th><th>Scientific</th></tr>
<tr><td>I</td><td>1</td><td>1E0</td></tr>
<tr><td>V</td><td>5</td><td>5E0</td></tr>
<tr><td>X</td><td>10</td><td>1E1</td></tr>
<tr><td>L</td><td>50</td><td>5E1</td></tr>
<tr><td>C</td><td>100</td><td>1E2</td></tr>
<tr><td>D</td><td>500</td><td>5E2</td></tr>
<tr><td>M</td><td>1000</td><td>1E3</td></tr>
</table>
</P>
<P>
The challenge is to write a subroutine that takes a single
valid Roman letter (I,V,X,L,C,D,M) in <CODE>$_</CODE> and returns
the corresponding Arabic (or Scientific) representation.
</P>
<P><B>Example Solution</B></P>
<P>
An example solution is:
<CODE>
# 12345678901234567890123456789012345
sub r{1+4*y/VLD//.E.(3*/M/+2*/C|D/+/X|L/)}
</CODE>
The score is the number of characters in the subroutine body,
35 for this example.
</P>
<P><B>Different Approaches</B></P>
<P>
There are at least two fundamental approaches to this problem:
<ul>
<li> A formula. In this approach, illustrated in the example solution above, you calculate the arabic number from a formula containing the Roman letter.
<li> A lookup table. Here, you lookup the arabic number corresponding to a Roman letter from some sort of lookup table or data structure. AFAICT, this approach does seem to produce the shortest solutions. I won't discuss this approach further in this meditation.
</ul>
</P>
<P><B>The Magic Formula Approach</B></P>
<P>
<blockquote>
<P>
<I>
There's just no sane regularity in this thing. But in "random" mappings
with a very small result set like this, the shortest solution is often
to make up some magic formula that has no particular meaning, but just
happens to give the wanted result.
</I>
</P>
<P align="right">
<small>
-- Ton Hospel <a href="http://groups.google.com/group/pl.comp.lang.perl/browse_frm/thread/6e0afdfe37ec51be/dbf17d1a9c9adee0?hl=en&fwc=1">explaining his original decimal-to-roman magic formula</a>
</small>
</P>
</blockquote>
</P>
<P>
In the example solution above, notice that the last bit, namely:
<CODE>
3*/M/+2*/C|D/+/X|L/
</CODE>
maps each Roman letter to a digit as follows:
</P>
<P>
<table border="1">
<tr><th>Roman</th><th>Digit</th></tr>
<tr><td>I</td><td>0</td></tr>
<tr><td>V</td><td>0</td></tr>
<tr><td>X</td><td>1</td></tr>
<tr><td>L</td><td>1</td></tr>
<tr><td>C</td><td>2</td></tr>
<tr><td>D</td><td>2</td></tr>
<tr><td>M</td><td>3</td></tr>
</table>
</P>
<P>
How to shorten this code? Since a <CODE>%4</CODE> modulo operation always produces
a digit in the required <CODE>0-3</CODE> range, an obvious approach is to
concoct some sort of magic formula ending in <CODE>%4</CODE>.
</P>
<P><B>Brute Force Search Programs</B></P>
<P>
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:
<CODE>
for my $m (1 .. 999) {
for my $n (1 .. 99) {
for my $p (4 .. 9) {
$M = ord(M)x3%$m%$n%$p;
$D = ord(D)x3%$m%$n%$p;
$C = ord(C)x3%$m%$n%$p;
$L = ord(L)x3%$m%$n%$p;
$X = ord(X)x3%$m%$n%$p;
$V = ord(V)x3%$m%$n%$p;
$I = ord(I)x3%$m%$n%$p;
if ($M==3 && $D==2 && $C==2 && $L==1 && $X==1 && $V==0 && $I==0) {
print "m=$m n=$n p=$p: M=$M D=$D C=$C L=$L X=$X V=$V I=$I\n";
}
}
}
}
</CODE>
</P>
<P>
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:
<CODE>
#include <stdio.h>
#define magic(v,m,n,p) ((v) % (m) % (n) % (p))
#define MATCH_M(M,D,C,L,X,V,I) ( (M)==3 \
&& (D)==2 && (C)==2 \
&& (L)==1 && (X)==1 \
&& (V)==0 && (I)==0)
int main(int argc, char* argv[])
{
int m, n, p;
int I, V, X, L, C, D, M;
for (m = 1; m <= 999; ++m) {
for (n = 1; n <= 99; ++n) {
for (p = 4; p <= 9; ++p) {
M = magic(777777, m, n, p); // 777777 is ord(M)x3
D = magic(686868, m, n, p); // 686868 is ord(D)x3
C = magic(676767, m, n, p); // 676767 is ord(C)x3
L = magic(767676, m, n, p); // 767676 is ord(L)x3
X = magic(888888, m, n, p); // 888888 is ord(X)x3
V = magic(868686, m, n, p); // 868686 is ord(V)x3
I = magic(737373, m, n, p); // 737373 is ord(I)x3
if (MATCH_M(M,D,C,L,X,V,I)) {
printf("m=%d n=%d p=%d: M=%d D=%d C=%d L=%d X=%d V=%d I=%d\n",
m, n, p, M, D, C, L, X, V, I);
}
}
}
}
return 0;
}
</CODE>
</P>
<P>
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:
<CODE>
m=75 n=50 p=4: M=3 D=2 C=2 L=1 X=1 V=0 I=0
m=734 n=13 p=4: M=3 D=2 C=2 L=1 X=1 V=0 I=0
m=737 n=92 p=5: M=3 D=2 C=2 L=1 X=1 V=0 I=0
</CODE>
which tells you that there are three magic formulae, the shortest
of which is the shortest line above, corresponding to Perl code of:
<CODE>
ord()x3%75%50%4
</CODE>
Thankfully, this is 3 strokes shorter than
the original non-magic:
<CODE>
3*/M/+2*/C|D/+/X|L/
</CODE>
</P>
<P>
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:
<CODE>
sub m1{1+4*y/VLD//.E.ord()x3%75%50%4}
sub m2{1+4*y/VLD//.E.ord()*49/3%54%4}
sub d1{1 .E.ord()*39%73%7%5>>y/VLD//}
sub d2{1 .E.ord()*38/9%62%4>>y/VLD//}
sub d3{1 .E.~-ord()*41%52%5>>y/VLD//}
sub d4{1 .E.(8^ord)*29%65%4>>y/VLD//}
</CODE>
<B>Update</B>: Found three that are one stroke shorter:
<CODE>
sub d5{1 .E.(72^ord)*5/7%5>>y/VLD//}
sub d6{1 .E.(6^ord)%72%7%4>>y/VLD//}
sub d7{1 .E.(76^2+ord)%7%5>>y/VLD//}
</CODE>
and two that are three strokes shorter:
<CODE>
sub d8{1 .E.(3^77%ord)%7>>y/VLD//}
sub m8{5**y/VLD//.E.(42^88*ord)%5}
</CODE>
</P>
<P>
Notice that the solutions ending in <CODE>>>y/VLD//</CODE>
above divide by two rather than multiply by five and therefore
have a slightly different mapping, namely:
</P>
<P>
<table border="1">
<tr><th>Roman</th><th>Digit</th></tr>
<tr><td>I</td><td>0</td></tr>
<tr><td>V</td><td>1</td></tr>
<tr><td>X</td><td>1</td></tr>
<tr><td>L</td><td>2</td></tr>
<tr><td>C</td><td>2</td></tr>
<tr><td>D</td><td>3</td></tr>
<tr><td>M</td><td>3</td></tr>
</table>
</P>
<P>
Can you find a shorter magic formula?
</P>
<P><B>References</B></P>
<P>
<ul>
<li> [id://759963]
<li> [id://594299]
<li> <a href="http://www.fonality.com/golf/">Christmas 2006 Fonality Golf Challenge</a>
<li> <a href="http://codegolf.com/roman-to-decimal">codegolf.com Roman to Decimal game</a>
<li> <a href="http://groups.google.com/group/pl.comp.lang.perl/browse_frm/thread/6e0afdfe37ec51be/dbf17d1a9c9adee0?hl=en&fwc=1">Original Polish Golf where Ton first used his magic formula</a>
</ul>
</P>
<P><B>References Added Later</B></P>
<P>
<ul>
<li> [id://1083046]
<li> [id://1009253] by [primo] (2012) (<I>"the most difficult part of finding a magic formula is not writing the search algorithm, but knowing what to search for in the first place"</I>)
</ul>
</P>
</readmore>