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)
| 