Along the same lines, here's my solution:
-ln0 s/^(.*) \1$/$1/mg;/ \Q$& /||print($&),s/^\Q$&\E\s//mgwhile/\S+/g;$_&&& The basic algorithm is this (shamelessly borrowed from http://www.math.grin.edu/~rebelsky/Courses/152/97F/Outlines/outline.49.html) : while not done if the graph is empty, then we're done (exit the loop) pick a node with no predecessors if no such node exists , then the graph is cyclic (exit the loop) output that node (number that node) delete that node from the graph end while Initially, I started with using hashes to create my graph. Deep down I knew that this wouldn't get me anywhere near Ton, who was way below 100 already. I just wanted to get a feel of the problem and its complexities before I started real golfing. Doing that convinced me that I had to play with strings and use Perl's regexps to shave off the valuable characters needed to access hashes, but I didn't know where to start. Thanks to a series of highly unlikely events, I managed to come up with a slight variation of my final solution. Here's the explanation: -ln0 ## We all know what that does. s/^(.*) \1$/$1/mg; ## This basically collapses any duplicates (the second ## word is deleted if it's the same as the first). / \Q$& /||print($&),s/^\Q$&\E\s//mgwhile/\S+/g; ## This can be re-written as: ## while (/\S+/g) { ## if (!/ \Q$&\E\n/) { ## print $&; ## s/^\Q$&\E\s//mg; ## } ## } ## ## This iterates through all words in the list. If it can't ## match a space followed by the word followed by \n, ## this means that the word has no predecessors. Print it, ## then delete all occurrences of it from the list. $_&&& ## This little monster is well-known to the more ## experienced golfers. I believe it was proposed ## by (-ugene. It basically calls the undefined ## subroutine &; if $_ containes anything. This ## basically throws an error and the program exits ## with a non-zero exit value. The ; is part of ## the -n switch. Check perlrun for details. Now, ## if we have no cycles, then all the words would ## have been printed and deleted in the while() ## loop, leaving $_ empty. In case of problems, ## $_ will retain something, and thus we should die. Excellent hole. Many thanks to the referees. --/-\la
