develooper Front page | | Postings from July 2002

Re: My solution annotated

Thread Previous | Thread Next
Michael W Thelen
July 9, 2002 12:07
Re: My solution annotated
Message ID:
First off, many sincere thanks to the referees for this hole.  You did a great
job overall, and made a really enjoyable hole.

I was amazed to find that my solution was almost identical to Ala Qumsieh's,
except that Ala's was 9 strokes shorter than mine. :-)  Apparently (if I
understand the difference correctly), I had forgotten that doing a substitution
on a string resets the pos value used in /g matches.  Armed with this
realization when I saw the post-mortem today (I've been out of town without net
access for four days), I was able to shave 8 strokes off my score within 5
seconds.  That was a major "D'oh"!

Unlike Ala, I didn't (knowingly) steal my algorithm from anywhere, although I
did steal other algorithms from various places that didn't turn out to be as
short. :-) Here's my solution:

# Read the entire input into $_, and turn on line-processing mode.

# For each line that has the same node on the left and right, replace the
# duplication with a single reference to the node.
s/^(.*) \1$/$1/mg;

# The main part of the algorithm takes place on the right side of a
# substitution.  This is unnecessary, but I didn't see that.  Basically, the
# substitution just makes sure that there is something left in $_.  If there is
# not, then the program exits normally.

# $& is the string matched in the while condition. Basically, each node (series
# of non-space characters) is represented by $& at some point during this loop.
# If this node occurs in $_ with a space before it, then there is some
# predecessor node that has not yet been removed, so we do nothing and move on
# to another node.
# If not, then we print this node and remove all occurrences of it from $_,
# along with a trailing space or newline char.  We also start over from the
# beginning of the program (the beginning of the -n while loop, actually).  The
# redo is also unnecessary, and removing both the substitution and this redo 
# yielded the immediate 8-stroke improvement.
/ \Q$&\
/||(print$&)&s/^\Q$&\E\s//mg&redo while/\S+/g;

# If we reach this point, then two things are true: 1) $_ is not empty. 2)
# Every node that is left has some predecessor node that cannot be removed.
# That means we have found a loop.  We die by calling the undefined subroutine
# "&a".  I thought division by zero was more clever, but I couldn't figure out
# how to make it shorter.

# The end of the completely unnecessary substitution.

-- Mike

Michael W. Thelen
eval unpack u,'M*"1C/2<P,BDN-"`U+C`A(RLG*3U^>2\A+48O82UZ+SME=F%L*"1C+B(G=2HG

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