Front page | perl.golf | Postings from July 2002

## RE: My solution annotated

Thread Previous | Thread Next
From:
Ala Qumsieh
Date:
July 8, 2002 07:57
Subject:
RE: My solution annotated
Message ID:
8812A03F65CDD511AE98006008F5E8712828AE@hermes.hyperchip.com
```
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

nntp.perl.org: Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at ask@perl.org | Group listing | About