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``'
