develooper Front page | | Postings from May 2002

Re: can someone please explain..

Thread Previous | Thread Next
May 8, 2002 14:28
Re: can someone please explain..
Message ID:
In article <BF889CEBEFD2D511B993009027F60ABE1556ED@ag-jasmine-nt4>,
	Mark Schoonover <> 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.


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 Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About