Beefy Boxes and Bandwidth Generously Provided by pair Networks Frank
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Re: The golf course looks great, my swing feels good, I like my chances (Part II)

by eyepopslikeamosquito (Canon)
on May 27, 2009 at 11:21 UTC ( #766382=note: print w/ replies, xml ) Need Help??


in reply to The golf course looks great, my swing feels good, I like my chances (Part II)

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.

My first thought was that he'd performed some fancy functional footwork on my magic formula. So I tried:

x=[10**(205558%ord(c)%7)%9995for c in raw_input()] print sum(n-p%n*2for p,n in zip([0]+x,x))
Hmmm, 92 strokes. Nope, this approach looked like a hopeless dead-end.

So, I went back to good old Eugene again ("can't possibly work, try it anyway") and just stared at my original 78 stroker:

t=p=0 for r in raw_input():n=10**(205558%ord(r)%7)%9995;t+=n-2*p%n;p=n print t
What might hallvabo have chopped? Well, that damned p "previous value" variable is an eyesore ... so I just hacked it out:
t=0 for r in raw_input():n=10**(205558%ord(r)%7)%9995;t+=n-2*t%n print t
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 72 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.

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, unlike Guido, I very much like the reduce function, so, for fun (not golf, because reduce never wins at golf), I put this to the proof.

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:

use List::Util 'reduce'; print reduce{$a+$b-2*$a%$b}map{10**(19&654115/ord)%1645}<>=~/./g
and Python:
print reduce(lambda t,n:t+n-2*t%n,(10**(19&654115//ord(r))%1645for r i +n raw_input()))
and Ruby 1.9:
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}
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 /).

Update: Two slightly different implementations:

# 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()))
One stroke longer, but the "7&" seems better than "19&" because it ensures that 10**(expr) always fits into a 32-bit integer. Note that "%9995" and "%1999" both work fine in this formula.

As usual, this new Python algorithm may lead to further improvements in the other languages. My PHP solution will definitely improve a little, though I don't see much hope for the Perl and Ruby ones.

Perl Update: After further thought, I was able to shave some more strokes from my Perl solution.

Ruby Update: Though I found some new 54 stroke Ruby solutions using the new algorithm, for example:

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
I couldn't improve on my original quirky 53 stroker:
n=1;$.+=n/2-n%n=10**(494254%C/9)%4999while C=getc;p$.

Once again defeated by Ruby's unusual treatment of booleans. That is, most other languages would allow you to shave two strokes from:

while 0<N=10**(494254%getc/9)%4999/2
via:
while N=10**(494254%getc/9)%4999/2
... but not Ruby, where numeric zero evaluates to true.

The shortest Ruby 1.9 solution I can see is 55 strokes:

n=t=1;$<.bytes{|c|t+=n/2-n%n=10**(494254%c/9)%4999};p t

Feb 2012 Update: The shortest solution at therubygame: Roman numerals. What are they good IV?, played in Ruby 1.9.3, was 58 strokes:

n=s=0;roman.bytes{|c|s+=n-2*n%n=10**(205558%c%7)%9995};s+n
Of course, that is easily shortened by two strokes:
s=0;roman.bytes{|c|s+=(n=10**(205558%c%7)%9995)-s%n*2};s

June 2011 Python Update: I found out much later that hallvabo's original 79 stroke solution was:

a=0 for e in raw_input():v=10**(84179%ord(e)%5)>>(e in'VLD');a+=v-2*a%v print a
which he reduced by seven strokes simply by plugging in my improved magic formula. Interestingly, his original magic formula:
10**(84179%ord(e)%5)>>(e in'VLD')
has the same basic structure as the first decent one I found for Perl, namely:
1 . E.(3^77%ord)%7>>y/VLD//

Update: See also: Rosetta PGA-TRAM.


Comment on Re: The golf course looks great, my swing feels good, I like my chances (Part II)
Select or Download Code
Re^2: The golf course looks great... (Part II) ("speed")
by tye (Cardinal) on May 27, 2009 at 13:07 UTC
    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 /).

    Your criteria probably make sense if you are writing C code. I doubt they make sense when writing in any of the languages you are actually writing in.

    In particular, in Perl your fastest formula is going to be the one with the fewest operations. Dispatching a Perl opnode is going to be (I'm guessing) two or three orders of magnitude slower than even something "slow" like a division machine-language instruction.

    - tye        

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://766382]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (14)
As of 2014-04-24 10:36 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (565 votes), past polls