Merge pull request #4970 from drbaggy/master

additional optimizations - esp with memory

1 files changed, 31 insertions, 22 deletions

diff --git a/challenge-133/james-smith/perl/ch-2.pl b/challenge-133/james-smith/perl/ch-2.pl
index 6163b97940..1f07513985 100644
--- a/challenge-133/james-smith/perl/ch-2.pl
+++ b/challenge-133/james-smith/perl/ch-2.pl
@@ -5,41 +5,50 @@ use strict;
 use warnings;
 use feature qw(say);
 
-my(@primes,%ds,%comp) = (2,3);
+my(%comp,@primes); ## Caches of digit sums of factors of $N
+
 say $_ foreach smith_numbers(@ARGV?$ARGV[0]:100);
-#say $_ foreach smith_numbers_readable(@ARGV?$ARGV[0]:100);
 
-sub sum {        my $t = 0; $t+=$_ foreach @_; $t; }
-sub sum_digits { return $ds{$_[0]} ||= sum split //, $_[0]; }
+sub sum_digits { my $t = 0; $t+=$_ foreach split //, $_[0]; $t } ## Digit sum of number...
 
-sub prime_factors {
+sub sum_prime_factors {
+  ## We don't need to remember factors - just the digit sum...
   my $N = shift;
 
-  ## If we are composite then store the factors for the composite and return...
-  ( $N % $_) or ( return @{ $comp{$N} = [ $_, @{$comp{ $N / $_ }||[$N/$_]}] } ) foreach @primes;
+  ## If we are composite then store the sum of the digit factors for the composite and return...
+  ( $N % $_) || ( return $comp{$N} = $comp{$N/$_} + $comp{$_} ) foreach @primes;
 
   ## Otherwise we are prime so add to primes and return nothing....
+  $comp{$N} = sum_digits $N;
   push @primes, $N;
-  return;
+  return 0; ## Although we now the sum digits we return 0 as prime!
 }
 
-sub smith_numbers_readable {
-  my ( $C, $n, @sn ) = (shift,3);
-  while($n++) { ## $n starts at 4 ... lowest possible smith number is 4 ( composite or 2 x 2 )
-    next unless my @q = prime_factors($n); ## Must be composite as prime_factors returns list...
-    next if sum_digits($n) - sum map { sum_digits $_ } @q; ## Digit sums are equal...
-    push @sn, $n;
-    return @sn if @sn==$C;
-  }
+sub smith_numbers { ## This is the short form! using &&
+  my ( $C, $n, @sn ) = (shift,1);
+  ( sum_digits( $n ) == sum_prime_factors $n ) &&     ## Diff between sums of factors == 0
+  ( push @sn, $n                             ) &&     ## push
+  ( @sn == $C                                ) &&     ## check length & return...
+  ( return @sn                               ) while $n++;
 }
 
+## Same functions without comments....
 
-sub smith_numbers { ## This is the short form! using &&
-  my ( $C, $n, @sn ) = (shift,3);
-  ( sum_digits( $n ) - sum map { sum_digits $_ } prime_factors( $n ) ) ||
-  ( push @sn, $n                                                     ) &&
-  ( @sn == $C                                                        ) &&
-  ( return @sn                                                       ) while $n++;
+sub cl_sum_digits { my $t = 0; $t+=$_ foreach split //, $_[0]; $t }
+
+sub cl_sum_prime_factors {
+  my $N = shift;
+  ( $N % $_) || ( return $comp{$N} = $comp{$N/$_} + $comp{$_} ) foreach @primes;
+  $comp{$N} = cl_sum_digits $N;
+  push @primes, $N;
+  return 0;
+}
+sub cl_smith_numbers {
+  my ( $C, $n, @sn ) = (shift,1);
+  ( cl_sum_digits( $n ) == cl_sum_prime_factors $n ) &&
+  ( push @sn, $n                                   ) &&
+  ( @sn == $C                                      ) &&
+  ( return @sn                                     ) while $n++;
 }