On Sat, Jan 17, 2004 at 03:13:20PM -0600, Riey Bryant wrote:
> for$=(@F){@;=grep{$*=$_;grep$*eq$_,@;?@;:@[EMAIL PROTECTED],[EMAIL PROTECTED]@I
[...]
> -lp0a
> for$=(@F){@;=map{$*=$_;grep$*eq$_,@;?@;:@[EMAIL PROTECTED],[EMAIL PROTECTED]@
[...]
> Why does this substitution (grep to map) make such a huge difference in
> running time? Both statements should return the same array, right?
Not as far as I can see, though I didn't look too hard. The latter
program is returning a copy of @; or @* for each iteration of the
outer map{}. Here's a simpler example:
% perl -le '@a=(1,2,3); print grep { @a } @a; print map { @a } @a'
123
123123123
> Maybe it actually passes, but I didn't have the patience to wait for it... I
> noticed Juho mentioned something similar about test 81.
In my case, it was just a matter of there being excessive backtracking
in a regexp.
Here's a brief explanation of my solution, since this is a decent
example of the traditional golfing technique of transforming the
problem into a suitable string, and then letting the regexp engine do
the work.
#!perl -lp0a
s/.+/ @{[map"$&$_ $_$&",@F]} /g;($_)=/(\d+)(.*
.* \1 )*.*$/
The substitution transforms the input into a form where each line
contains the original content of the line concatenated with the
contents of all lines. We do two concatenations for each line, one with
the original content at the start and one with the original content at
the end. The results are separated by spaces. For example, with the
input:
0
01
1
00
The result after the substitution:
00 00 001 010 01 10 000 000
010 001 0101 0101 011 101 0100 0001
[...]
Now, to fulfill the problem statement we just need to a substring
matching /\b\d+\b/, that's found from all lines. This is simple enough
using a regexp like /^.*\b(\d+)\b.*\n(.*\b\1\b.*\n)*$/. Then it's just
a matter of optimizing the regexp for size and speed.
--
Juho Snellman
