imported my solutions to this week's challenges; two nice tasks

3 files changed, 246 insertions, 27 deletions

diff --git a/challenge-136/duncan-c-white/README b/challenge-136/duncan-c-white/README
index 9e73de07f7..c41627048b 100644
--- a/challenge-136/duncan-c-white/README
+++ b/challenge-136/duncan-c-white/README
@@ -1,56 +1,77 @@
-TASK #1 - Middle 3-digits
+TASK #1 - Two Friendly
 
-You are given an integer.
+You are given 2 positive numbers, $m and $n.
 
-Write a script find out the middle 3-digits of the given integer, if
-possible otherwise throw sensible error.
+Write a script to find out if the given two numbers are Two Friendly.
+
+Two positive numbers, m and n are two friendly when gcd(m, n) = 2 ^
+p where p > 0. The greatest common divisor (gcd) of a set of numbers
+is the largest positive number that divides all the numbers in the set
+without remainder.
 
 Example 1
 
-  Input: $n = 1234567
-  Output: 345
+    Input: $m = 8, $n = 24
+    Output: 1
+
+    Reason: gcd(8,24) = 8 => 2 ^ 3
 
 Example 2
 
-  Input: $n = -123
-  Output: 123
+    Input: $m = 26, $n = 39
+    Output: 0
 
-Example 3
+    Reason: gcd(26,39) = 13
 
-  Input: $n = 1
-  Output: too short
+Example 3
 
-Example 4
+    Input: $m = 4, $n = 10
+    Output: 1
 
-  Input: $n = 10
-  Output: even number of digits
+    Reason: gcd(4,10) = 2 => 2 ^ 1
 
-MY NOTES: Pretty easy, although it's not clear how to always treat negative numbers.
-Assume abs() them.
+MY NOTES: Pretty easy.  Euclid's GCD algorithm, then check if the result is a power of 2.
 
 
-TASK #2 - Validate SEDOL
+TASK #2 - Fibonacci Sequence
 
-You are given 7-characters alphanumeric SEDOL.
+You are given a positive number $n.
 
-Write a script to validate the given SEDOL. Print 1 if it is a valid SEDOL otherwise 0.
+Write a script to find how many different sequences you can create using
+Fibonacci numbers where the sum of unique numbers in each sequence are
+the same as the given number.
 
-For more information about SEDOL, please checkout https://en.wikipedia.org/wiki/SEDOL
+    Fibonacci Numbers: 1,2,3,5,8,13,21,34,55,89,..
 
 Example 1
 
-  Input: $SEDOL = '2936921'
-  Output: 1
+  Input:  $n = 16
+  Output: 4
+
+  Reason: There are 4 possible sequences that can be created using Fibonacci numbers
+  i.e. (3 + 13), (1 + 2 + 13), (3 + 5 + 8) and (1 + 2 + 5 + 8).
 
 Example 2
 
-  Input: $SEDOL = '1234567'
-  Output: 0
+  Input:  $n = 9
+  Output: 2
+
+  Reason: There are 2 possible sequences that can be created using Fibonacci numbers
+  i.e. (1 + 3 + 5) and (1 + 8).
 
 Example 3
 
-  Input: $SEDOL = 'B0YBKL9'
-  Output: 1
+  Input:  $n = 15
+  Output: 2
+
+  Reason: There are 2 possible sequences that can be created using Fibonacci numbers
+  i.e. (2 + 5 + 8) and (2 + 13).
 
-MY NOTES: Pretty easy
+MY NOTES: Pretty easy - find subsets of the first few Fibonacci numbers that sum to N.
+How many Fibonacci numbers should we consider?  Those <= N.  Then, how do we sum subsets
+of them?  Two obvious ways:
 
