Front page | perl.golf |
Postings from July 2002
Re: My solution annotated
From: Michael W Thelen
July 9, 2002 12:07
Re: My solution annotated
Message ID: 20020709130703.B25215@cs.utah.edu
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.
# 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.
# 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.
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