Beefy Boxes and Bandwidth Generously Provided by pair Networks
good chemistry is complicated,
and a little bit messy -LW
 
PerlMonks  

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

by eyepopslikeamosquito (Canon)
on Apr 30, 2009 at 07:31 UTC ( #761053=perlmeditation: print w/ replies, xml ) Need Help??

"To be competitive at Perl golf, you have to be a Perl expert, with years of language experience" -- Yorkey

"Rubbish! In TPR 3, Mickut of Finland was on the leaderboard two hours after he learnt Perl! And Perl expert Petdance, despite many years of Perl experience, finished more than 80 strokes behind the leaders in the Fonality golf challenge" -- me

-- Yorkey and me arguing during a lunchtime walk to Kirribilli

Were it not for this chance argument during a lunchtime walk with my workmate and good friend, Yorkey, I probably would have given up the Roman to Decimal golf game after a few weeks. After all, I was completely stuck at that time with my Perl solution and had no fresh ideas to try out. However, Yorkey's stubborn refusal to change his point of view provoked me into proving my point to him by playing this golf in languages I hardly knew, namely Ruby, Python and PHP.

That's not my earring! ... All right, what's going on?

-- My (non-hacker) wife after finding audreyt's earring sitting on our bedside table

I decided to start with Ruby because I at least had a passing familiarity with that language after audreyt stayed for a few days at my home while my wife was out of town. During her stay, we went through the library section of the Pickaxe book together because Audrey felt it would make a great model for documenting the Perl 6 libraries. Unfortunately, the absent-minded Audrey left one of her earrings behind on our bedside table and I assumed it belonged to my wife, so just left it there. On her return, my wife saw the earring sitting on her bedside table and freaked. I had previously told my wife that Perl hacker "autrijus" was coming to stay for a few days while she was away. Luckily, when I hastily explained that autrijus had become audrey, my wife judged it unlikely that I would invent such a story and quickly calmed down. :-)

After a full month of play, the Perl leader was robin on 60 strokes, with Ruby languishing far behind on 73. So I naturally thought it "impossible" for Ruby to overtake Perl in this game -- and ludicrous to suggest that I might be able to beat my Perl solution in Ruby. My expectations were much lower than that; I simply wanted to be competitive in Ruby (anywhere in the 70s would be fine) so as to shut Yorkey up.

Taking the Lead in Ruby

Since I'd already worked out some basic magic formulae by that time, I naturally started converting these to work with Ruby. Unfortunately, in addition to mapping M -> 1000, D -> 500, C -> 100, L -> 50, X -> 10, V -> 5, I -> 1, I needed to further map the trailing newline to zero because I could find no short way of removing it in Ruby. In Perl, the trailing newline was easily removed via /./g. This extra newline mapping invalidated most of the Perl magic formulae I had previously found, so I had to adjust my magic formula searcher and start searching all over again.

This program might contain the fastest known existing implementation of full forward crypt

-- Ton Hospel sensationally wins a Perl golf tournament by writing the fastest C program

I won't bore you here with the gory details of my magic formula searcher, written in C, for speed. To get a feel for what these searching programs look like, take a look at my simple one, described in Golf: Magic Formula for Roman Numerals, or Ton's much more complex one.

My new and improved search program found a Ruby-friendly magic formula easily enough, and I was flabbergasted when my first Ruby approach, despite using the nine character each_byte method, was equal leader on 73 strokes!

p=t=0 $<.each_byte{|c|n=10**(238%c%19%4)>>-c%29%2;p<n&&t-=2*p;t+=p=n} p t
As you can see, this is just a straightforward translation of the original algorithm I was using in Perl, albeit with a magic formula replacing the Perl regex-based lookup table. As I was quick to point out to Yorkey, I didn't need to be a Ruby expert to do this, just needed to know the core parts of the language and, more importantly, find a good algorithm.

I started with each_byte only because I couldn't get the shorter getc function to work. For example, this attempt:

