Merge pull request #1406 from dcw803/master

committed my Perl solutions to challenge 51

3 files changed, 126 insertions, 39 deletions

diff --git a/challenge-051/duncan-c-white/README b/challenge-051/duncan-c-white/README
index 3d714d2e48..1c6e36e8ae 100644
--- a/challenge-051/duncan-c-white/README
+++ b/challenge-051/duncan-c-white/README
@@ -1,52 +1,30 @@
-Task 1: "Merge Intervals
+Task 1: "3 Sum
 
-Write a script to merge the given intervals whereever possible.
+Given an array @L of integers, and a target T. Write a script to find
+all unique triplets such that a + b + c is same as the target T. Also
+make sure a <= b <= c.
 
-    [2,7], [3,9], [10,12], [15,19], [18,22]
+Example:
 
-The script should merge [2, 7] and [3, 9] together to return [2, 9].
+    @L = (-25, -10, -7, -3, 2, 4, 8, 10);
 
-Similarly it should also merge [15, 19] and [18, 22] together to return [15, 22].
-
-The final result should be something like below:
-
-[2, 9], [10, 12], [15, 22]
+One such triplet for target 0 i.e. -10 + 2 + 8 = 0.
 "
 
-My notes: Fine, but why wouldn't we also merge [2,9] and [10,12] to give
-[2,12]?  I think we would.  The immediate thought to implement this is
-to collapse all ranges to an integer set, and then reconstruct the minimal
-sequence of ranges direct from the set.
-
+My notes: Fine.
 
-Task #2: "Noble Integer
 
-You are given a list, @L, of three or more random integers between 1 and
-50. A Noble Integer is an integer N in @L, such that there are exactly
-N integers greater than N in @L. Output any Noble Integer found in @L,
-or an empty list if none were found.
+Task #2: "Colourful Number
 
-An interesting question is whether or not there can be multiple Noble
-Integers in a list.
+Write a script to display all Colorful Number with 3 digits.
 
-For example,
+    A Colorful Number is an integer where all the products of consecutive
+    subsets of digit are different.
 
-Suppose we have list of 4 integers [2, 6, 1, 3].
-
-Here we have 2 in the above list, known as Noble Integer, since there
-are exactly 2 integers in the list greater than 2: 3 and 6.
-
-Therefore the script would print 2.
+For example, 263 is a Colorful Number since 2, 6, 3, 2x6, 6x3, 2x6x3 are unique.
 "
 
-My notes: Interesting, especially the question about "whether or not there
-can be multiple Noble Integers in a list": If repeated numbers are allowed,
-you can definitely have multiple (identical) noble numbers eg 2 1 1 1 1...
-(each 1 is noble because there's exactly one number >1 (the 2)).  So disallow that.
-Now, given distinct numbers, I don't think multiple noble numbers are possible
-in one list. "find a list with 2 numbers greater than 2 and 3 numbers greater
-than 3" is not possible, because every number greater than 3 is ALSO greater
-than 2, so there are at least as many numbers greater than 2 as there are
-numbers greater than 3, i.e. at least 3 numbers in the list are greater than 2,
-which contradicts the specification that only (exactly) 2 numbers in the list are
-greater than 2.
+My notes: Interesting.
+
+Having written this, assuming that it's correct, I find 328 Colourful 3-digit
+numbers.
diff --git a/challenge-051/duncan-c-white/perl/ch-1.pl b/challenge-051/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..590b4f1288
--- /dev/null
+++ b/challenge-051/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,47 @@
+#!/usr/bin/perl
+#
+# Task 1: "3 Sum
+#
+# Given an array @L of integers, and a target T. Write a script to find
+# all unique triplets such that a + b + c is same as the target T. Also
+# make sure a <= b <= c.
+# 
+# Example:
+# 
+#     @L = (-25, -10, -7, -3, 2, 4, 8, 10);
+# 
+# One such triplet for target 0 i.e. -10 + 2 + 8 = 0.
+# "
+# 
+# My notes: Fine.  The obvious way of achieving a<=b<=c in all
+# answers is to sort @L.
+# 
+
+use feature 'say';
+use strict;
+use warnings;
+#use Function::Parameters;
+#use Data::Dumper;
+
+die "Usage: 3-sum T LIST\n" if @ARGV < 4;
+my $t = shift;
+my @l = @ARGV;
+
+@l = sort @l;
+my $n = @l;
+my %v2p = map { $l[$_] => $_ } 0..$n-1;
+
+foreach my $i (0..$n-3)
+{
+	my $a = $l[$i];
+	foreach my $j ($i+1..$n-2)
+	{
+		my $b = $l[$j];
+		my $sum2 = $a+$b;
+		my $left = $t - $sum2;
+		if( defined $v2p{$left} )
+		{
+			say "found a=$a, b=$b, c=$left (target=$t)";
+		}
+	}
+}
diff --git a/challenge-051/duncan-c-white/perl/ch-2.pl b/challenge-051/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..fe3e3cfe3b
--- /dev/null
+++ b/challenge-051/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,62 @@
+#!/usr/bin/perl
+#
+# Task #2: "Colourful Number
+#
+# Write a script to display all Colorful Number with 3 digits.
+# 
+#     A Colorful Number is an integer where all the products of consecutive
+#     subsets of digit are different.
+# 
+# For example, 263 is a Colorful Number since 2, 6, 3, 2x6, 6x3, 2x6x3 are unique.
+# "
+# 
+# My notes: Interesting.  Having written this, assuming that it's correct, I
+# find 328 Colourful 3-digit numbers.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+#use Data::Dumper;
+
+# for every 3 digit number $i
+foreach my $i (100..999)
+#my $i = 263;
+{
+	say "$i is colourful" if colourful($i);
+}
+
+
+#
+# my $iscol = colourful( $x );
+#	Function to determine whether or not $x is a colourful number,
+#	i.e. an integer where all the products of consecutive subsequences
+#	of digits are different.  Return 1 iff it is; otherwise 0.
+# 
+# For example, 263 is a Colorful Number since 2, 6, 3, 2x6, 6x3, 2x6x3 are unique.
+#
+fun colourful( $x )
+{
+	my @dig = split( //, $x );	# find all digits.
+	my $n = @dig;
+	my %seen;			# combinations already seen.
+	#say "x=$x";
+	foreach my $startpos (0..$n-1)
+	{
+		foreach my $endpos ($startpos..$n-1)
+		{
+			#say "startpos: $startpos, endpos: $endpos";
+			my $prod = 1;
+			foreach my $p ($startpos..$endpos)
+			{
+				$prod *= $dig[$p];
+			}
+			#say "prod=$prod";
+			return 0 if $seen{$prod}++;
+		}
+	}
+	return 1;
+}
+
+