diff options
Diffstat (limited to 'challenge-153')
| -rw-r--r-- | challenge-153/duncan-c-white/README | 68 | ||||
| -rwxr-xr-x | challenge-153/duncan-c-white/perl/ch-1.pl | 41 | ||||
| -rwxr-xr-x | challenge-153/duncan-c-white/perl/ch-2.pl | 89 |
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); +} |