n=t=0 t+=n-n*(n<(n=10**(238%c%19%4)>>-c%29%2)?2:0)while c=getc p t
failed to compile with "undefined local variable or method `c'". Following Eugene's advice of "Can't possibly work, try it anyway", I changed c to C (uppercase variables are constants in Ruby):
n=t=0 t+=n-n*(n<(n=10**(238%C%19%4)>>-C%29%2)?2:0)while C=getc p t
and it worked! The screen was littered with "warning: already initialized constant C" messages (written to stderr), but these don't matter to codegolf, which only cares about what is written to stdout. Combining with a well-known Ruby golfing trick of replacing the three-char 238 with the two-char ?ascii-char-with-ord-of-238, shortened my solution to 65. As you might expect, I felt elated at leading the Ruby experts by eight strokes! And, more importantly, forcing Yorkey to eat his words.

Choking on my breakfast cereal

Complacency is dangerous in golf and I had become complacent. If anyone had told me at this time that I could reduce my Ruby solution from 65 strokes all the way down to 53, I would have declared them insane.

After basking for months in my newly acquired Ruby fame, I almost choked on my breakfast cereal when I checked the codegolf leaderboard one morning and noticed that Python golfing god, Mark Byers, had posted a 59 stroke Ruby solution. This was intolerable! Back to work.

After experimenting some more with Ruby's evaluation order, I came up with a weird spaceship operator 60 stroke solution:

n=t=0;t+=n.*1+n<=>n=10**(238%C%19%4)>>-C%29%2while C=getc;p t
I've left the 238 above for readability, but my submitted solution naturally used the ?ascii-char-with-ord-of-238 dirty trick mentioned earlier. This solution introduces another dirty Ruby golfing trick, namely using a .* "method call" for "multiplies" rather than *(...), thus saving a stroke by eliminating the parens. You can try this trick routinely when golfing in Ruby whenever you need to change operator precedence -- though it doesn't always work, Ruby's parsing being pretty quirky, in my experience. By the way, it was this Ruby solution that inspired my weird 62 stroke Perl spaceship operator solution, mentioned in the previous article, an example of transferring ideas from one language to another. Often the hard part in golf is generating new ideas to try, and using multiple languages is a fertile source of fresh ideas.

Alas, I couldn't improve this solution further, so switched to Python, hoping to take revenge on the "Python golfing god" there.

Python Baby Steps

As you might expect by now, my first Python attempt was the same ol' same ol':

t=p=0 for c in map(ord,raw_input()):n=10**(84169%c%5)>>-c%29%2;t+=n-2*p*(p<n +);p=n print t
89 strokes! This solution bears a close resemblance to the earlier Ruby ones. Notice that Python, like Perl, but unlike Ruby, does not need to map the trailing newline because the Python raw_input function removes it.

Two further strokes were whittled easily enough with:

t=p=0 for c in raw_input():x=84169%ord(c);n=10**(x%5)>>x/4%2;t+=n-2*p*(p<n); +p=n print t
Notice too that in Python, alone among the four languages, assignment is not an operator. This proved a chronic nuisance in this game because I couldn't see any opportunity to exploit evaluation order to eliminate the "previous value" variable (p in the Python solution above).

Another generally applicable golfing tip is to study every single built-in function the language has to offer, especially the short ones. When I did that, the Python hash function caught my eye. I wonder if it could be used in a magic formula? Well, it seems to have better properties for this purpose than ord and is only one stroke longer. Definitely worth a try. It did indeed improve things:

t=p=0 for c in map(hash,raw_input()):n=10**(c/619%4)>>c%8/5;t+=n-2*p*(p<n);p +=n print t
... but only by one stroke. 86 strokes now, but still a gaping eight strokes behind the Python golfing god.

Going for the Outright Lead

Necessity is the mother of invention

The Python solutions are different to the Ruby and Perl ones in that you have to either map the hash/ord functions, or assign them to a variable, as in x=84169%ord(c), because all the magic formulae seen so far use the character twice. It occurred to me therefore, that if I could find a magic formula that used each character in the input string once only that would be a big saving in Python. How to find such a formula? I have no idea, but I played around one afternoon, just trying stuff, and stumbled on a gem:

