diff options
| -rw-r--r-- | challenge-137/james-smith/perl/ch-2.pl | 66 |
1 files changed, 51 insertions, 15 deletions
diff --git a/challenge-137/james-smith/perl/ch-2.pl b/challenge-137/james-smith/perl/ch-2.pl index 8951d7c972..12637c00b5 100644 --- a/challenge-137/james-smith/perl/ch-2.pl +++ b/challenge-137/james-smith/perl/ch-2.pl @@ -9,7 +9,8 @@ use Benchmark qw(cmpthese timethis); use Data::Dumper qw(Dumper); my $MAX = 1e9; -my $MAX_LARGE = 40; +my $S_MAX = 1e6; +my $MULT = 100; my $COUNT = 500; my @TESTS = ( [ 56, 0 ], @@ -18,8 +19,11 @@ my @TESTS = ( [196, 1 ], ); -is( lychrel( $_->[0]), $_->[1] ) foreach @TESTS; -is( lychrel_large($_->[0]), $_->[1] ) foreach @TESTS; +my %seeds; +my %lychrel; + +is( lychrel( $_->[0]), $_->[1] ) for @TESTS; +is( lychrel_large($_->[0]), $_->[1] ) for @TESTS; done_testing(); @@ -30,25 +34,57 @@ sub lychrel { } sub lychrel_large { - my($n,$c) = (shift,$COUNT); - my @n = split //, $n; - while( $c-- && @n <= $MAX_LARGE ) { + my ( $c, @n ) = ( $COUNT, split //, $_[0] ); + while( $c-- ) { + return 0 if (join '', my @r = reverse @n ) eq (join '', @n); ## Check if palindromic + ## Add the arrays as if numbers - note this is compact - but does the job! + ( $n[$_] += $r[$_] ) > 9 && ($n[$_] -= 10, $_ ? ($n[$_-1]++) : (unshift @n, 1) ) for reverse 0 .. @n-1; + } + 1; +} + +sub lychrel_large_seed { + my ( $c, $n, @n ) = ( $COUNT, $_[0], split //, $_[0] ); + while( $c-- ) { my @r = reverse @n; - return 0 if (join '', @r) eq (join '', @n); - foreach ( reverse 0 .. @n-1 ) { - $n[$_] += $r[$_]; - next if $n[$_] < 10; - $n[$_]-=10; - $_ ? ($n[$_-1]++) : (unshift @n,1); - } + my $rn = join '', @r; + my $nn = join '', @n; + return exists $lychrel{$seeds{$rn}} if $r[0] && defined $seeds{$rn}; + return exists $lychrel{$seeds{$nn}} if defined $seeds{$nn}; + $seeds{ $rn } = $n if $rn < $S_MAX*$MULT && $r[0]; + $seeds{ $nn } = $n if $nn < $S_MAX*$MULT; + return 0 if $rn eq $nn; ## Check if palindromic + ## Add the arrays as if numbers - note this is compact - but does the job! + ( $n[$_] += $r[$_] ) > 9 && ($n[$_] -= 10, $_ ? ($n[$_-1]++) : (unshift @n, 1) ) for reverse 0 .. @n-1; } 1; } +use Time::HiRes qw(time); +my $time = time; print "Simple:"; -print " $_" foreach grep { lychrel $_ } 10..1000; +print " $_" for grep { lychrel $_ } 10..1000; +print "** time ", time - $time; + +foreach my $n (10..$S_MAX) { + if( defined $seeds{$n} ) { + $lychrel{$n}++ if exists $lychrel{$seeds{$n}}; + next; + } + $lychrel{$n}=1 if lychrel_large_seed($n); +} +print "\nSieve: "; +print join " ", sort { $a <=> $b } keys %lychrel; +print "** time ", time - $time; +print "\n\n"; + +$time = time; print "\nLarge: "; -print " $_" foreach grep { lychrel_large $_ } 10..1000; +print " $_" for grep { lychrel_large $_ } 10..$S_MAX; +print "** time ", time - $time; print "\n\n"; +$time = time; + + |