|Perl: the Markov chain saw|
Re^2: The golf course looks great, my swing feels good, I like my chances (Part III)by eyepopslikeamosquito (Canon)
|on Apr 25, 2010 at 07:03 UTC||Need Help??|
Though I'd long stopped searching for fresh ideas to try in this game, a little while after this ToastyX-provoked epiphany, I could not help but wonder if the string bitwise & PHP golfing trick might somehow be similarly applied to the older Roman to Decimal game.
I started with an inspection of my previous best PHP solution:
There's a lot to dislike about this code. Much nicer is:
While such a solution undoubtedly exists (as argued last time), I don't have a powerful enough computer to find it. The reason such a long (ten character) magic string is likely to be required is because hitting the longer Roman numbers is so improbable; that is, the probability of a random MD5 digest happening to start with 100[a-f], 500[a-f] or 1000[a-f] is too low.
Can good ol' string bitwise & help here? To find out, I started by running a little Perl program:
to display the bit patterns of all characters that may appear in a MD5 digest:
Hmmm, though we clearly cannot bitwise & from [a-f] to [0-9] or vice versa, we can bitwise & all digits to zero. For example:
Does that help? Yes! You see, applying &p to the second, third and fourth characters of the MD5 digest transforms any digit in these character positions to zero, making it much more likely to hit the problematic 100, 500 and 1000 Roman numbers.
What about the first character? A simple brute force search program showed that the best we can do here is &u, which transforms [0-9] like so:
thus making a starting 1 or 5 more likely.
Putting these two together, a &uppp bitwise string operation truncates an MD5 digest string to four characters as follows:
The bitwise &uppp operation therefore reduces the possible numbers in a MD5 digest from millions to just thirteen, namely: 0, 1, 4, 5, 10, 40, 50, 100, 400, 500, 1000, 4000, 5000.
The next step was to update my old C search program with an adjusted my_md5 function as follows:
After adjusting M_TARG and related #defines, running this modified search program unearthed a number of five character magic string hits, but none shorter. From the many different five character solutions, I naturally chose one consisting of all alphabetic characters, namely PQcUv.
Because PHP and Perl have essentially the same string bitwise operator behavior, I was able to test these ideas in Perl. You can see more clearly how all this works, by running the following Perl test program:
Note that the ` characters above, the result of applying &p to [a-f], terminate the number when it's used in an arithmetic operation. Note too that for PHP we require the newline case to evaluate to zero (as a000 does above) to terminate the controlling while loop (this is not required in Perl because /./g removes the trailing newline).
Here's an example Perl solution to this game:
Were md5 a built-in Perl function, this would probably be a winning Perl golf entry. Note, by the way, that it may be possible to replace md5 with Perl's built-in crypt function and be competitive in this game.
As you might expect, having a built-in md5 function made this new approach a winner in PHP, as demonstrated by the following 63 stroker:
Curiously, this turned out to have exactly the same length as the (theoretical) long magic string solution postulated earlier:
The shortest known PHP solution to this game is thus reduced from 68 to 63 strokes, and without requiring a super computer.
A general golfing lesson to take from this little episode is that if you get stuck on one golf game, try another. You may be able to apply tricks learnt in the new game to the one you were previously stuck on.