t=p=0 for r in raw_input():n=10**(205558%ord(r)%7)%9995;t+=n-2*p%n;p=n print t

By way of explanation, notice that the magic formula 205558%ord(r)%7 maps M -> 3, D -> 6, C -> 2, L -> 5, X -> 1, V -> 4, I -> 0 as shown in the following table:

Romanm10**m10**m%9995
M310001000
D61000000500
C2100100
L510000050
X11010
V4100005
I011

Generally, formulae that map M -> 3, C-> 2, X -> 1 and I -> 0 are highly effective because applying "%NNNN", where NNNN > 1000, does not mangle the already matching 10**m, so instead of requiring seven lucky hits, you now need only three (D, L and V).

Combining this new formula with the same modulo trick I used to move my Perl solution from 62 to 60 strokes reduced my Python solution to 78 strokes and tied for the lead with Mark Byers!

Code Golf is 10% strategy, 90% tactics

Actually, I've found many different 78 stroke Python solutions, but none shorter. Here are some more variations in the middle line:

n=10**(hash(r+"*N_")%9)%2857;t+=n-2*p%n;p=n n=10**(hash(r+"@M4")%7)%9995;t+=n-2*p%n;p=n n=10**(hash(r*37509)%7)%9995;t+=n-2*p%n;p=n n=10**"IXCMVLD".find(r)%9995;t+=n-2*p%n;p=n n=10**(494254%ord(r)/9)%4999;t+=n/2-p%n;p=n
The last one is noteworthy in that it uses a different mapping, namely M -> 2000, D -> 1000, C -> 200, L -> 100, X -> 20, V -> 10, I -> 2. Also noteworthy is that, because it divides by two (n/2), it also works with a:
t=p=1
initialization. This observation will allow us later to exploit a Ruby built-in variable ($.), which is initialized to one. Note that this second alternative mapping is available, without penalty, in Ruby and Python, but not Perl and PHP, for various complicated tactical reasons. These are the sort of tactical tricks that are crucial when fighting for the lead in golf.

Incredibly, applying what I learnt in my Python diversion to Ruby, plus yet another dirty Ruby trick (using the Perl-inspired Ruby built-in variable $. to eliminate the t=0), enabled me to reduce my Ruby solution from 60 strokes all the way down to 53 and so steal the outright lead from "primo":

n=1;$.+=n/2-n%n=10**(494254%C/9)%4999while C=getc;p$.

Success is never final -- Winston Churchill

Of course, I can't prove that I've found the optimal magic formula. It's also likely that further language or algorithmic golfing improvements will be found, especially given my relative inexperience in Ruby and Python.

In the next installment of this series, I'll show off my PHP solutions.

Leaderboards, end of April 2009

All languages (281 entries):

1st 53 eyepopslikeamosquito Ruby 2nd 55 primo Ruby 3rd 56 flagitious Ruby 4th 58 ySas Perl 5th 58 leonid Ruby 6th 59 bearstearns Perl 7th 59 Mark Byers Ruby 8th 59 kounoike Perl 9th 60 robin Perl 10th 61 arpad Perl

Perl (69 entries):

1st 55 eyepopslikeamosquito 2nd 58 ySas 3rd 59 bearstearns 4th 59 kounoike 5th 60 robin 6th 61 arpad 7th 61 shinh 8th 62 0xF 9th 66 ersagun 10th 66 redneval 11th 66 o0lit3 12th 66 Aidy 13th 67 szeryf 14th 70 ott 15th 73 jojo 16th 73 yvl 17th 73 acura 18th 77 Jasper 19th 78 agenticarus 20th 79 tybalt89 21st 82 yojeb 22nd 82 grizzley 23rd 85 twice11 24th 86 yanick-walloper 25th 87 Ciaran 26th 87 olivier 27th 88 justin 28th 91 SubStack 29th 93 wendelscardua 30th 94 Trinary 31st 95 tripa 32nd 95 dropbear 33rd 95 sprimmer 34th 98 yanick 35th 99 chargrill 36th 99 kjan 37th 99 Jocelyn 38th 100 k12u 39th 102 duranain 40th 104 sphx95

