imported my solutions for challenge 67

3 files changed, 180 insertions, 80 deletions

diff --git a/challenge-067/duncan-c-white/README b/challenge-067/duncan-c-white/README
index 634b83d279..36a77b6d74 100644
--- a/challenge-067/duncan-c-white/README
+++ b/challenge-067/duncan-c-white/README
@@ -1,95 +1,41 @@
-Task 1: "Digits Sum
+Task 1: "Number Combinations
 
-You are given two positive numbers $N and $S.
+You are given two integers $m and $n. Write a script print all possible
+combinations of $n numbers from the list 1 2 3 ... $m.
 
-Write a script to list all positive numbers having exactly $N digits
-where sum of all digits equals to $S.
+Every combination should be sorted i.e. [2,3] is a valid combination but
+[3,2] is not.
 
-Example
+Example:
 
-Input:
-    $N = 2
-    $S = 4
+Input: $m = 5, $n = 2
 
-Output:
-    13, 22, 31, 40
+Output: [ [1,2], [1,3], [1,4], [1,5], [2,3], [2,4], [2,5], [3,4], [3,5], [4,5] ]
 "
 
-My notes: sounds like fun.
+My notes: generally I hate permutation questions, but this looks ok.
 
 
-Task 2: "Palindrome Partition
+Task 2: "Letter Phone
 
-You are given a string $S. Write a script print all possible partitions
-that gives Palindrome. Return -1 if none found.
+You are given a digit string $S. Write a script to print all possible letter combinations that the given digit string could represent.
 
-Please make sure, partition should not overlap. For example, for given
-string "abaab", the partition "aba" and "baab" would not be valid,
-since they overlap.
+(1 represents _ or @,
+2 A,B or C,
+3 D,E or F,
+4 G, H or I,
+5 J, K or L,
+6 M, M or O,
+7 P, Q, R or S,
+8 T, U or V,
+9 W, X, Y or Z
+letters from a phone panel)
 
-Example 1
+Example:
 
-Input: $S = 'aabaab'
-Ouput:
- There are 3 possible solutions.
- a) 'aabaa'
- b) 'aa', 'baab'
- c) 'aba'
+  Input: $S = '35'
 
-Example 2
+  Output: ["dj", "dk", "dl", "ej", "ek", "el", "fj", "fk", "fl"].
 
