Front page | perl.golf |
Postings from July 2002
Re: My solution annotated
Thread Previous
|
Thread Next
From:
Michael W Thelen
Date:
July 9, 2002 12:07
Subject:
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.
-ln0
# 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.
s!.!
# $& 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.
&a
# The end of the completely unnecessary substitution.
!e
-- 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
M+"<Z,D<U4SU<(B%!.T9=5#HF-5(H)2%%/$907$`Z)B5#.E8U4BM@2&`G+EPD$+R(I.P``'
Thread Previous
|
Thread Next