> Date: Mon, 8 Apr 2002 17:54:24 +0100
> From: Adam Spiers <[EMAIL PROTECTED]>
>
> Lars Henrik Mathiesen ([EMAIL PROTECTED]) wrote:
> > I've made a quick rundown of the methods used in the solutions that
> > got under a score of 80 (as an arbitrary cutoff).
>
> [snip excellent analysis/summary]
>
> Thanks for that. I wonder if there are any other methods with
> potential. The only other one I came up with started with
>
> sort map"@{[sort/./g]}_$_",<>
>
> but at the time it looked like it would need a mammoth effort to
> extract the anagram sets in size order. Perhaps it's doable using a
> technique similar to your winning one?
Hmmm... join the result of that sort into a single string, and then
s/^(.+_)(\C+)\n\1(.+)/$_="$2 $3",y+\n++-1||print,$1.$_/ge
until satisfied. Not tested, not even for syntax. Some golfing needed.
And the runtime will probably be horrible! (regex backtracking)
> > In conclusion: There's more than one way to skin a cat, but still only
> > a finite number. But I was a bit surprised to see that noone else was
> > using the same method as I was.
>
> I wasn't. It's *damn* clever. I briefly considered the grep-based
> approach of your earlier attempts but it looked so unpromising I
> quickly gave up. Hmph. What I want to know is, how the hell did you
> manage to pick what was essentially the winning technique from the
> word go? :-) It took me several days just to get sort<>. It's a bit
> like chess really. The best players instinctively know which lines to
> analyse and which to reject.
Believe it or not, I started out with a reasonably straightforward
program, a lot like like this:
#!perl
$set{join '', sort split //} .= $_ for <>;
@set = grep { / / } map { (join ' ', sort split) . "\n" } values %set;
print sort { $a =~ y/ // <=> $b =~ y/ // || $a cmp $b} @set
I find that the fewer fancy tricks I put in when creating a first
working version, the easier it is to find the right way to improve it
later. "Premature optimization hurts."
The point of mentioning this is that I think my final solution is only
about as far removed from this first working draft, measured in number
of mental steps, as say Ton Hospel's is --- and I'd like to believe
that if the way I first chose hadn't worked out, I could have gone
back and tried the other way.
Anyway, for me this whole course has been about changing the order of
operations. Sorting the input before collecting sets instead of
sorting the sets, for instance.
So when I thought that perhaps it would be a good idea to split the
sort of the anagram sets into two, an alphabetical sort and one on set
size, to see if that was shorter, I wasn't tied to a specific string
representation. And since Perl's sort isn't stable, I realized that I
had to do something else instead of the outer sort.
Hmmm... I need the outer sort so that shorter anagram sets get printed
first. So if I can just find the the short ones and print them first,
I don't need the sort. I've swapped it for a multiple traversal.
And I guess that was the seed of the 'one newline at a time' idea.
Once I'd come up with something very like Yanick's solution, I thought
about what was happening to each anagram set. It was getting traversed
multiple times by a regex, but only printed on the one traversal where
it had been processed as many times as the regex matched... and then
the idea struck: Instead of using the external counter, I can let each
anagram set record how many times it had been processed, by changing
it one match at a time --- at least until it had been printed.
So, by thinking about the whole list, I replaced the sort with an
external counter and multiple traversal of the list. And thinking
about each anagram set, I removed the use of the external counter and
the multiple traversal of the set.
With the external counter, originally counting 1..15 or so, reduced to
the role of controlling the number of traversals, it could be replaced
with an iteration over something else. (In response to Steven Turner:
Using $_ as the loop variable there was one of those try-it-and-see
things... it obviously didn't work when it had to be accessible inside
a map, but at this point that didn't apply any more. The same goes for
using the map-over-input-lines for iteration: I originally used %::
because it had entries enough. I worried that using the map would mean
that I got partially built hashes on each traversal, but then I tried
it anyway, and it worked).
Anyway, I think it is impossible to get from the sort-on-prefix
majority version to something like mine in a single mental leap ---
you need to go by way of something like Yanick's version.
But now it's much too late at night. No more explaining myself for
now, I'm not sure this much introspection will be good for my golf
form.
Lars Mathiesen (U of Copenhagen CS Dep) <[EMAIL PROTECTED]> (Humour NOT marked)
