develooper 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