Eugene van der Pijll wrote: > > Among the entries, there were some that had something extra. They used a > new, unique or surprising technique, used an unusual method, or were > just ununderstandable. Some of these are: > > Kolakoski: Rick Klement (54.25) > > I'd like to invite the authors of these solutions to explain these > solutions to the public, or at least the original bits.
OK, I'll give it a shot (pun intended). Here it is: s/.?/$ARGV[1&pos]x$&||2/ge>>9?print$_&'?'x pop,$/:do$0 A little google searching lead me to this page: http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A001083 which has an example that will "generate sequence of sequences by recursion using next1()". It shows the sequence generated, a program that prints it, and the recursive function nextl(), given as: next1(v)=local(w); w=[]; for(n=1,length(v),for(i=1,v[n],w=concat(w,2-n%2))); w Converting this to perl gives: s/./$ARGV[1&pos]x$&/ge with the outer loop controlled by the s///g, the inner loop implemented by the 'x' repetition operator, and $_ being used for both v and w. The mod function was used to flip between 1 and 2 in the result string, and since we had to do Kolakoski for any two digits, some changes were required. I started using $|-- (the golf friendly toggle special variable), and while it worked, it had to be cleared each time through the cycle, and that costs at least seven strokes (see Lars 58.21 for a good example). The $|= part always seemed to be in the way when I was shuffling things around, so I went looking for alternatives, and found one of the same length in [$-[0]%2]. This got me thinking about pos() (especially since pos() is mentioned in the perlvar description of @+, the close cousin to @-. I knew Mtv Europe used /\G/ inside a s///g, so it was worth a shot. So I changed the code to [pos%2], which gives a warning, but [pos()%2] worked :) It does have a hated pair of parentheses, though, so that was the next attack. Fortunately, %2 has a cousin, &1 which does close to the same thing, and when [pos&1] produced the same warning, I could flip the two and that's how I wound up with [1&pos]. I now had the process body. I could do s/./$ARGV[1&pos]x$&/ge enough times, and I would have a Kolakoski string containing the required answer. That only left three things to settle, the initialization, the loop control, and printing the first $ARGV[2] digits of the resulting string. -l $_=2;1until s/./$ARGV[1&pos]x$&/ge>500;print substr$_,0,pop would be one version of this, it's a 62.25. Let's look at it. The initialization is done with $_=2; - why 2? I saw 2 in the web page :) I thought it was there because the two digits were 1 and 2, and they started with the off digit. That turns out to be wrong, 2 will serve as a general purpose seed for any two digits, if you do enough cycles. OK, we now have an initialization that takes five strokes (that's pretty long, we'll get back to it). Let's print. "substr" is a pretty long word, so let's try to do better. Close to print in perlfunc is printf: $_=2;1until s/./$ARGV[1&pos]x$&/ge>500;printf"%.$ARGV[2]s ",$_ 62.24. Slightly better, but wait, look closely, and there's a field width limiting value for strings that takes an argument: "%.*s" so: $_=2;1until s/./$ARGV[1&pos]x$&/ge>500;printf"%.*s ",pop,$_ Cool, three strokes better to 59.23 It's not enough - it's never enough! Keep scanning through the docs - and perlfunc gives a positive: pack. Hmmm pack 'a20', $_ will give a string of length 20 - OK: -l $_=2;1until s/./$ARGV[1&pos]x$&/ge>500;print pack a.pop,$_ 61.26 - longer, bummer :( Keep looking - scan the perlop precedence chart for the thousandth time - notice '&', which on strings, will shorten the longer string to the shorter. How do I make the shorter string? Look around some more and spot 'x', let's replicate a mask character that will pass all the digits of the starting string without change, but is the desired length. a quick trip to "man ascii" (and having done the masking on another golf) shows that '?' is the one printable character that will not change a digit. Let's try it: $_=2;1until s/./$ARGV[1&pos]x$&/ge>500;print$_&'?'x pop,$/ 58.25 - better. The next thing to look at is the loop control: "1until ;". This is a count of eight strokes, partly because I can't nest the until and the s///. Let's see what we need in loop control, and if there isn't something shorter. First of all, where does that >500 come from? The 500 comes from the rules "The third argument will be a number between 1 and 500 inclusive." If I do more than 500 replacements, I'm sure the result string is longer than that, since one of the numbers must be greater than 1. A documented, but little used, fact is that s///g has a return value, the number of substitutions made, which in this case is the length of the original string. That 500 is pretty long, so we'll have to get back to it again. Let's look for short looping structures. 'for' and 'map' are pretty short, but require that the number of iterations be known - which they are not in this solution. I have to loop the s/// until I have a "long enough" string, and that can take over 100 cycles, yet 100 cycles of a 8,9 is horribly long string. So I looked for loop controls with a test in them. Both 1until ; and 1while ; take eight strokes. Sometimes, though, the 1 can be replaced by something useful, and that applies in this case. The $_=2; can replace the 1, leading to: $_.=2until s/./$ARGV[1&pos]x$&/ge>500;print$_&'?'x pop,$/ a 57.23, where I had to change the straight assignment to an append, because the $_.=2 now gets executed each time through. It still initializes when $_ is empty, and adding a 2 to the end of the string each time doesn't hurt, because we're generating a longer string than required. It's still seven strokes for the loop control, though. Hmmm, time to look at one of my favorites, the ?:do$0, cleverly used by Ton in SecretNumber. This one is only six strokes (if all the conditions can be met). One of the rules is "no assignments" because of precedence problems, and I have that $_.=2 in there. It could be left as a separate statement, though, leading to: $_.=2;s/./$ARGV[1&pos]x$&/ge>500?print$_&'?'x pop,$/:do$0 a 57.26, because the ';' is back, so no overall strokes are saved. Now (note: big step coming) since the initialization has changed from "do once" to "do each time", can some advantage be taken of that? That $_.=2; takes six strokes, and I wondered if the s/// could be made "self-starting", which it currently is not, because the '.' pattern requires that $_ contain at least one digit. Time to steal^Wborrow the pattern Eugene used to pass me in even.pl, using a pattern of '.?', which matches each character, and then the empty string at the end. For a string of length zero, it will match once (that sounds good), and for a string of length three, it will match each character, then match once more at the end (that could be OK). How do I know it's matching the empty string at the end? That turns out to be easy - all the digits in the Kolakoski are greater than zero, so I could check $& with a simple test. Let's see: s/.?/$&?$ARGV[1&pos]x$&:2/ge>500?print$_&'?'x pop,$/:do$0 57.24 - but wait, if $& is empty (has value zero), replicating by zero gives a result of length zero, so this can be reshuffled to: s/.?/$ARGV[1&pos]x$&||2/ge>500?print$_&'?'x pop,$/:do$0 a 55.25 - wheee - a saving of TWO whole strokes. These latest two came about by asking the question "can the iteration be made self-starting?". I promised to get back to that "horribly long" 500. Going slowly, operator by operator, through perlop, I paused for a second on the << >> line, and a bell went off in my head. By shifting a number several bits to the right, I could test for greater or equal to some power of two. Cool... Well, that 500 could be any value larger than 500. The next power of two larger than 500 is 512 (2**9) where 9 is only one stroke. That means I could replace the >500 with >511, and >>9 is exactly the same as >511. This leads to: s/.?/$ARGV[1&pos]x$&||2/ge>>9?print$_&'?'x pop,$/:do$0 which is the 54.25 this story started with. To sum up: find an initial algorithm: s/./$ARGV[1&pos]x$&/ge find the shortest "print first part": print$_&'?'x pop,$/ find the shortest loop control: ?:do$0 make it self-starting: .? with ||2 shorten anything that looks long: >>9 I hope this helps someone... (no, I don't, there are already too many excellent golfers). -- Rick Klement
