A while back I posted this to codereview.stackexchange.com but it did not
elicit the type of answers I was after. Not the right forum I guess. I have since revised the code and added some debugging to better demonstrate what it does.
After reading why is my project euler #4 program not working?, I was contemplating the most efficient way to approach this (finding the target palindrome as early as possible).
Is the logic in this snippet about as efficient as it gets? I am only considering the merits of the logic, not the choice of language. It would be easier (but not as efficient) to brute-force it with two nested loops.
Also, is this logic common enough for it to have a name?
I struggle to find a name for it, hence the debug code left in to show what it does.
#!/usr/bin/perl
#
use strict;
$^W = 1;
my $DEBUG = 1;
my ($n) = @ARGV;
$n = 3 if (! defined $n || $n < 2 || $n > 8);
my ($lo,$hi,$lm) = ( 10**($n-1), 10**$n-1, 10**($n+$n-2) );
my ($a,$b,$x) = ($hi,$hi);
my ($index,$save,$tmp) = (0);
for (;;) {
++$index; # show attempts before palindrome found
$x = $a*$b; # candidate to test
if ($x eq reverse $x) {
print "$x is $a * $b (candidate $index)\n"
if ($x > $lm); # remove 'noise' at the end of a run
last if (!$DEBUG || $n > 2); # show all palindromes when there are not that many
}
next if (!(--$a < $lo) & !(++$b > $hi)); # continue on this diagonal
++$a; --$b;
$tmp = "$a * $b"; # use to show progress
print " tested ".((defined $save && $save ne $tmp)?"$save thru ":"")."$tmp\n" if ($DEBUG);
$b += $a; $a = int --$b/2; $b -= $a; # new diagonal of candidates
last if ($a*$b < $lm); # we're done
$save = "$a * $b"; # save to show progress
}
print "\n";
Aucun commentaire:
Enregistrer un commentaire