fix

2 files changed, 52 insertions, 19 deletions

diff --git a/challenge-153/james-smith/README.md b/challenge-153/james-smith/README.md
index 88a29d84c9..0d5719305e 100644
--- a/challenge-153/james-smith/README.md
+++ b/challenge-153/james-smith/README.md
@@ -62,7 +62,7 @@ to write out the first 21 (the largest number that can be represented as a an in
 Firstly we need to note that (in base 10) that the largest Factorion would have at most 7 digits. For a given number of digits (m) the largest value of the sum of the digits is
 `9! x m` or `362,880 x m`. For `m=7` we have the largest value being `2,540,160` which has 7-digits, for `m=8` we note that this value `2,903,040` also has 7 digits - so we can't have a solution with 8 or more digits.
 
-So when we loop through possibly values we know the limit is actually `2,177,282` greatly reducing our search space.
+So when we loop through possibly values we know the limit is actually `2,177,282` greatly reducing our search space (If the value has 7 digits, the first digit must be 1 or 2) then the highest value is `2 + 6 * 9!`.
 
 ## Solution
 
@@ -80,10 +80,39 @@ is_factorion($_) && say for 1..2_177_282;
 
 sub is_factorion {
   my $t = $_[0];
-  $t-=$f[$_] for split //,$_[0];
-  !$t;
+  ($t-=$f[$_])||return 1 for split //,$t;
+  return 0;
 }
-
 ```
 
 Running this gives the only 4 factorions: `1`, `2`, `145`, `40585`;
+
+This takes around 3 seconds to run on my test box. To speed this up we can work with groups of up to 4 digits - so we first create the sum arrays for 1, 2, 3 and 4 digits. Note the sum for `20` is different to the sum from `0020` - as `0! = 1`.
+
+The code then becomes:
+
+```perl
+my @f = (1);
+push @f, $_*$f[-1] foreach 1..9;
+my @z = map { my $t = $_; map {$t+$_} @f } 
+my @q = map { my $t = $_; map {$t+$_} @f } 
+my @t = map { my $t = $_; map {$t+$_} @f } @f;
+
+is_factorion_10k($_) && say for 1..2_177_282;
+
+sub is_factorion_10k {
+  my $t = $_[0];
+  return $t == (
+      $t >= 1e6 ? $z[ $t/1e3 ] + $q[ $t%1e3 ]
+    : $t >= 1e5 ? $q[ $t/1e3 ] + $q[ $t%1e3 ]
+    : $t >= 1e4 ? $t[ $t/1e3 ] + $q[ $t%1e3 ]
+    : $t >= 1e3 ?                $z[ $t     ]
+    : $t >= 100 ?                $q[ $t     ]
+    : $t >=  10 ?                $t[ $t     ]
+    :                            $f[ $t     ]
+  );
+}
+
+```
+
+This comes in at just less than 1 second - a `4x` speed up. Note the order of the ternaries is important - we start from highest to lowest as it minimizes the average number of comparisions performed.
diff --git a/challenge-153/james-smith/perl/ch-2.pl b/challenge-153/james-smith/perl/ch-2.pl
index b04809c552..c9d92f1b0f 100644
--- a/challenge-153/james-smith/perl/ch-2.pl
+++ b/challenge-153/james-smith/perl/ch-2.pl
@@ -11,20 +11,23 @@ use Data::Dumper qw(Dumper);
 ## Prep for tests!
 my @f = (1);
 push @f, $_*$f[-1] foreach 1..9;
+my @b = map { my $t = $_; map {$t+$_} @f }
+my @a = map { my $t = $_; map {$t+$_} @f }
+my @z = map { my $t = $_; map {$t+$_} @f }
+my @q = map { my $t = $_; map {$t+$_} @f }
 my @t = map { my $t = $_; map {$t+$_} @f } @f;
-my @q = map { my $t = $_; map {$t+$_} @f } @t;
 
 my @TESTS = ( [ 145, 1 ], [ 125, 0 ], );
 is( is_factorion(    $_->[0])||0, $_->[1] ) foreach @TESTS;
-is( is_factorion_1k( $_->[0])||0, $_->[1] ) foreach @TESTS;
+is( is_factorion_10k( $_->[0])||0, $_->[1] ) foreach @TESTS;
 done_testing();
 
 say join ', ', get_factorions();
-say join ', ', get_factorions_1k();
+say join ', ', get_factorions_10k();
 
 cmpthese( 100, {
-  '10' => sub { get_factorions()    },
-  '1k' => sub { get_factorions_1k() },
+  '10'   => sub { get_factorions()    },
+  '10k'  => sub { get_factorions_10k() },
 });
 
 ## Has to be at most 7 digits as 8x9! < 9_999_999
@@ -35,7 +38,7 @@ cmpthese( 100, {
 ## So we are guaranteed to find all values if we
 ## search as far as this value...
 
-## In the 1k method - we cheat and store the sum of 3 factorials for values
+## In the 10k method - we cheat and store the sum of 3 factorials for values
 ## from 0..999 {along with 2 digit version 0..99 and the previously used 0..9}
 ## We have to do this as the sum of "99" isn't the same as the sum "099".
 
@@ -54,26 +57,27 @@ sub is_factorion {
   return 0;
 }
 
-sub get_factorions_1k {
+sub get_factorions_10k {
   @f = (1);
   push @f, $_*$f[-1] foreach 1..9;
+  @z = map { my $t = $_; map {$t+$_} @f }
+  @q = map { my $t = $_; map {$t+$_} @f }
   @t = map { my $t = $_; map {$t+$_} @f } @f;
-  @q = map { my $t = $_; map {$t+$_} @f } @t;
   my @res;
-  is_factorion_1k($_) && push @res,$_ for 1 .. 2_177_282;
+  is_factorion_10k($_) && push @res,$_ for 1 .. 2_177_282;
   return @res;
 }
 
-sub is_factorion_1k {
+sub is_factorion_10k {
   my $t = $_[0];
   return $t == (
-      $t >= 1e6 ? $f[ $t/1e6 ] + $q[ ($t/1e3)%1e3 ] + $q[ $t%1e3 ]
+      $t >= 1e6 ? $z[ $t/1e3 ] + $q[ $t%1e3 ]
     : $t >= 1e5 ? $q[ $t/1e3 ] + $q[ $t%1e3 ]
     : $t >= 1e4 ? $t[ $t/1e3 ] + $q[ $t%1e3 ]
-    : $t >= 1e3 ? $f[ $t/1e3 ] + $q[ $t%1e3 ]
-    : $t >= 100 ? $q[ $t ]
-    : $t >=  10 ? $t[ $t ]
-    :             $f[ $t ]
+    : $t >= 1e3 ? $z[ $t     ]
+    : $t >= 100 ? $q[ $t     ]
+    : $t >=  10 ? $t[ $t     ]
+    :             $f[ $t     ]
   );
 }