develooper Front page | | Postings from July 2002

Re: My solution annotated

Thread Previous | Thread Next
July 8, 2002 09:11
Re: My solution annotated
Message ID:
In article <Pine.LNX.3.96.1020708101325.1117C-100000@gentoo>,
	Stephen Turner <> writes:
> So, last month I annotated all the top 12 solutions. People seemed to
> appreciate it, but there's no way I've got time to do it again this month!
> So I thought it would be interesting if players annotated their own
> solutions this month. I for one would like to see what people say about
> their own solutions.
mm, my first attempt seems to have gotten lost. Retry.

my solution:

-ln0 / \Q$&/||print$1while s/(\n|(?= ?\G))\Q$&/ \n/g,/(\S+) /g/$#+

-n0 slurps the whole string.

The first time the while is entered, $& is empty, and
s/(\n|(?= ?\G))\Q$&/ \n/g
will add a space newline in front (the (?= ?\G) triggers), and add a
space at the end of every line (the \n triggers).  So a typical line
"a b" can now be read as "\n a b ", and "c c" can be seen as "c c \n"

The /(\S+) /g is the core of the solution. this will repeatedly try
each successive word in the string, but if any changes are done during
the loop, it will restart. So it functions as a "try for every word as
long as we are making progress". It sets up $1 as the word, and $& as
the word followed by a space.

/ \Q$&/||print$1

Checks if the word is both preceded and followed by a space. In that
case it appears as follower (or singleton), we don't print and $& is
changed to " word ". If it's not a follower, we print the word $1
(the -l adds the newline), and $& is unchanged.

We now get to s/(\n|(?= ?\G))\Q$&/ \n/g again. \G will be at the place
/(\S+ )  / stopped matching, even in the case that / \Q$&/ matched
(the change of pos is localized, but the change of $& isn't). So there
are two cases:
- / \Q$&/ did not match, $& is "word ", and \G is just at the end of
  the "word " under consideration. The \G cannot match because that
  would imply the line under consideration is "word word ", which would
  have caused / \Q$&/ to match. So the substitute is essentially
  s/\nword / \n/. This removes all cases of "word" at the beginning
  (and adds an extra space to the previous line). So "\ne f \nword b \n"
  becomes "\ne f  \nb \n". A line like "\nb \n" is a placeholder for
  later output when all cases with b as follower have been eliminated:
  it will match the /(\S+) /, not match the / \Q$&/ and get safely
  eliminated by the s/\nword / \n/ to become " \n\n"
- / \Q$&/ did match, now $& is " word " and \G is just at the end of the
  "word " under consideration. Since we never have "\n word " in the
  input, the \n branch can never match, therefore we effectively are
  doing s/(?= \G) word / \n/.  This will change *one* singleton
  "word word ...." to "word \n...." (where the ... is any number of
  spaces followed by a newline) or do nothing. So singletons slowly
  get removed from the input and replaced by placeholders.

As long as the /(\S+) / matches, $#+ will be 1. The whole process runs
until no more words make any progress. At that point, the last thing
that ever matched will be either the s/(\n|(?= ?\G))\Q$&/ \n/g if the
last thing we did was removing the last word ($#+ will be 1) or the
/ \Q$&/ if there are still words but we can make no progress (which
means loops and $#+ will be 0). So $#+ is only ever zero at the end of
processing and if the input contained loops. And in that case the
division by $#+ causes an error.

My 65 solution before this was less twisted, but mtve was quickly
catching up in a way that made me certain he was just a cat's whisker
away from finding the s/// unification in that solution (he was, but
he used an inferior unification). So I did an extra effort on saturday
to get at least one non-obvious weirdness ahead of the storming mtve.

There might be a solution which mangles the original input in a more
clever way so the lookahead won't be needed. I found some tempting 60's
and 61's that pass several tests, but couldn't make it all come
together. If anybody would have gotten to 65, I'd have started exploring
that branch systematically.
old (pre-golf) conversation on ircnet #perl:
<Addi> Just imagine we are meeting the aliens for the first time.
<ton>  Most people would just shoot them
       to see how many points they are worth.

Thread Previous | Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About