From:

Date:

May 8, 2002 14:28Subject:

Re: can someone please explain..Message ID:

abc57k$ti2$1@post.home.lunixIn article <BF889CEBEFD2D511B993009027F60ABE1556ED@ag-jasmine-nt4>, Mark Schoonover <schoon@amgt.com> writes: > Thanks to all who are discussing their solutions! I ghosted this one because > I was only able to come up with a partial solution. Now, here's what I've > noticed about the various tourneys - at what percent of the solution is > coming up with a good algorithm?? The Perl itself is tough enough, but from > what I've been able to ascertain from all the tourneys so far is that all > the entries have really cool (tm) algorithms! Where does one pick up those > skills?? Basic questions I know, but this is a major stumbling block for > some, including myself! > > Great job to all those that referred and submitted soln! > > .mark > Among the top-golfers, the algorithm is probably the most important part. Technique in polishing a particular solution useally makes differences of about 3 strokes, the algorithm can easily be 5 strokes or more. E.g. when you consider kolakoski you see 3 basic algorithms: 1) Take a sequence of numbers, and replace each by that many times the alternating first two arguments. repeat until you have a sequence long enough to print, and print the first part (as much as requested) (e.g. rick's solution) 2) Walk the sequence of numbers, and add that many times the alternating arguments at the end. Output the multiplier each time for as many times as requested. (e.g. my solution) 3) extend the sequence by 1 digit at the end each time. this means you need a counter for when to switch alternating arguments (bob's solution) In my case I thought of method 1 and got 57. Rick did better in the technique and made it a 54. Method 2 got me another 57 which is about as good as that one gets I think (if you don't need to print "\n" it can be written as this 50: eval'$_.=chop()x$1.$ARGV[$|--];print/$&(.)/;'x pop) And method 3 i totally missed and has been optimized by Mtv to 51. So: Method 1: 54 Method 2: 57 Method 3: 51 It's interesting to note that (almost ?) no golfer thought of all three methods, which is in fact fairly typical. This is why Bob can often beat everybody. He usually gets to see all ideas. The method I tend to use is to first try to look at a problem in as many ways as possible. And if I think of a new view, I always make it into a program, even if I think it'll never be short. First of all you will probably think of several optimizations while writing it down, and it will deepen your understanding of the hole. After a few days you normally start to really understand the structure of the problem and should try to dispassionately think of fresh approaches. E.g. here are a few cantor views: - a base 3 counter. any 1 in the expansion means " ", all others are "-" - start with "-". Repeatedly extend a string first with length spaces then add the string itself - start with "-". repeatedly replace each char by "char space char" - start with a long sequence of "-"'s, replace the middle third by spaces, repeat recursively for each third. Another important step is to quickly scan perlfunc and perlop. There are probably functions/operators that are in fact useable, but you hadn't considered yet. Just work through them one by one and ask yourself "can i use hex in this problem" ? "can i think of ANY way to use vec ?" unpack ? split ? grep ? map ? for ? e.g. one way to think of cantor is that if you use a multistep method building the result, you must extend the sequence by about a factor 3 each time. So you might think of: - using "x" to extend a series by a factor 3 or add by a factor 2 to itself - use some form of $first.$middle.$last - the same as the above but now formulated as s/$/twice the string length/ or s//twice the string length/ or s/.*/three times the string length/ - using s/one char/three chars/g in some way - using s/no chars/two chars/g in some way - using map{three things} repeatedly on a sequence - extend an array using $#array = $number, then make the contents or printing do something intelligent Using this and some basic counting i concluded that the 34-stroke cantor just *HAD* to use s/one char/three chars/g and that what I was missing was setting up $_ or $\. So I went to perldoc perlvar and read about all things that automatically set $_ and there was reminded of using "for". I miscounted the \n when trying that and though I had found yet another 36 while I had in fact found a 35 which almost certainly would have ended as 34. So the method worked even though I misapplied it. At least this way of thinking would probably allow almost anyone to discover some version of the basic s/./$& $&/g inside a loop.Thread Previous | Thread Next

- can someone please explain.. by Jasper McCrea
- RE: can someone please explain.. by Mark Schoonover
- RE: can someone please explain.. by Tuomo Salo
**Re: can someone please explain..**by perl-golf- Re: can someone please explain.. by Mtv Europe
- Re: can someone please explain.. by Jay Tilton
- Re: can someone please explain.. by Mtv Europe
- Re: can someone please explain.. by Marcelo E. Magallon
- Re: TPR(0,3) in review by Marko P. O. Nippula
- Re: TPR(0,3) in review by Peter Makholm
- Re: can someone please explain.. by perl-golf
- Re: can someone please explain.. by Peter Makholm
- Re: can someone please explain.. by Yanick

nntp.perl.org: Perl Programming lists via nntp and http.

Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About