|Perl: the Markov chain saw|
Re: The golf course looks great, my swing feels good, I like my chances (Part II)by eyepopslikeamosquito (Chancellor)
|on May 27, 2009 at 11:21 UTC||Need Help??|
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:
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:
What might hallvabo have chopped? Well, that damned p "previous value" variable is an eyesore ... so I just hacked it out:
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:
and Ruby 1.9:
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: See also: Rosetta PGA-TRAM.
Update: Two slightly different implementations:
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:
I couldn't improve on my original quirky 53 stroker:
Once again defeated by Ruby's unusual treatment of booleans. That is, most other languages would allow you to shave two strokes from:
... but not Ruby, where numeric zero evaluates to true.
The shortest Ruby 1.9 solution I can see is 55 strokes:
Feb 2012 Update: The shortest solution at therubygame: Roman numerals. What are they good IV?, played in Ruby 1.9.3, was 58 strokes:
Of course, that is easily shortened by two strokes:
June 2011 Python Update: I found out much later that hallvabo's original 79 stroke solution was:
which he reduced by seven strokes simply by plugging in my improved magic formula. Interestingly, his original magic formula:
has the same basic structure as the first decent one I found for Perl, namely:
May 2014 Update: I eventually took the lead back at 71 strokes by using a magic formula in this form:
as described in detail in a four-part series at The 10**21 Problem (Part I).