Merge pull request #2878 from dcw803/master

imported my solutions; liked both tasks

3 files changed, 245 insertions, 44 deletions

diff --git a/challenge-088/duncan-c-white/README b/challenge-088/duncan-c-white/README
index 5fd57a5033..decc181333 100644
--- a/challenge-088/duncan-c-white/README
+++ b/challenge-088/duncan-c-white/README
@@ -1,70 +1,63 @@
-Task 1: "Longest Consecutive Sequence
+Task 1: "Array of Product
 
-You are given an unsorted array of integers @N.
+You are given an array of positive integers @N.
 
-Write a script to find the longest consecutive sequence. Print 0 if no sequence found.
+Write a script to return an array @M where $M[i] is the product of all elements of @N except the index $N[i].
 
 Example 1:
 
-	Input: @N = (100, 4, 50, 3, 2)
-	Output: (2, 3, 4)
+Input:
+    @N = (5, 2, 1, 4, 3)
+Output:
+    @M = (24, 60, 120, 30, 40)
 
-Example 2:
+    $M[0] = 2 x 1 x 4 x 3 = 24
+    $M[1] = 5 x 1 x 4 x 3 = 60
+    $M[2] = 5 x 2 x 4 x 3 = 120
+    $M[3] = 5 x 2 x 1 x 3 = 30
+    $M[4] = 5 x 2 x 1 x 4 = 40
 
-	Input: @N = (20, 30, 10, 40, 50)
-	Output: 0
+Example 2:
 
-Example 3:
+Input:
+    @N = (2, 1, 4, 3)
+Output:
+    @M = (12, 24, 6, 8)
 
-	Input: @N = (20, 19, 9, 11, 10)
-	Output: (9, 10, 11)
+    $M[0] = 1 x 4 x 3 = 12
+    $M[1] = 2 x 4 x 3 = 24
+    $M[2] = 2 x 1 x 3 = 6
+    $M[3] = 2 x 1 x 4 = 8
 "
 
-My notes: clearly defined, sort it first, then walk list looking for sequences
+My notes: clearly defined.  So M[i] is product(all elements)/M[i]
+Hang on! unless M[i]==0 in which it's product(all other elements)
 
 
-Task 2: "Largest Rectangle
+Task 2: "Spiral Matrix
 
-You are given binary matrix m x n with all values being 0 or 1.
+You are given m x n matrix of positive integers.
 
-Write a script to find the largest rectangle containing only 1. Print 0 if none found.
+Write a script to print a spiral path throught the matrix as list.
 
 Example 1:
 
 Input:
-    [ 0 0 0 1 0 0 ]
-    [ 1 1 1 0 0 0 ]
-    [ 0 0 1 0 0 1 ]
-    [ 1 1 1 1 1 0 ]
-    [ 1 1 1 1 1 0 ]
-
-Output:
-    [ 1 1 1 1 1 ]
-    [ 1 1 1 1 1 ]
+    [ 1, 2, 3 ]
+    [ 4, 5, 6 ]
+    [ 7, 8, 9 ]
+Ouput:
+    [ 1, 2, 3, 6, 9, 8, 7, 4, 5 ]
 
 Example 2:
 
 Input:
-    [ 1 0 1 0 1 0 ]
-    [ 0 1 0 1 0 1 ]
-    [ 1 0 1 0 1 0 ]
-    [ 0 1 0 1 0 1 ]
-
-Output: 0
-
-Example 3:
-
-Input:
-    [ 0 0 0 1 1 1 ]
-    [ 1 1 1 1 1 1 ]
-    [ 0 0 1 0 0 1 ]
-    [ 0 0 1 1 1 1 ]
-    [ 0 0 1 1 1 1 ]
-
+    [  1,  2,  3,  4 ]
+    [  5,  6,  7,  8 ]
+    [  9, 10, 11, 12 ]
+    [ 13, 14, 15, 16 ]
 Output:
-    [ 1 1 1 1 ]
-    [ 1 1 1 1 ]
+    [ 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10 ]
 "
 
