http://qs1969.pair.com?node_id=24145

There's an interesting number pattern:
```1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
3 1 2 2 1 1
For those of you that don't know this pattern, each line is a description of the previous line. For instance, the line "1 1 1 2 2 1" describes the line "1 2 1 1", because it says "one 1, one 2, two 1's". And so on.

On PerlGuru.com, there was recently a quiz to come up with a good (fast? short?) way to create these lines in Perl. I came up with a very short solution, as well as a very fast solution. These are in the form:
```@a = (1);
for (1..10) {
print "@a\n";
# real juicy stuff here
}
I'd like to see possible solutions from people. My fastest code executed the 1..10 loop 500 times in 2.40 seconds, and a 1..35 loop 10 times in 43.51 seconds. My shortest one is a bit slower, because it uses a regex, at 3.76 seconds and 57.35 seconds.

Replies are listed 'Best First'.
RE: Generating a Pattern
by fundflow (Chaplain) on Jul 25, 2000 at 01:29 UTC
Here's my version:
```@a = (1);
for (1..10) {
print "@a\n";
@na=();
for (@a)
{ \$na[-1] == \$_ ? \$na[-2]++ : push @na, (1, \$_) }
@a=@na;
}
It does not move elements around (assuming push/pop are doing the natural thing) and has only one temporary copy.

Update: Use [-1] instead of [\$#na]. Cool, learned a new thing!
Update: use ?: instead of if/then
I first have to say that I really enjoyed this problem. It took me a little while to come up with a working algorithm, unfortunately it wasn't at elegant as yours. I thought I would play with your version to see if I could improve upon it a bit. The only thing I could do was add the use of references which reduces the memcopy time on larger lists. Below is a script that benchmarked the old 'non_ref' vs. the new 'ref'. Not necessarily staggering, but an improvement. I compacted the for loop for flipping it around and putting the for statement at the end of the conditional line.
```#!/usr/bin/perl
use Benchmark;
my \$count = 100;

my \$end = 30;
sub ref {
my \$a = [1];

for(1..\$end){
#    print "@\$a\n";

my @na;
(\$na[-1] == \$_ ? \$na[-2]++ : push @na, (1, \$_)) for @\$a;
\$a = \@na;
}
}

sub no_ref {
my @a = (1);

my @na;
for (1..\$end){
#    print "@a\n";

@na = ();
(\$na[-1] == \$_ ? \$na[-2]++ : push @na, (1, \$_)) for @a;

@a = @na;
}
}
timethese(\$count, { 'no_ref' => \&no_ref , 'ref' => \&ref} );
```Benchmark: timing 100 iterations of no_ref, ref...
no_ref: 11 wallclock secs (11.12 usr +  0.04 sys = 11.16 CPU)
ref:  9 wallclock secs ( 8.34 usr +  0.06 sys =  8.40 CPU)
```
RE: Generating a Pattern
by japhy (Canon) on Jul 25, 2000 at 07:39 UTC
Here's my code:
```# fastest
my @a = (1);
for (1..10) {
my \$s = @a;
while (\$s-- and my \$e = shift @a) {
push @a, 1, \$e;
\$a[-2]++, \$s--, shift @a while \$a[0] == \$e and \$s;
}
}

# shortest
my @a = (1);
for (1..10) {
my \$i;
@a = map \$i++ % 2 : length : \$_, join("", @a) =~ /((\d)\2*)/g;
}

\$_="goto+F.print+chop;\n=yhpaj";F1:eval
RE: Generating a Pattern
by hawson (Monk) on Jul 27, 2000 at 00:47 UTC
Here's mine:
```#!/usr/local/bin/perl

@a=split(//,"1");  #easier to make test strings this way. :)
for (1..10) {
print "@a\n";
@b=();
\$a=join("",@a);
while ( \$a =~ /((.)\2*/cg ) {
push (@b, (length \$1, \$2));
}
@a=@b
}
500 iterations of this took 1.15 seconds. 10 iterations running 1..35 took 18.73 seconds. For reference, I'm running this on an Ultrasparc-5.
That is more or less identical to my regex solution. Very nice, though.

\$_="goto+F.print+chop;\n=yhpaj";F1:eval
RE: Generating a Pattern
by bastard (Hermit) on Jul 29, 2000 at 02:01 UTC
1-10, 500 reps = 1 secs ( 1.09 usr 0.00 sys = 1.09 cpu)
1-35, 10 reps = 17 secs (17.67 usr 0.02 sys = 17.69 cpu)
```#!/usr/local/bin/perl

use Benchmark;

\$t0 = new Benchmark;
for (my \$x = 0; \$x < 500; \$x++) {
my \$numb = 1;
for (my \$x = 0; \$x < 10; \$x++) {
my @numb = split(//, \$numb);

my \$count = 1;
my \$newnumb = "";

for(my \$x = 1; \$x <= length(\$numb); \$x++) {
if (\$numb[\$x-1] ne \$numb[\$x]) {
\$newnumb .= "\$count\$numb[\$x-1]";
\$count = 1;
}
else { \$count++; }
}
\$numb = \$newnumb;
}
}

\$t1 = new Benchmark;

\$td = timediff(\$t1,\$t0);

print timestr(\$td), "\n";
RE: Generating a Pattern
by lhoward (Vicar) on Jul 25, 2000 at 03:28 UTC
My fastest did 500 iterations of 1..10 in 0.23 seconds and 10 iterations of 1..35 in 3.72 seconds.

Why don't you post your code so we can benchmark against it in a meaningful comparison. Raw time numbers (like I posted above) mean nothing cause I could have written really bad code, but benchmarked it on a Cray....

RE: Generating a Pattern
by jimt (Chaplain) on Aug 10, 2000 at 19:59 UTC
Just to chime in with my own version,
```1-10, 500x:  2 secs ( 1.13 usr  0.00 sys =  1.13 cpu) (printing)
1-10, 500x:  1 secs ( 0.48 usr  0.00 sys =  0.48 cpu) (not printing)
1-35m  10x: 26 secs (26.53 usr  0.00 sys = 26.53 cpu) (printing)
1-35,  10x: 15 secs (15.05 usr  0.00 sys = 15.05 cpu) (not printing)
My approach is similar to several of the ones already posted, but differs enough that I figured I might as well post it:
```\$x = 1;
for(1..10){
\$x =~ s/((.)\2*)/length(\$1).\$2/ge;
#print "@{[split//,\$x]}\n";
}
Uncomment that print line to print everything out. And, of course, get rid of the array-de-ref function call if you don't care about spaces between the numbers.

Incidentally, I used the array ref so I could take advantage of \$" being a space and not have to worry about mapping the numbers so they'd have spaces between them.
RE: Generating a Pattern
by turnstep (Parson) on Jul 25, 2000 at 05:04 UTC

Here's how I did it. Have no idea how this does on time.

```#!perl
\$total=10; ## Set to 1000 and watch your memory drain away! :)

@a=qw(1);
for (1..\$total) {
print "@a\n";
my @all;
\$count=1; \$x=0;
{
if (\$a[\$x] != \$a[\$x+1]) {
push(@all, \$count); push(@all, \$a[\$x]);
\$count=0;
}
last unless ++\$count and \$a[\$x++];
redo;
}
*a=\@all;
}
```times not implemented at foo.pl line ...