-Input: $S = 'abbaba'
-Output:
- There are 3 possible solutions.
- a) 'abba'
- b) 'bb', 'aba'
- c) 'bab'
-"
-
-My notes: hang on, what exactly do we mean by a "partition"?  this isn't clear!
-
-First: isn't a single letter a substring - an element - of a partition?
-presumably not - otherwise 'a', 'a', 'b', 'a', 'a', 'b' would be a solution
-to the first example.  So presumably each partitioned substring is of
-minimum length 2.
-
-Second: Do all the substrings in a partition have to "span" the string, i.e.
-do all the substrings in a partition have to append together to form the
-original string?  Presumably not, otherwise 'aabaa' would not be a solution to
-the first example.
-
-Third: Can there be more than two elements in a single partition of a string?
-None of the examples show more than two.  I don't know the answer to this one,
-so I'll assume that "there can only one or two elements in a partition".
-
-So this problem is badly specified.  Let's assume that we mean:
-
-"A partition of a string S is either a single substring of minimum length 2
-or a pair of exactly 2 non-overlapping substrings of S, each of minimum length
-2.  Find all partitions of S for which the partition substring(s) are all
-palindromes."
-
-If this isn't the right definition, well damn it, the question should have
-been clearer - and I expect full marks!
-
-Having programmed the above, this also claims (for example) that "aa" is a
-possible solution to example 1 - which is fair enough by the above statement.
-So I tried adding the logic:
-- find the single substrings that are palindromes, call that @p1
-- find the pairs of non-overlapping substrings where each substring is
-  a palindrome, call that @p2
-- remove from @p1 any element that is one of any pair in @p2
-
-But even this shows 4 solutions for example 1:
-
-aabaa
-aba
-aa,baab
-aa,aa
-
-(whereas only the first 3 are expected).  I guess we are saying that aa,aa
-should not a solution because aa,baab is (and baab contains aa)?  I can't
-be bothered to implement this, as the deal is: we implement the problems
-given to us; not we first debug the problem specs given to us and then
-implement the debugged spec.  Please make the problem spec clearer next
-week, Mohammed!
+My notes: sounds pretty easy.  Lookup the set of possibilities for each
+letter, then cross-product them.
diff --git a/challenge-067/duncan-c-white/perl/ch-1.pl b/challenge-067/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..0dea0a7d40
--- /dev/null
+++ b/challenge-067/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,55 @@
+#!/usr/bin/perl
+#
+# Task 1: "Number Combinations
+#
+# You are given two integers $m and $n. Write a script print all possible
+# combinations of $n numbers from the list 1 2 3 ... $m.
+# 
+# Every combination should be sorted i.e. [2,3] is a valid combination but
+# [3,2] is not.
+# 
+# Example:
+# 
+# Input: $m = 5, $n = 2
+# 
+# Output: [ [1,2], [1,3], [1,4], [1,5], [2,3], [2,4], [2,5], [3,4], [3,5], [4,5] ]
+# "
+# 
+# My notes: generally I hate permutation questions, but this looks ok.
+# First digit: may be 1..M-N+1  Second digit: firstdigit+1 .. M-(N-1)+1 etc.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+use Data::Dumper;
+
+die "Usage: number-combinations M N\n" unless @ARGV==2;
+my( $m, $n ) = @ARGV;
+
+
+#
+# my @l = combinations( $lo, $hi, $n, @pre );
+#	Find all sorted combinations of $n digits from $lo..$hi
+#	prepending @pre to every combination found.
+#
+fun combinations( $lo, $hi, $n, @pre )	# @pre is a list of numbers
+{
+	#say "combinations: lo=$lo, hi=$hi, n=$n, x=", join(',',@pre);
+	my @l;			# list of lists
+	foreach my $i ($lo..$hi-$n+1)
+	{
+		my @y = @pre;
+		push @y, $i;
+		#say "i=$i, y=", Dumper \@y;
+		push @l, $n==1 ?
+			[ @y ] :
+			combinations( $i+1, $hi, $n-1, @y );
+	}
+	return @l;
+}
+
+
+my @l = combinations( 1, $m, $n, () );
+say '[ ', join(', ', map { '['. join(',',@$_). ']' } @l ), ' ]';
diff --git a/challenge-067/duncan-c-white/perl/ch-2.pl b/challenge-067/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..3dd44bd36e
--- /dev/null
+++ b/challenge-067/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,99 @@
+#!/usr/bin/perl
+#
+# Task 2: "Letter Phone
+#
+# You are given a digit string $S. Write a script to print all possible
+# letter combinations that the given digit string could represent.
+# 
+# (1 represents _ or @,
+# 2 A,B or C,
+# 3 D,E or F,
+# 4 G, H or I,
+# 5 J, K or L,
+# 6 M, M or O,
+# 7 P, Q, R or S,
+# 8 T, U or V,
+# 9 W, X, Y or Z
+# letters from a phone panel)
+# 
+# Example:
+# 
+#   Input: $S = '35'
+# 
+#   Output: ["dj", "dk", "dl", "ej", "ek", "el", "fj", "fk", "fl"].
+# 
+# My notes: sounds pretty easy.  Lookup the set of possibilities for each
+# letter, then cross-product them.
+#
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+use Data::Dumper;
+
+die "Usage: letter-phone numstring\n" unless @ARGV==1;
+my $numstring = shift;
+
+my %data = (1 => '_@',
+	2 => 'abc',
+	3 => 'def',
+	4 => 'ghi',
+	5 => 'jkl',
+	6 => 'mmo',
+	7 => 'pqrs',
+	8 => 'tuv',
+	9 => 'wxyz',
+	);
+
+#
+# my @out = cross( @str );
+#	Given an array of strings, where each string represents
+#	alternative letters, form an array of all cross-products
+#	of all those letters.
+#	eg. cross( 'DEF', 'GHI' ) = ( 'DG', DH', 'DI', 'EG'..)
+#
+fun cross( @str )
+{
+	my $first = shift @str;
+	my @x = split(//,$first);
+	foreach my $next (@str)
+	{
+		@x = cross_one( $next, @x );
+	}
+	return @x;
+}
+
+
+#
+# my @out = cross_one( $next, @x );
+#	Given a string $next (representing alternative letters) and an
+#	array of strings @x, form a new array @out which contains every
+#	element of @x with every letter in $next appended.
+#	eg cross_one( 'DEF', 'X', 'Y' ) gives 'XD', 'XE', 'XF', 'YD'..
+#
+fun cross_one( $next, @x )
+{
+	my @out;
+	my @letters = split(//,$next);
+	foreach my $word (@x)
+	{
+		foreach my $letter (@letters)
+		{
+			push @out, $word.$letter;
+		}
+	}
+	return @out;
+}
+
+
+my @str;
+foreach my $digit (split(//,$numstring))
+{
+	die "bad digit $digit in $numstring" unless defined $data{$digit};
+	push @str, $data{$digit};
+}
+#say Dumper \@str;
+
+my @out = cross( @str );
+say "[", join(',', map { "'$_'" } @out), "]";