Front page | perl.golf |
Postings from July 2002
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
Thread Previous
|
Thread Next