Merge pull request #5714 from dcw803/master

imported my solutions to this week's tasks; factorials everywhere:-)

3 files changed, 156 insertions, 42 deletions

diff --git a/challenge-153/duncan-c-white/README b/challenge-153/duncan-c-white/README
index 2bc85c8535..918a4a5540 100644
--- a/challenge-153/duncan-c-white/README
+++ b/challenge-153/duncan-c-white/README
@@ -1,61 +1,45 @@
-TASK #1 - Triangle Sum Path
+TASK #1 - Left Factorials
 
-You are given a triangle array.
+Write a script to compute Left Factorials of 1 to 10. Please refer OEIS
+A003422 for more information.
 
-Write a script to find the minimum sum path from top to bottom.
+(My summary: left factorial N = sum k! for k in (0..N-1), remembering that
+ 0! = 1! = 1.  So lf(N+1) = lf(N) + N!)
 
-Example 1:
-
-	Input: $triangle = [ [1], [5,3], [2,3,4], [7,1,0,2], [6,4,5,2,8] ]
-
-			1
-		       5 3
-		      2 3 4
-		     7 1 0 2
-		    6 4 5 2 8
-
-	Output: 8
-
-	    Minimum Sum Path = 1 + 3 + 2 + 0 + 2 => 8
-
-Example 2:
-
-	Input: $triangle = [ [5], [2,3], [4,1,5], [0,1,2,3], [7,2,4,1,9] ]
-
-			5
-		       2 3
-		      4 1 5
-		     0 1 2 3
-		    7 2 4 1 9
+Expected Output:
 
-	Output: 9
+1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114
 
-	    Minimum Sum Path = 5 + 2 + 1 + 0 + 1 => 9
+MY NOTES: easy, 1 pass, calc N! on the fly (by multiplying (N-1)! by N)
+and add (N-1)! to lf(N-1) to give lf(N).
 
-MY NOTES: So it appears at each row, we simply pick the minimum value.
-It doesn't have to be adjacent, or even close to, the one we picked
-on the row above.  Ok, so that's easy!  Actually, parsing the input
-may be the hardest part.
 
+TASK #2 - Factorions
 
-TASK #2 - Rectangle Area
+You are given an integer, $n.
 
-You are given coordinates bottom-left and top-right corner of two rectangles in a 2D plane.
+Write a script to figure out if the given integer is factorion.
 
-Write a script to find the total area covered by the two rectangles.
+A factorion is a natural number that equals the sum of the factorials of its digits.
 
 Example 1:
 
-	Input: Rectangle 1 => (-1,0), (2,2)
-	       Rectangle 2 => (0,-1), (4,4)
+  Input: $n = 145
+  Output: 1
 
-	Output: 22
+    Since 1! + 4! + 5! => 1 + 24 + 120 = 145
 
 Example 2:
 
-	Input: Rectangle 1 => (-3,-1), (1,3)
-	       Rectangle 2 => (-1,-3), (2,2)
+  Input: $n = 123
+  Output: 0
 
-	Output: 25
+    Since 1! + 2! + 3! => 1 + 2 + 6 <> 123
 
-MY NOTES: Of course the tricky bit here is when the rectangles overlap.
+MY NOTES: cool, precompute 0..9! in a 10 element array, split number into
+digits, sum their factorials and check if the result if the number you
+first thought of.  Let's add a tabulating mode (invoked if --tab given) that
+shows, which numbers (1..$n) are factorian.  Running this as:
+	./ch-2.pl -t 1000000
+reveals that the only base 10 factorians under 1000000 are:
+        1, 2, 145, 40585
diff --git a/challenge-153/duncan-c-white/perl/ch-1.pl b/challenge-153/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..5fd706125d
--- /dev/null
+++ b/challenge-153/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,41 @@
+#!/usr/bin/perl
+# 
+# TASK #1 - Left Factorials
+# 
+# Write a script to compute Left Factorials of 1 to 10. Please refer OEIS
+# A003422 for more information.
+# 
+# (My summary: left factorial N = sum k! for k in (0..N-1), remembering that
+#  0! = 1! = 1.  So lf(N+1) = lf(N) + N!)
+# 
+# Expected Output:
+# 
+# 1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114
+# 
+# MY NOTES: easy, 1 pass, calc N! on the fly (by multiplying (N-1)! by N)
+#           and add (N-1)! to lf(N-1) to give lf(N).
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use List::Util qw(min);
+#use Data::Dumper;
+
+my $debug=0;
+die "Usage: left-factorials [--debug] [firstN - default 10]\n"
+	unless GetOptions( "debug"=>\$debug ) && @ARGV<2;
+my $n = shift // 10;
+
+my $fact = 1;
+my $lf = 1;
+my @lf;
+foreach my $i (1..$n)
+{
+	push @lf, $lf;
+	$fact *= $i;
+	$lf += $fact;
+}
+
+say join( ', ', @lf );
diff --git a/challenge-153/duncan-c-white/perl/ch-2.pl b/challenge-153/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..8e78697c54
--- /dev/null
+++ b/challenge-153/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,89 @@
+#!/usr/bin/perl
+# 
+# TASK #2 - Factorions
+# 
+# You are given an integer, $n.
+# 
+# Write a script to figure out if the given integer is factorion.
+# 
+# A factorion is a natural number that equals the sum of the factorials of its digits.
+# 
+# Example 1:
+# 
+#   Input: $n = 145
+#   Output: 1
+# 
+#     Since 1! + 4! + 5! => 1 + 24 + 120 = 145
+# 
+# Example 2:
+# 
+#   Input: $n = 123
+#   Output: 0
+# 
+#     Since 1! + 2! + 3! => 1 + 2 + 6 <> 123
+# 
+# MY NOTES: cool, precompute 0..9! in a 10 element array, split number into
+# decimal digits, sum their factorials and check if the result if the number you
+# first thought of.  Let's add a tabulating mode (invoked if --tab given) that
+# shows, which numbers (1..$n) are factorian.  Running this as:
+#	./ch-2.pl -t 1000000
+# reveals that the only base 10 factorians under 1000000 are:
+#       1, 2, 145, 40585
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use Function::Parameters;
+use List::Util qw(sum);
+#use Data::Dumper;
+
+my $debug=0;
+my $tabulate=0;
+
+
+# calculate 0..9! in @df.
+my $fact = 1;
+my @df;
+map { push @df, $fact; $fact *= $_ } 1..10;
+#say join( ', ', @df );
+#die;
+
+
+#
+# my $sum = sumfactdigits( $x );
+#	Add up the factorials of the individual decimal digits of $x;
+#	return the sum.
+#
+fun sumfactdigits( $x )
+{
+	my @d = split( //, $x );
+	return sum( map { $df[$_] } @d );
+}
+
+#
+# my $isfactorian = isfactorian( $x );
+#	Return 1 iff $x is factorian (i.e. sumfactdigits($x)==$x);
+#	return 0 otherwise.
+#
+fun isfactorian( $x )
+{
+	my $sum = sumfactdigits( $x );
+	return $sum == $x ? 1 : 0;
+}
+
+
+die "Usage: is-factorian [--debug] [--tabulate] N\n" unless
+	GetOptions( "debug" => \$debug, "tabulate" => \$tabulate ) && @ARGV==1;
+my $n = shift;
+
+
+if( $tabulate )
+{
+	my @isf = grep { isfactorian($_) } 1..$n;
+	say join( ', ', @isf );
+} else
+{
+	say isfactorian($n);
+}