Ruby (86 entries):

1st 53 eyepopslikeamosquito 2nd 55 primo 3rd 56 flagitious 4th 58 leonid 5th 59 Mark Byers 6th 71 shinh 7th 71 tryeng 8th 73 yvl 9th 73 bitsweat 10th 76 ozy4dm

Python (87 entries):

1st 78 Mark Byers 2nd 78 eyepopslikeamosquito 3rd 79 tryeng 4th 79 hallvabo 5th 80 tha 6th 80 primo 7th 81 BjarkeEbert 8th 85 hiro.suzuki 9th 91 mick 10th 91 gtalpo

PHP (62 entries):

1st 70 eyepopslikeamosquito 2nd 89 hiro.suzuki 3rd 89 Methedrine 4th 89 W 5th 89 Trinary 6th 90 arpad 7th 90 angpoo 8th 91 rollercoaster375 9th 92 El Hombre Gris 10th 92 morten

Leaderboard Update

One month later, the leaderboard changes are:

hallvabo Python 79 -> 72 hendrik Python 94 -> 90 d3m3vilurr Python 108 -> 101 yvl Perl 73 -> 61 falsetru Python 216 -> 95 Leinad Perl -> 152 eyepopslikeamosquito Python 78 -> 72 eyepopslikeamosquito PHP 70 -> 68 Kalindor PHP -> 93 tomatoring Python -> 295

References

Comment on The golf course looks great, my swing feels good, I like my chances (Part II)
Select or Download Code
Re: The golf course looks great, my swing feels good, I like my chances (Part II)
by wazoox (Prior) on Apr 30, 2009 at 13:43 UTC
    Oooh even more to wait :) BTW you should think about compiling all of your wonderful PM articles in a book :)
      you should think about compiling all of your wonderful PM articles in a book :)
      I second that :) There is this PerlGolf History Book thing but no real book with a friendly language AFAICT. It'll be nice to have one and I'll definitely add that to my bookshelf. I liked the tone of Perl Hacks, this one will be even better perhaps :)