-My notes: clearly defined, I assume that a rectangle has min-width 2,
-min-height 2, brute force: find all rectangles, pick max area
+My notes: clearly defined.  Is "a spiral path" clear?  Think so.
diff --git a/challenge-088/duncan-c-white/perl/ch-1.pl b/challenge-088/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..660c6b2130
--- /dev/null
+++ b/challenge-088/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,66 @@
+#!/usr/bin/perl
+#
+# Task 1: "Array of Product
+# 
+# You are given an array of positive integers @N.
+# 
+# Write a script to return an array @M where $M[i] is the product of all elements of @N except the index $N[i].
+# 
+# Example 1:
+# 
+# Input:
+#     @N = (5, 2, 1, 4, 3)
+# Output:
+#     @M = (24, 60, 120, 30, 40)
+# 
+#     $M[0] = 2 x 1 x 4 x 3 = 24
+#     $M[1] = 5 x 1 x 4 x 3 = 60
+#     $M[2] = 5 x 2 x 4 x 3 = 120
+#     $M[3] = 5 x 2 x 1 x 3 = 30
+#     $M[4] = 5 x 2 x 1 x 4 = 40
+# 
+# Example 2:
+# 
+# Input:
+#     @N = (2, 1, 4, 3)
+# Output:
+#     @M = (12, 24, 6, 8)
+# 
+#     $M[0] = 1 x 4 x 3 = 12
+#     $M[1] = 2 x 4 x 3 = 24
+#     $M[2] = 2 x 1 x 3 = 6
+#     $M[3] = 2 x 1 x 4 = 8
+# "
+# 
+# My notes: clearly defined.  So M[i] is product(all elements)/M[i].
+#	Hang on! unless M[i]==0 in which it's product(all other elements)
+#
+
+use strict;
+use warnings;
+use feature 'say';
+#use Data::Dumper;
+use Getopt::Long;
+use List::Util qw(product);
+
+#
+# my $p = prod_except($pos, @x);
+#	Compute and return the product of all elements of @x EXCEPT ELEMENT $pos.
+#
+sub prod_except
+{
+	my( $pos, @x ) = @_;
+	splice( @x, $pos, 1 );
+	return product(@x);
+}
+
+
+
+my $debug = 0;
+die "Usage: array-of-product [--debug] array\n" unless
+	GetOptions( "debug" => \$debug ) &&
+	@ARGV>1;
+my @x = @ARGV;
+my $prod = product(@x);
+@x = map { $x[$_]==0 ? prod_except($_, @x) : $prod / $x[$_] } 0..$#x;
+say for @x;
diff --git a/challenge-088/duncan-c-white/perl/ch-2.pl b/challenge-088/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..9ddc797753
--- /dev/null
+++ b/challenge-088/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,142 @@
+#!/usr/bin/perl
+#
+# Task 2: "Spiral Matrix
+# 
+# You are given m x n matrix of positive integers.
+# 
+# Write a script to print a spiral path throught the matrix as list.
+# 
+# Example 1:
+# 
+# Input:
+#     [ 1, 2, 3 ]
+#     [ 4, 5, 6 ]
+#     [ 7, 8, 9 ]
+# Output:
+#     [ 1, 2, 3, 6, 9, 8, 7, 4, 5 ]
+# 
+# Example 2:
+# 
+# Input:
+#     [  1,  2,  3,  4 ]
+#     [  5,  6,  7,  8 ]
+#     [  9, 10, 11, 12 ]
+#     [ 13, 14, 15, 16 ]
+# Output:
+#     [ 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10 ]
+# "
+# 
+# My notes: clearly defined.  Is "a spiral path" clear?  Think so.
+# How to do this?  Given non-square matrix:
+#  1,  2,  3,  4,  5
+#  6,  7,  8,  9, 10
+# 11, 12, 13, 14, 15
+# 16, 17, 18, 19, 20
+# 
+# - we first consume whole top row: 1  2  3  4  5
+# matrix now:
+#  6  7  8  9 10
+# 11 12 13 14 15
+# 16 17 18 19 20
+# - consume whole last column, top to bottom: 10 15 20
+# matrix now:
+#  6  7  8  9
+# 11 12 13 14
+# 16 17 18 19
+# - consume whole bottom row, backwards: 19 18 17 16
+#  matrix now:
+#  6  7  8  9
+# 11 12 13 14
+# - consume whole first column, bottom to top: 11 6
+#  matrix now:
+#  7  8  9
+# 12 13 14
+# - repeat: consume whole top row: 7 8 9
+#  matrix now:
+# 12 13 14
+# - consume whole last column: 14
+#  matrix now:
+# 12 13
+# - consume whole bottom row, backwards: 13 12
+# matrix empty
+#
+
+use strict;
+use warnings;
+use Data::Dumper;
+use Function::Parameters;
+use feature 'say';
+
+# Read the matrix ignoring everything but digits and commas..
+my @m;
+my $rowlen = undef;
+while( <> )
+{
+	chomp;
+	tr/0-9,//cd;
+	my @row = split( /,/ );
+	unless( defined $rowlen )
+	{
+		$rowlen = @row;
+	} else
+	{
+		die "matrix: line $. ($_) of wrong length, should be $rowlen\n"
+			unless $rowlen == @row;
+	}
+	push @m, \@row;
+}
+#say Dumper(\@m);
+
+#
+# my @l = spiral( $ncols, @m );
+#	Trace a spiral path through @m, each row of which has
+#	$ncols columns.  Return the list of matrix elements.
+#
+fun spiral( $ncols, @m )
+{
+	my @l;
+	while( @m )
+	{
+		# consume top row
+		my $toprow = shift @m;
+		push @l, @$toprow;
+
+	last if @m==0;
+
+		# consume last column
+		foreach my $row (@m)
+		{
+			my $val = pop(@$row);
+			push @l, $val;
+		}
+
+		$ncols--;
+
+	last if $ncols==0;
+
+		# consume bottom row, backwards
+		my $bottomrow = pop @m;
+		push @l, reverse @$bottomrow;
+
+	last if @m==0;
+
+		# consume first column, upwards
+		my @rev;
+		foreach my $row (@m)
+		{
+			my $val = shift(@$row);
+			push @rev, $val;
+		}
+		push @l, reverse @rev;
+
+		$ncols--;
+
+	last if $ncols==0;
+
+	}
+	return @l;
+}
+
+my @l = spiral( $rowlen, @m );
+say for @l;
+