|Perl: the Markov chain saw|
Re: The golf course looks great, my swing feels good, I like my chances (Part VI)by eyepopslikeamosquito (Canon)
|on Jan 10, 2010 at 18:33 UTC||Need Help??|
Shortly after posting this node, I noticed something baffling on the codegolf activity log:
What was ToastyX up to? If he'd read my node and wanted to catch up, why not just post 129? What's with the failed 127 and 128 attempts? Of course, it's perfectly possible he had not read my node and, Jasper-like, concocted a completely different 129 stroke solution. I had no way of knowing, but was alarmed by those failed 127 and 128 attempts. My previous golfing experience told me that failed attempts like these are frequently followed by a successful submission. To lose the lead now would be intolerable. What to do?
As is my custom in such emergencies, I stared at my 129 stroker:
looking for anything that makes me pull a face. The only thing that truly disgusted me was the hideous "$r$r" expression. Surely something can be done to shorten this. I started by rechecking the excellent wikipedia string function comparison page. Nope, PHP does not support string slices, a la Python and Ruby, no matter how much I'd like it to. The best I could find was substr($r,3) -- which is exactly the same length as before.
PHP function names tend to be quite verbose, so the best chance is surely to apply an operator to $r. What about our old friend, the string bitwise & operator? If I could apply this operator to convert the first three characters of $r to white space, while leaving the last two characters unchanged, that would do it.
To investigate this possibility, I started by running a little Perl program:
to display the bit patterns of the characters of interest, namely:
Hmmm, all these characters can be converted to a space simply by bitwise and'ing them with the ord value 160 character. For example:
Furthermore, all these characters are left unchanged by and'ing them with the ord value 255 character. For example:
We can therefore transform, for example, "12:34" to " 34" via:
where XXXXX is a string with ord values 160, 160, 160, 255, 255. Update: replacing 160 with 176 also works (converting to zeros rather than spaces) as was used by ToastyX.
In the context of a solution to this game, this trick saves two strokes, as shown below:
The shortest known PHP solution to this game is thus reduced from 129 to 127 strokes and has now drawn level with Python in the battle for the wooden spoon.
April 2012 Update
It's perfectly possible he had not read my node and, Jasper-like, concocted a completely different 129 stroke solution.It turns out that is exactly what happened!
In fact, ToastyX found two completely different solutions, one of 129 strokes and one of 130.
His 129-stroke solution:
is essentially a PHP version of the 103-stroke Perl solution described in detail at Spending Time on Saving Time [golf], where GGGGGGGGGGGGGGGGGGGGGGGG is a (bitwise negated) 24 character string with ord values 0, 8, 22, 40, 59, 77, 92, 102, 84, 63, 43, 26, 14, 9, 23, 24, 41, 42, 60, 61, 78, 79, 93, 103, XXXXX is a string with ord values 176, 176, 176, 255, 255, B is ord value 253 (i.e. "}" with the high bit set), S is ord value 160 (i.e. space with the high bit set), and N is ord value 138 (i.e. newline with the high bit set).
ToastyX deserved to win the game with this brilliant concoction because it can easily be shortened by five strokes simply by removing the chr() above. Maybe he knew PHP too well and didn't bother to look up the strpos function. As a PHP novice, I looked it up and was surprised to learn that, in addition to a character string, strpos also accepts an ord value as its second argument, thus making the chr() wrapping unnecessary.
His 130-stroke solution was:
where GGGGGGGGGGGGGGGGGGGGGG is a (bitwise negated) 22 character string with ord values 8, 22, 40, 59, 77, 92, 102, 84, 63, 43, 26, 14, 9, 23, 24, 41, 42, 60, 61, 78, 79, 93.
PHP String "autovivification"
In spirit, ToastyX's 130-stroke solution is akin to a two-dimensional array autovivification Perl entry, for example the 96-stroke:
PHP strings have an odd feature, illustrated by this test program:
That is, instead of failing with a "string index out of range" error, PHP "helpfully" extends the string, filling in the missing bit with spaces!
Note that this is different behavior to Ruby where:
and Perl, where:
Finally, Python strings are immutable, so this technique would appear to be out of the question there.
Curiously, Perl's vec function has similar behaviour to PHP strings, but fills in the empty bit with '\0' characters, not spaces.
So ToastyX's 130-stroke PHP solution can be loosely translated into Perl via:
Of course, at 122 strokes, this is far too long to be a serious Perl golf entry.
Perl program to generate PHP solutions
For convenience, here is a Perl program that generates ToastyX's two PHP entries: