note
eyepopslikeamosquito
<P>
Shortly after posting this article, I (again) had difficulty swallowing my breakfast
cereal when "hallvabo" -- who had been lurking just one stroke
off the pace -- sprinted past both Mark Byers and myself,
snatching a six stroke lead on a remarkable 72 strokes.
What on Earth was hallvabo up to? I might add that when one golfer
tries to guess what another is doing, they are almost always wrong.
</P>
<P>
My first thought was that he'd performed some fancy functional
footwork on my magic formula. So I tried:
<CODE>
x=[10**(205558%ord(c)%7)%9995for c in raw_input()]
print sum(n-p%n*2for p,n in zip([0]+x,x))
</CODE>
Hmmm, 92 strokes. Nope, this approach looked like a hopeless dead-end.
</P>
<P>
So, I went back to good old Eugene again ("can't possibly work, try it anyway")
and just stared at my original 78 stroker:
<CODE>
t=p=0
for r in raw_input():n=10**(205558%ord(r)%7)%9995;t+=n-2*p%n;p=n
print t
</CODE>
What might hallvabo have chopped?
Well, that damned p "previous value" variable is an eyesore ... so I just hacked it out:
<CODE>
t=0
for r in raw_input():n=10**(205558%ord(r)%7)%9995;t+=n-2*t%n
print t
</CODE>
I was doing this in the middle of the night while lying in bed, without
access to a computer. I could not help but notice though, that the program
was now precisely <B>72</B> strokes in length! Hope! A straw to clutch.
So I ran a few tests by hand and couldn't find an example that broke this abbreviated
new algorithm. And it did indeed pass all 3999 tests
when I finally ran it on a computer the next day.
</P>
<P>
Because I'd been pondering a functional approach, I also noticed
that this neat trick of using the "running total" t for state,
rather than the ugly "previous value" p, made this
new algorithm a perfect fit for "reduce"!
You see, <a href="http://www.artima.com/weblogs/viewpost.jsp?thread=98196">unlike Guido</a>,
I very much like the reduce function, so, for fun (not golf, because reduce
never wins at golf), I put this to the proof.
</P>
<P>
As far as I'm aware, the simple functional algorithm shown below, to convert
from Roman to Arabic, has never been published before. Early in this game, I did
google around for functional algorithms and didn't find anything like it.
So, given that golf is sometimes accused of never producing anything useful,
I hereby lay claim to be the inventor of this golf-inspired algorithm and even give it
a name: the PGA-TRAM algorithm, or, in long-hand,
"Pure-functional Golfic Algorithm - Transform Roman to Arabic Magically".
Here's a sample implementation in Perl:
<CODE>
use List::Util 'reduce';
print reduce{$a+$b-2*$a%$b}map{10**(19&654115/ord)%1645}<>=~/./g
</CODE>
and Python:
<CODE>
print reduce(lambda t,n:t+n-2*t%n,(10**(19&654115//ord(r))%1645for r in raw_input()))
</CODE>
and Ruby 1.9:
<CODE>
p gets.chomp.bytes.map{|c|10**(205558%c%7)%9995}.reduce(0){|t,n|t+n-t%n*2}
# or:
p gets.chomp.bytes.reduce(0){|t,c|t+(n=10**(205558%c%7)%9995)-t%n*2}
</CODE>
I chose the "19&" version of a magic formula here only because the bitwise and & operator is typically
faster than the modulo % operator. BTW, an interesting (non-golf) problem is to find the most
efficient magic formula: for that, I expect you'd try to use "fast" operators (such
as &, ^, |, >>), while avoiding "slow" ones (such as % and /).
</P>
<P>
<B>Update: </B> See also: [id://771219].
</P>
<P>
<B>Update:</B> Two slightly different implementations:
<CODE>
# Perl:
reduce{$a+$b-$a%$b*2}map{10**(7&69303333/ord)%9995}<>=~/./g
# Python:
reduce(lambda t,n:t+n-t%n*2,(10**(7&69303333//ord(r))%1999for r in raw_input()))
</CODE>
One stroke longer, but the "7&" seems better than "19&" because it ensures
that <CODE>10**(expr)</CODE> always fits into a 32-bit integer.
Note that "%9995" and "%1999" both work fine in this formula.
</P>
<P>
As usual, this new Python algorithm may lead to further improvements
in the other languages.
My [id://766633|PHP solution will definitely improve a little],
though I don't see much hope for the Perl and Ruby ones.
</P>
<P>
<B>Perl Update:</B> After further thought, I was able to
[id://768354|shave some more strokes from my Perl solution].
</P>
<P>
<B>Ruby Update:</B> Though I found some new 54 stroke
Ruby solutions using the new algorithm, for example:
<CODE>
t=0;t+=N-t%N*2while 0<N=10**(494254%getc/9)%4999/2;p t
$.+=N-~-$.%N*2while 1<N=10**(494254%getc/9)%4999;p$./2
</CODE>
I couldn't improve on my original quirky 53 stroker:
<CODE>
n=1;$.+=n/2-n%n=10**(494254%C/9)%4999while C=getc;p$.
</CODE>
</P>
<P>
Once again defeated by Ruby's unusual treatment of booleans.
That is, most other languages would allow you to shave two strokes from:
<CODE>
while 0<N=10**(494254%getc/9)%4999/2
</CODE>
via:
<CODE>
while N=10**(494254%getc/9)%4999/2
</CODE>
... but not Ruby, where numeric zero evaluates to true.
</P>
<P>
The shortest Ruby 1.9 solution I can see is 55 strokes:
<CODE>
n=t=1;$<.bytes{|c|t+=n/2-n%n=10**(494254%c/9)%4999};p t
</CODE>
</P>
<P>
<B>Feb 2012 Update:</B> The shortest solution at <a href="http://www.therubygame.com/challenges/5/submissions?order=shortest">therubygame: Roman numerals. What are they good IV?</a>, played in Ruby 1.9.3, was 58 strokes:
<CODE>
n=s=0;roman.bytes{|c|s+=n-2*n%n=10**(205558%c%7)%9995};s+n
</CODE>
Of course, that is easily shortened by two strokes:
<CODE>
s=0;roman.bytes{|c|s+=(n=10**(205558%c%7)%9995)-s%n*2};s
</CODE>
</P>
<P>
<B>June 2011 Python Update:</B> I found out much later that
hallvabo's original 79 stroke solution was:
<CODE>
a=0
for e in raw_input():v=10**(84179%ord(e)%5)>>(e in'VLD');a+=v-2*a%v
print a
</CODE>
which he reduced by seven strokes simply by plugging
in my improved magic formula.
Interestingly, his original magic formula:
<CODE>
10**(84179%ord(e)%5)>>(e in'VLD')
</CODE>
has the same basic structure as the first decent one
I found for Perl, namely:
<CODE>
1 . E.(3^77%ord)%7>>y/VLD//
</CODE>
</P>
<P>
<B>May 2014 Update:</B> I eventually took the lead back
at 71 strokes by using a magic formula in this form:
<CODE>
hash(r+"magicstrng")%1001
</CODE>
as described in detail in a four-part series at [id://1083046].
</P>
761053
761053