Re: The golf course looks great, my swing feels good, I like my chances (Part II)
by ambrus (Abbot) on May 01, 2009 at 10:32 UTC

    You know, it doesn't really surprise me that perl isn't always optimal for golf. I've seen it in action in that fibonacci golf tingy at Re: Fibo Golf challenge on 3 monkeys and (OT) Fibonacci numbers in Ruby - final shot - 24 chars etc. Also, when I write one-liners, which I do a lot, and I don't golf on purpose, the ruby ones always turn out to be shorter than the perl ones, only the ruby ones get hard to manage earlier when they grow. Ruby just has a larger, better standard library for basic things, but cpan wins when you need more complicated stuff like xml parsing.

    As for ruby,

    did you look at that golf prelude thingy in ruby-1.9.0? I never tried it, but I've seen it's there. It has some methods and stuff (like Integer.each instead of Integer.times) defined in such a way to ease golfing but that you wouldn't want to use in sane code, and it also defines the equivalent of AUTOLOAD so you can abbreviate methods to the shortest unique prefix or something. I've no idea how you're supposed to use it officially, but it's in file golf_prelude.c, which is called by goruby.c, which I guess you compile to a goruby executable using some hidden makefile switch or something. (Update: though in 1.9.0 you lose the Kernel#getc method that was already depreciated in 1.8.5.)

      Though I'll give a more detailed analysis in my next article, I just did a quick count of the last ten codegolf games. Ruby and Perl always finished first and second in code length: Perl won 6 times, Ruby 4 times. As for the longest solutions, it was: PHP 7 times, Python 3 times. That agrees with my impression when playing these games: Perl and Ruby are (often quite excitingly) vieing for the Silver Cup, while Python and PHP are battling for the wooden spoon. What surprised me enormously is popularity, measured by number of entries: Python 5, Ruby 4, Perl 1. It seems that golf is more popular in Python than Perl nowadays. That shocked me, because four years ago the top google hit for "Python golf" was a lovely pair of Python skin ladies golf shoes. :)

Re: The golf course looks great, my swing feels good, I like my chances (Part II)
by eyepopslikeamosquito (Canon) on May 19, 2009 at 09:37 UTC

    In golf, there are many more failed attempts than successful breakthroughs. That's the nature of the game. To keep the articles reasonably short, I focused on the breakthroughs, omitting many of the failures. To add a dose of reality, and while I'm still able to remember, I thought I'd describe some of my more interesting "heroic failures" in this game. You never know, someone may find an improvement and transform one of these failures into a winner.

    Mapping to Different Number Bases

    Mapping to different number bases is a generally useful golfing technique. While I couldn't find a useful number base mapping for the original M -> 1000, D -> 500, C -> 100, L -> 50, X -> 10, V -> 5, I -> 1, I spied an opportunity later in the game after uncovering the alternative M -> 2000, D -> 1000, C -> 200, L -> 100, X -> 20, V -> 10, I -> 2 mapping, illustrated in the following table.

    Romanoctaldecimal1<<n2<<n
    M20001024109
    D100051298
    C20012876
    L1006465
    X201643
    V10832
    I2210

    Noticing this cute mapping led directly to the following Python 82 stroker:

    t=p=0 for r in raw_input():n=int(oct(2<<6155848/ord(r)%11));t+=n/2-p%n;p=n print t
    As you can see, this solution was not competitive in this game only because of the five stroke Python string to int conversion penalty of having to call int() -- which wouldn't have been required in Perl or PHP. This idea was similarly foiled in Ruby by the need for string to int conversion.

    Equally cruelly, in a language where the string to int conversion is not required, namely PHP, this idea was crushed by the arbitrariness of PHP's internal function names. You see, PHP calls this function not oct, like any reasonable language, but decoct, costing three precious strokes. Aaargh. Finally, in Perl, the oct function converts the other way and I couldn't find any very short way to convert from decimal to octal.

    Eliminating Exponentiation

    Though exponentiation is "natural" for Roman numerals, it does cost around six strokes (10**()), leaving the door open for shorter, if less natural, alternatives -- such as the PHP md5 lucky hit found in the third article of this series.

    Though less ideal than PHP's md5 function, Python's built-in hash function seems the best hope of eliminating exponentiation among the other three languages. Indeed, this 79 stroker proved only one stroke too long:

    t=p=0 for r in raw_input():n=hash(r+"VFkQW")%291*5%1254;t+=n-2*p%n;p=n print t
    This formula should be able to be further shortened with a more direct mapping of a longer magic string, such as:
    n=hash(r+"magicstring")%1234
    Though such a solution should exist -- just like the "proven" shorter PHP md5 solutions -- I was unable to write a fast enough search program to find one.

    Update: found some "six of seven" solutions:

    % 1001: 4 54 19 40 39 73 101 65 49: 1000 500 100 50 10 5 834 7 55 9 41 72 44 7 30 110: 1000 500 100 50 10 5 922 34 83 78 1 106 105 80 69 86: 1000 500 100 50 10 5 811 47 44 104 115 85 115 62 11 111: 1000 500 100 50 10 5 55 51 90 57 45 89 47 88 67 9: 1000 500 100 50 10 5 81 80 2 111 57 25 124 120 74 62: 1000 500 100 50 10 5 253 107 70 81 43 111 3 64 45 82: 1000 500 100 50 10 522 1 118 107 110 22 86 1 79 117 109: 1000 500 100 50 10 624 1 1 16 88 96 24 114 15 119 6 125: 1000 500 100 50 10 494 1 1 20 62 52 8 46 58 12 39 29: 1000 500 100 50 10 779 1 1 23 105 120 47 93 48 104 16 39: 1000 500 100 50 10 5 734* 1 61 61 73 46 107 4 103 114 54: 1000 500 100 50 10 916 1* 1 68 125 58 6 81 39 76 57 34: 1000 500 100 50 10 956 1* 1 77 91 35 121 50 78 4 40 117: 1000 500 100 50 10 5 95* 1 85 79 40 70 115 63 26 96 68: 1000 500 100 50 10 5 553 1 92 16 1 85 33 48 2 109 125: 1000 500 100 50 10 786 1 1 92 36 49 47 64 56 29 87 123: 1000 500 100 50 10 26 1 2 24 70 80 56 33 49 14 84 38: 1000 500 100 50 10 5 720 2 55 7 58 19 95 66 106 123 76: 1000 500 100 50 10 5 223 2 78 45 126 107 78 4 125 50 39: 1000 500 100 50 10 996 1 2 119 112 12 43 73 103 42 63 82: 1000 500 100 50 10 5 197 3 3 110 96 21 116 76 79 62 126: 1000 500 100 50 10 5 886* 3 32 11 74 49 87 11 9 97 32: 1000 500 100 50 10 965 1 3 48 91 63 25 24 4 1 60 21: 1000 500 100 50 10 37 1* 3 48 91 63 25 24 4 1 61 21: 1000 500 100 50 10 37 1* 3 64 99 73 123 40 97 68 88 1: 1000 500 100 50 10 370 1 3 82 4 111 53 42 62 67 50 32: 1000 500 100 50 10 910 1* 3 87 44 79 85 80 45 6 107 93: 1000 500 100 50 10 5 448* 3 100 26 46 83 95 28 97 64 88: 1000 500 100 50 10 372 1 3 120 99 112 40 69 102 8 114 14: 1000 500 100 50 10 530 1* 3 124 119 88 127 67 22 113 67 123: 1000 500 100 50 10 954 1* 4 20 27 28 11 64 88 81 120 126: 1000 500 100 50 10 5 191 4 43 14 62 25 58 27 36 68 79: 1000 500 100 50 10 5 29 4 89 72 27 70 115 122 7 50 29: 1000 500 100 50 10 5 289 4 89 72 27 70 115 122 7 51 29: 1000 500 100 50 10 5 273 5 8 124 117 9 72 5 111 96 110: 1000 500 100 50 10 5 878 5 8 124 117 9 72 5 111 112 110: 1000 500 100 50 10 5 622 5 42 77 27 93 51 126 85 59 97: 1000 500 100 50 10 5 936 5 52 94 25 97 87 9 76 114 20: 1000 500 100 50 10 147 1 5 61 120 123 86 20 62 35 42 119: 1000 500 100 50 10 5 315 6 14 32 112 84 121 98 26 116 19: 1000 500 100 50 10 277 1 6 25 53 101 4 114 61 55 56 59: 1000 500 100 50 10 5 247 6 40 29 66 1 11 41 110 84 15: 1000 500 100 50 10 5 183 6 59 34 115 24 123 71 86 85 80: 1000 500 100 50 10 5 922 6 90 30 49 53 77 9 43 49 109: 1000 500 100 50 10 864 1 6 90 40 43 27 11 2 111 83 31: 1000 500 100 50 10 5 335 6 127 122 67 20 12 106 17 47 90: 1000 500 100 50 10 5 89 7 82 45 71 6 60 20 45 122 42: 1000 500 100 50 10 147 1 7 91 114 61 33 121 14 33 127 8: 1000 500 100 50 10 5 960 8 24 74 68 29 46 54 28 45 122: 1000 500 100 50 10 157 1 8 81 99 126 73 33 84 39 23 58: 1000 500 100 50 10 3 1 8 109 37 7 102 98 19 25 27 60: 1000 500 100 50 10 5 143 9 8 60 1 94 6 51 38 78 100: 1000 500 100 50 10 810 1 9 21 3 59 26 7 72 92 114 1: 1000 500 100 50 10 5 107 9 97 39 6 74 69 102 33 28 20: 1000 500 100 50 10 5 307 9 99 60 53 116 57 54 109 36 63: 1000 500 100 50 10 177 1 9 100 85 27 24 79 114 88 2 83: 1000 500 100 50 10 722 1 11 31 6 74 111 80 49 21 5 106: 1000 500 100 50 10 750 1 11 112 65 42 28 21 91 105 107 97: 1000 500 100 50 10 235 1 11 119 73 69 89 121 102 103 82 5: 1000 500 100 50 10 908 1 12 19 63 11 15 120 67 58 102 65: 1000 500 100 50 10 5 167 12 30 27 7 52 91 33 77 80 59: 1000 500 100 50 10 5 574 12 34 117 60 98 3 116 40 62 59: 1000 500 100 50 10 476 1 12 54 14 99 51 123 48 42 84 1: 1000 500 100 50 10 313 1 12 93 75 47 78 84 12 60 83 32: 1000 500 100 50 10 954 1 14 36 71 80 101 39 123 49 33 85: 1000 500 100 50 10 57 1 14 37 20 37 26 91 96 8 51 14: 1000 500 100 50 10 5 448 14 76 18 127 16 48 79 1 27 24: 1000 500 100 50 10 185 1 14 79 111 28 29 81 7 68 121 49: 1000 500 100 50 10 5 301 14 87 50 108 7 117 30 72 61 1: 1000 500 100 50 10 5 942 14 97 109 101 47 78 124 106 98 61: 1000 500 100 50 10 519 1 14 104 76 107 79 22 79 75 112 56: 1000 500 100 50 10 750 1 14 108 43 91 86 71 39 63 93 56: 1000 500 100 50 10 900 1 14 113 51 97 31 112 94 80 67 123: 1000 500 100 50 10 926 1 15 19 103 89 2 124 124 48 50 89: 1000 500 100 50 10 483 1 16 17 30 115 63 98 20 51 55 14: 1000 500 100 50 10 5 13 16 122 8 28 24 106 121 34 69 33: 1000 500 100 50 10 5 608 17 32 37 28 15 44 79 63 34 102: 1000 500 100 50 10 652 1 17 38 34 46 117 66 91 43 93 76: 1000 500 100 50 10 5 115 17 39 32 53 7 127 114 8 77 22: 1000 500 100 50 10 115 1 17 57 37 112 36 73 78 53 39 119: 1000 500 100 50 10 5 63 17 57 107 60 113 117 72 64 56 17: 1000 500 100 50 10 988 1 17 107 81 48 51 8 106 7 62 69: 1000 500 100 50 10 105 1 17 123 66 76 11 24 57 58 7 65: 1000 500 100 50 10 5 974 % 1221: 7 101 33 5 111 70 62 112 97: 1000 500 100 50 10 5 1132 9 35 63 104 98 9 36 113 57: 1000 500 100 50 10 5 819
    Need to unearth around 500 of these to have a good chance of finding an elusive "seven of seven" solution. :-(

    An example "six of seven" solution:

    s=chr(7)+chr(101)+chr(33)+chr(5)+chr(111)+chr(70)+chr(62)+chr(112)+chr +(97) t=0 for r in raw_input():n=hash(r+s)%1221%1131;t+=n-2*t%n print t

    Update 18-May-2014: To clarify exactly what is being searched for, running this program:

    magic = chr(8)+chr(81)+chr(99)+chr(126)+chr(73)+chr(33)+chr(84)+chr(39 +)+chr(23)+chr(58) for r in ["M", "D", "C", "L", "X", "V", "I"]: n = hash(r + magic) % 1001 print r, n
    produces:
    M 1000 D 500 C 100 L 50 X 10 V 3 I 1
    That is, it hits six of the seven Roman numerals. The goal is to find a magic string that produces:
    M 1000 D 500 C 100 L 50 X 10 V 5 I 1
    i.e. one that hits all seven. Such a solution was eventually found as described in detail at The 10**21 Problem (Part I).
    magic = chr(17)+chr(11)+chr(119)+chr(60)+chr(47)+chr(44)+chr(78)+chr(1 +03)+chr(125)+chr(48)

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

    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: See also: Rosetta PGA-TRAM.

    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//

    May 2014 Update: I eventually took the lead back at 71 strokes by using a magic formula in this form:

    hash(r+"magicstrng")%1001
    as described in detail in a four-part series at The 10**21 Problem (Part I).

      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: perlmeditation [id://761053]
Approved by Corion
Front-paged by grinder
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (18)
As of 2014-12-18 15:09 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (56 votes), past polls