+1. recursive function, iterating over the Fibonacci values: each value is either in the
+   subset or not, try both possibilities.
+2. binary-counting method, iterate over every combination C from 1 .. 2**(number values)-1,
+   then sum up only the elements where the corresponding bit in C is true.
diff --git a/challenge-136/duncan-c-white/perl/ch-1.pl b/challenge-136/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..08e3486f2a
--- /dev/null
+++ b/challenge-136/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,74 @@
+#!/usr/bin/perl
+# 
+# TASK #1 - Two Friendly
+# 
+# You are given 2 positive numbers, $m and $n.
+# 
+# Write a script to find out if the given two numbers are Two Friendly.
+# 
+# Two positive numbers, m and n are two friendly when gcd(m, n) = 2 ^
+# p where p > 0. The greatest common divisor (gcd) of a set of numbers
+# is the largest positive number that divides all the numbers in the set
+# without remainder.
+# 
+# Example 1
+# 
+#     Input: $m = 8, $n = 24
+#     Output: 1
+# 
+#     Reason: gcd(8,24) = 8 => 2 ^ 3
+# 
+# Example 2
+# 
+#     Input: $m = 26, $n = 39
+#     Output: 0
+# 
+#     Reason: gcd(26,39) = 13
+# 
+# Example 3
+# 
+#     Input: $m = 4, $n = 10
+#     Output: 1
+# 
+#     Reason: gcd(4,10) = 2 => 2 ^ 1
+# 
+# MY NOTES: Pretty easy.  Euclid's GCD algorithm, then check if the result is a power of 2.
+#
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use Function::Parameters;
+#use Data::Dumper;
+
+
+#
+# my $gcd = gcd( $a, $b );
+#       Compute and return the GCD (Greatest Common Denominator) of $a and $b.
+#
+fun gcd( $a, $b )
+{
+        while( $b != 0 )
+        {
+                ( $a, $b ) = ( $b, $a % $b );
+        }
+        return $a;
+}
+
+
+my $debug=0;
+die "Usage: 2-friendly N M\n" unless
+	GetOptions( "debug"=>\$debug ) && @ARGV==2;
+my( $n, $m ) = @ARGV;
+
+my $gcd = gcd( $n, $m );
+say "gcd is $gcd" if $debug;
+
+my $ispower = 0;
+for( my $twop = 2; $twop <= $gcd; $twop *= 2 )
+{
+	$ispower++ if $twop == $gcd;
+}
+
+say $ispower;
diff --git a/challenge-136/duncan-c-white/perl/ch-2.pl b/challenge-136/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..d3a4cd88e7
--- /dev/null
+++ b/challenge-136/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,124 @@
+#!/usr/bin/perl
+# 
+# TASK #2 - Fibonacci Sequence
+# 
+# You are given a positive number $n.
+# 
+# Write a script to find how many different sequences you can create using
+# Fibonacci numbers where the sum of unique numbers in each sequence are
+# the same as the given number.
+# 
+#     Fibonacci Numbers: 1,2,3,5,8,13,21,34,55,89,..
+# 
+# Example 1
+# 
+#   Input:  $n = 16
+#   Output: 4
+# 
+#   Reason: There are 4 possible sequences that can be created using Fibonacci numbers
+#   i.e. (3 + 13), (1 + 2 + 13), (3 + 5 + 8) and (1 + 2 + 5 + 8).
+# 
+# Example 2
+# 
+#   Input:  $n = 9
+#   Output: 2
+# 
+#   Reason: There are 2 possible sequences that can be created using Fibonacci numbers
+#   i.e. (1 + 3 + 5) and (1 + 8).
+# 
+# Example 3
+# 
+#   Input:  $n = 15
+#   Output: 2
+# 
+#   Reason: There are 2 possible sequences that can be created using Fibonacci numbers
+#   i.e. (2 + 5 + 8) and (2 + 13).
+# 
+# MY NOTES: Pretty easy - find subsets of the first few Fibonacci numbers that sum to N.
+# How many Fibonacci numbers should we consider?  Those <= N.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+use Getopt::Long;
+use Data::Dumper;
+
+my $debug = 0;
+
+die "Usage: count-fib [-d|--debug] N\n"
+	unless GetOptions( "debug"=>\$debug ) && @ARGV==1;
+my $n = shift @ARGV;
+
+#
+# my @fib = fibs_upto( $n );
+#	Find Fibonacci numbers up to $n.
+#
+fun fibs_upto( $n )
+{
+	my @result;
+	my( $a, $b ) = ( 1, 1 );
+	while( $a <= $n )
+	{
+		push @result, $a;
+		( $a, $b ) = ( $b, $a+$b );
+	}
+	return @result;
+}
+
+
+#
+# my @subsets = count_val_sum( $n, @val );
+#	Find all distinct subsets of @val total to $n, and
+#	and return an array of all such subsets.  Do it by
+#	iterating over all D-bit binary numbers from 1..2**D-1
+#	(where D is the length(@val), subset-summing each combination
+#
+fun count_val_sum( $n, @val )
+{
+	my $digits = 2**@val;
+	my @result;
+	for( my $comb=1; $comb<$digits; $comb++ )
+	{
+		my( $sum, @selected ) = subset_sum( $comb, @val );
+		next unless $sum == $n;
+		push @result, \@selected;
+	}
+	return @result;
+}
+
+
+#
+# my( $sum, @selected ) = subset_sum( $comb, @val );
+#	Consider $comb in binary, with as many bits as @val has
+#	elements.  Sum up just the values in @vol whose corresponding
+#	bit in $comb is 1, and return the sum and the selected values.
+#
+fun subset_sum( $comb, @val )
+{
+	my $sum = 0;
+	my @selected;
+	foreach my $val (@val)
+	{
+		if( $comb%2 == 1 )
+		{
+			$sum += $val;
+			push @selected, $val;
+		}
+		$comb = int($comb/2);
+	}
+	return ( $sum, @selected );
+}
+
+
+my @fib = fibs_upto( $n );
+shift @fib;			# remove duplicate 1
+#say Dumper(\@fib);
+
+my @subsets = count_val_sum( $n, @fib );
+my $count = @subsets;
+
+say "Output: $count";
+say "\nReason: the following $count subsets sum to $n";
+say join(',',@$_) for @subsets;