in reply to CarTalk Puzzler

As a demonstration of how finding the pattern (perfect squares) is so much better than brute force, a benchmark: 

use strict;
use warnings;
$|=1;

sub sol1 {
    #init;
    my $lights = 20_000;
    my @lit = map {1} (1..$lights);
    
    my @sol;
    
    #flip;
    for (2..$lights) { 
        my $cnt = $_-1;
        while ($cnt < $lights) { 
            $lit[$cnt] = !$lit[$cnt];
            $cnt+=$_;
        }
    }
    
    #answer;
    for (0..$#lit) { push @sol, $_+1 if $lit[$_] }
}

sub sol2 {
    my $lights = 20_000;
    
    my @sol;
    
    for (1..$lights) {
        my $sqr = sqrt($_);
        push @sol, $_ if int($sqr) == $sqr;
    }
}

use Benchmark ':all';
cmpthese( 100, {
    sol1 => \&sol1,
    sol2 => \&sol2,
});

__END__
       Rate  sol1  sol2
sol1 6.58/s    --  -93%
sol2 98.5/s 1398%    --

[download]

These two solutions are abstracted to work for any number of lights, and the first is meant to be something someone of average coding skill might come up with (i.e. my crack at the solution ;-) ). Notice how sol2, where we just find all the perfect squares in range, is tremendously faster.

Just goes to show that the best optimization is done by redefining the problem. In this case, redefining from "toggle every nth light for n=2..max" to "find all lights that are perfect squares" resulted in a performance gain of nearly 1700%1400%!

Updates:

<-radiant.matrix->
A collection of thoughts and links from the minds of geeks
The Code that can be seen is not the true Code
"In any sufficiently large group of people, most are idiots" - Kaa's Law

Replies are listed 'Best First'.
Re^2: CarTalk Puzzler
by Perl Mouse (Chaplain) on Nov 17, 2005 at 17:21 UTC
    That's not a very good benchmark, as you will be pushing the answer onto the same array over and over again. After running your benchmark, @main::sol contains 28200 elements.

    I don't understand why you are using our all over your program. What's wrong with my?

    But you missed a much faster solution: just taking the squares of the numbers from 1 to the square root of 20_000.

    Here's a revised benchmark: 

    use strict;
use warnings;

my (@sol1, @sol2, @sol3);
my $lights = 20_000;

sub sol1 {
        #init;
        my @lit = (1) x ($lights+1);
        
        #flip;
        for (2..($lights+1)) {
                my $cnt = $_;
                while ($cnt <= $lights) {
                        $lit[$cnt] = !$lit[$cnt];
                        $cnt+=$_;
                }
        }
 
        #answer;
        @sol1 = grep {$lit[$_]} 1 .. ($lights+1);
}
 
sub sol2 {
        @sol2 = ();
        for (1..$lights) {
                my $sqr = sqrt($_);
                push @sol2, $_ if int($sqr) == $sqr;
        }
}
 
sub sol3 {
        @sol3 = map {$_**2} 1 .. sqrt($lights);
}


use Benchmark ':all';
cmpthese( -10, {
        sol1 => \&sol1,
        sol2 => \&sol2,
        sol3 => \&sol3,
});     

__END__
       Rate   sol1   sol2   sol3
sol1 3.92/s     --   -90%  -100%
sol2 41.0/s   945%     --   -99%
sol3 3762/s 95923%  9085%     --

    [download]
    Perl --((8:>*
[reply]
[d/l]

      Yeah, I don't know why I used our. Not enough coffee today, I guess -- it's not even a general habit of mine. Odd. Thanks, though.

      Thanks also for your even-faster solution, which reinforces my core point: understanding the problem well enough to rephrase it leads to much faster results!

      <-radiant.matrix->
      A collection of thoughts and links from the minds of geeks
      The Code that can be seen is not the true Code
      "In any sufficiently large group of people, most are idiots" - Kaa's Law
[reply]
[d/l]

In Section Meditations