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.
| Roman | octal | decimal | 1<<n | 2<<n |
|---|
| M | 2000 | 1024 | 10 | 9 |
| D | 1000 | 512 | 9 | 8 |
| C | 200 | 128 | 7 | 6 |
| L | 100 | 64 | 6 | 5 |
| X | 20 | 16 | 4 | 3 |
| V | 10 | 8 | 3 | 2 |
| I | 2 | 2 | 1 | 0 |
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+"V FkQW")%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)
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.
