develooper Front page | | Postings from July 2002

Re: My solution annotated

Thread Previous | Thread Next
Juho Snellman
July 8, 2002 11:18
Re: My solution annotated
Message ID:
On Mon, Jul 08, 2002 at 10:19:42AM +0100, Stephen Turner wrote:
> So I thought it would be interesting if players annotated their own
> solutions this month. I for one would like to see what people say about
> their own solutions.

I managed to code myself into a blind alley during the first two days,
and had too little time (due to moving) to golf myself back out. In
addition, my solutions were rather brittle [1], which caused my leap from
77 to 87 at some point.

The basic strategy I used was to select a node that didn't appear
after any other node, print it, remove all of it's occurences from the
input, repeating until done.

Now, there are some problems here:
  * How does one properly pick a node that doesn't appear after any
  * How does one detect loops? 
  * How does one deal with those bloody isolated nodes?

The way I chose to solve the first problem was to double the input
before starting with regexps. I.e. in the following input, any regexp
without lookbehind chooses the 'b' instead of the 'z'. 

 a b
 b c
 z a


 a b
 b c
 z a
 a b
 b c
 z a

A simple /^(\S+)\s(?!\C* \1$)/m selects a proper node. This does have
a problem with isolated nodes, but that's easy (if expensive) to fix
using a nested negative lookahead assertion.

Now then, how are loops handled? Let's use a simple 'a b b a': 

 a b
 b a
 a b
 b a

The regexp (incorrectly) decides that 'b' never appears after any
other nodes, so we print it and proceed to remove 'b':s. To detect
loops, we simply check whether any nodes we were removing were in fact
after some other node, -> s/(^| )(\Q$1\E\s)+/$1&&&1/meg. Thanks to 
the input being doubled, this can only happen if there is a loop.
$1&&&1 was the best way of self-destruction I found for this situation.
The actual last solution tripled the input instead of doubling it, 
allowing the removal of a /m-modifier.

Here's the code: 

#!perl -ln0
$_ x=3;s/(^| )(\Q$1\E\s)+/$1&&&1/megwhile/
(?!\1 ).+ \1

And here it is annotated and slightly reorganized:

#!perl -ln0
# Triple the (slurped with -ln0) input.
$_ x=3;

# Find a node, that isn't "after" any other node, unless the node
# is "isolated" (e.g. 'aa aa'). And...
       /\n(\S+)\s(?!\C*\n(?!\1 ).+ \1\n)/ &&
# ... printing the node succeeds (as it always does)
       print $1 ) {
# Remove any occurences of the node in the input. If a removed instance
# was preceded by a space, there was a loop. In that case, exit with
# error. 
    s/(^| )(\Q$1\E\s)+/$1&&&1/meg

And finally, I'd like to thank the judges for making the game possible.

[1] In fact, 14 of my solutions were declared invalid. Victory!!! 
    Well, a tie for victory, since Sec also got to 14.

Juho Snellman
"C:stä on kehitetty Massachusettsin teknillisessä korkeakoulussa kieli
 nimeltä BCPL."  

Thread Previous | Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About