Your skill will accomplishwhat the force of many cannot PerlMonks

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

by eyepopslikeamosquito (Bishop)
 on May 19, 2009 at 09:37 UTC ( #764874=note: print w/replies, xml ) Need Help??

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+"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)

Create A New User
Node Status?
node history
Node Type: note [id://764874]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chilling in the Monastery: (3)
As of 2020-10-27 12:59 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My favourite web site is:

Results (256 votes). Check out past polls.

Notices?