Merge pull request #3635 from dcw803/master

imported my solutions for this week's tasks

3 files changed, 418 insertions, 44 deletions

diff --git a/challenge-101/duncan-c-white/README b/challenge-101/duncan-c-white/README
index 75645a7654..32eaf793d3 100644
--- a/challenge-101/duncan-c-white/README
+++ b/challenge-101/duncan-c-white/README
@@ -1,73 +1,104 @@
-Task 1: "Fun Time
+Task 1: "Pack a Spiral
+Submitted by: Stuart Little
 
-You are given a time (12 hour / 24 hour).
+You are given an array @A of items (integers say, but they can be anything).
 
-Write a script to convert the given time from 12 hour format to 24 hour
-format and vice versa.
+Your task is to pack that array into an MxN matrix spirally
+counterclockwise, as tightly as possible.
 
-Ideally we expect a one-liner.
+'Tightly' means the absolute value |M-N| of the difference has to be as
+small as possible.
 
 Example 1:
-	Input: 05:15 pm or 05:15pm
-	Output: 17:15
+
+	Input: @A = (1,2,3,4)
+
+	Output:
+
+	    4 3
+	    1 2
+
+Since the given array is already a 1x4 matrix on its own, but that's
+not as tight as possible. Instead, you'd spiral it counterclockwise into
+
+    4 3
+    1 2
 
 Example 2:
-	Input: 19:15
-	Output: 07:15 pm or 07:15pm
-"
 
-My notes: very simple, I like one liners.  In ch-1.sh, you'll see 2 slightly
-different versions, both with decent error checking.
+	Input: @A = (1..6)
 
+	Output:
 
-Task 2: "Triangle Sum
+	    6 5 4
+	    1 2 3
 
-You are given a triangle array.
+	or
 
-Write a script to find the minimum path sum from top to bottom.
+	    5 4
+	    6 3
+	    1 2
 
-When you are on index i on the current row then you may move to either
-index i or index i + 1 on the next row.
+	Either will do as an answer, because they're equally tight.
 
-Example 1:
-	Input: Triangle = [ [1], [2,4], [6,4,9], [5,1,7,2] ]
-	Output: 8
+Example 3:
 
-Explanation: The given triangle
+	Input: @A = (1..12)
 
-            1
-           2 4
-          6 4 9
-         5 1 7 2
+	Output:
 
-The minimum path sum from top to bottom:  1 + 2 + 4 + 1 = 8
+	       9  8  7 6
+	      10 11 12 5
+	       1  2  3 4
 
-             [1]
-           [2]  4
-           6 [4] 9
-          5 [1] 7 2
+	or
 
-Example 2:
+	       8  7 6
+	       9 12 5
+	      10 11 4
+	       1  2 3
+"
 
-	Input: Triangle = [ [3], [3,1], [5,2,3], [4,3,1,3] ]
-	Output: 7
+My notes: ok, interesting question.  First, need to find "tightest" MxN
+where abs(M-N) is minimum, easy.  Second, need to build MxN array via
+a "counterclockwise spiral starting at bottom corner".  Not trivial, but
+should be relatively easy.   Hmmm.. actually, I can't see a particularly
+quick and easy way, I'm sure I'm missing something.
 
-Explanation: The given triangle
 
-            3
-           3 1
-          5 2 3
-         4 3 1 3
+Task 2: "Origin-containing Triangle
+Submitted by: Stuart Little
+
+You are given three points in the plane, as a list of six co-ordinates:
+A=(x1,y1), B=(x2,y2) and C=(x3,y3).
+
+Write a script to find out if the triangle formed by the given three
+co-ordinates contain origin (0,0).
+
+Print 1 if found otherwise 0.
+
+Example 1:
+
+	Input: A=(0,1), B=(1,0) and C=(2,2)
+
+	Output: 0 because that triangle does not contain (0,0).
+
+Example 2:
 
-The minimum path sum from top to bottom: 3 + 1 + 2 + 1 = 7
+	Input: A=(1,1), B=(-1,1) and C=(0,-3)
 
-             [3]
-            3  [1]
-           5 [2] 3
-          4 3 [1] 3
+	Output: 1 because that triangle contains (0,0) in its interior.
 
+Example 3:
 
+	Input: A=(0,1), B=(2,0) and C=(-6,0)
 
+	Output: 1 because (0,0) is on the edge connecting B and C.
 "
 
-My notes: nice question.
+My notes: oh, God.  Geometry.  I hate geometry.  Intuitively I've no
+idea how to do this, so need to Google for solutions.  Many different
+ways, vectors, cross products, etc.  Easiest to understand is from
+www.geeksforgeeks.org/check-whether-a-given-point-lies-inside-a-triangle-or-not/
+and it seems to work (even it compares areas with "==").  Hmm, this seems
+easier than Task 1!
diff --git a/challenge-101/duncan-c-white/perl/ch-1.pl b/challenge-101/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..c227736bd4
--- /dev/null
+++ b/challenge-101/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,252 @@
+#!/usr/bin/perl
+# 
+# Task 1: "Pack a Spiral
+# Submitted by: Stuart Little
+# 
+# You are given an array @A of items (integers say, but they can be anything).
+# 
+# Your task is to pack that array into an MxN matrix spirally
+# counterclockwise, as tightly as possible.
+# 
+# 'Tightly' means the absolute value |M-N| of the difference has to be as
+# small as possible.
+# 
+# Example 1:
+# 
+# 	Input: @A = (1,2,3,4)
+# 
+# 	Output:
+# 
+# 	    4 3
+# 	    1 2
+# 
+# Since the given array is already a 1x4 matrix on its own, but that's
+# not as tight as possible. Instead, you'd spiral it counterclockwise into
+# 
+#     4 3
+#     1 2
+# 
+# Example 2:
+# 
+# 	Input: @A = (1..6)
+# 
+# 	Output:
+# 
+# 	    6 5 4
+# 	    1 2 3
+# 
+# 	or
+# 
+# 	    5 4
+# 	    6 3
+# 	    1 2
+# 
+# 	Either will do as an answer, because they're equally tight.
+# 
+# Example 3:
+# 
+# 	Input: @A = (1..12)
+# 
+# 	Output:
+# 
+# 	       9  8  7 6
+# 	      10 11 12 5
+# 	       1  2  3 4
+# 
+# 	or
+# 
+# 	       8  7 6
+# 	       9 12 5
+# 	      10 11 4
+# 	       1  2 3
+# "
+# 
+# My notes: ok, interesting question.  First, need to find "tightest" MxN
+# where abs(M-N) is minimum, easy.  Second, need to build MxN array via
+# a "counterclockwise spiral starting at bottom corner".  Not trivial, but
+# should be relatively easy.   Hmmm.. actually, I can't see a particularly
+# quick and easy way, I'm sure I'm missing something.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use Function::Parameters;
+use Data::Dumper;
+
+my $debug=0;
+die "Usage: pack-spiral [--debug] list of numbers\n"
+	unless GetOptions( "debug" => \$debug )
+	    && @ARGV>0;
+
+my @v = @ARGV;
+
+my $nvals = @v;
+my( $m, $n ) = findtightestMxN( $nvals );
+say "nvals=$nvals, best m=$m, best n=$n" if $debug;
+
+my @mat = spiral( $m, $n, @v );
+say mat2str( @mat );
+
+
+#
+# my( $m, $n ) = findtightestMxN( $nvals );
+#	Given $nvals, the number of values, find the tightest
+#	("most square" M x N == $nvals.
+#
+fun findtightestMxN( $nvals )
+{
+	my $limit = int(sqrt($nvals));
+
+	my $bestm = 1;
+	my $bestn = $nvals;
+	my $bestdiff = $nvals-1;
+
+	foreach my $m (1..$limit)
+	{
+		next unless $nvals % $m == 0;
+		my $n = $nvals / $m;
+		my $diff = abs($m-$n);
+		next unless $diff < $bestdiff;
+		$bestm = $m;
+		$bestn = $n;
+		$bestdiff = $diff;
+	}
+
+	return ($bestm, $bestn);
+}
+
+
+#
+# my $str = mat2str( @mat );
+#	Generate a printable version of the 2-d matrix @mat.
+#
+fun mat2str( @mat )
+{
+	my $result = "";
+	foreach my $row (@mat)
+	{
+		$result .= join( "  ",
+			map {
+				defined $_ ? sprintf("%2d",$_) : ' ?'
+			} @$row ) . "\n";
+	}
+	return $result;
+}
+
+
+#
+# my @mat = spiral( $m, $n, @v );
+#	Make an M x N 2d matrix containing the values from @v
+#	packed into a counterclockwise spiral starting from the
+#	lower left corner.
+#
+our @the_mat;	# shared between rest of functions below..
+our @vals;	# ditto..
+
+fun spiral( $m, $n, @v )
+{
+	@the_mat = map { [ (undef) x $n ] } 1..$m;
+	@vals = @v;
+
+	# start going east from (m-1, -1)
+	east( $m-1, -1, $m, $n );
+
+	return @the_mat;
+}
+
+
+#
+# east( $currm, $currn, $m, $n );
+#	Move EAST $n times using values from global @vals, adding
+#	them to global $the_mat[$currm][$currn..], then carry the spiral
+#	on to an M-1 x N matrix, NORTH, then WEST..
+#
+fun east( $currm, $currn, $m, $n )
+{
+	my $mstr = "E($currm,$currn,$m,$n):\n".mat2str(@the_mat);
+	say $mstr if $debug;
+	foreach my $i (1..$n)
+	{
+		return unless @vals;
+		die "run out of values in $mstr\n" unless @vals;
+		my $val = shift @vals;
+		$currn++;
+		$the_mat[$currm][$currn] = $val;
+	}
+
+	# have now dealt with current row, (m-1) x n matrix to fill, north
+	north( $currm, $currn, $m-1, $n ) if @vals;
+}
+
+
+#
+# north( $currm, $currn, $m, $n );
+#	Move NORTH $m times using values from global @vals, adding
+#	them to global $the_mat[$currm][$currn..], then carry the spiral
+#	on (WEST, then SOUTH, then EAST, then NORTH again...)
+#
+fun north( $currm, $currn, $m, $n )
+{
+	my $mstr = "N($currm,$currn,$m,$n):\n".mat2str(@the_mat);
+	say $mstr if $debug;
+	foreach my $i (1..$m)
+	{
+		return unless @vals;
+		die "run out of values in $mstr\n" unless @vals;
+		my $val = shift @vals;
+		$currm--;
+		$the_mat[$currm][$currn] = $val;
+	}
+
+
+	# have now dealt with current col, m x (n-1) matrix to fill, west..
+	west( $currm, $currn, $m, $n-1 ) if @vals;
+}
+
+
+#
+# west( $currm, $currn, $m, $n );
+#	Move WEST $n times using values from global @vals, adding
+#	them to global $the_mat[$currm][$currn..], then carry the spiral
+#	on (SOUTH, then EAST...)
+#
+fun west( $currm, $currn, $m, $n )
+{
+	my $mstr = "W($currm,$currn,$m,$n):\n".mat2str(@the_mat);
+	say $mstr if $debug;
+	foreach my $i (1..$n)
+	{
+		return unless @vals;
+		die "run out of values in $mstr\n" unless @vals;
+		my $val = shift @vals;
+		$currn--;
+		$the_mat[$currm][$currn] = $val;
+	}
+
+	south( $currm, $currn, $m-1, $n ) if @vals;
+}
+
+
+#
+# south( $currm, $currn, $m, $n );
+#	Move SOUTH $m times using values from global @vals, adding
+#	them to global $the_mat[$currm][$currn..], then carry the spiral
+#	on (EAST, then NORTH again...)
+#
+fun south( $currm, $currn, $m, $n )
+{
+	my $mstr = "S($currm,$currn,$m,$n):\n".mat2str(@the_mat);
+	say $mstr if $debug;
+	foreach my $i (1..$m)
+	{
+		return unless @vals;
+		die "run out of values in $mstr\n" unless @vals;
+		my $val = shift @vals;
+		$currm++;
+		$the_mat[$currm][$currn] = $val;
+	}
+
+	east( $currm, $currn, $m, $n-1 ) if @vals;
+}
diff --git a/challenge-101/duncan-c-white/perl/ch-2.pl b/challenge-101/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..7dd0c8fa45
--- /dev/null
+++ b/challenge-101/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,91 @@
+#!/usr/bin/perl
+# 
+# Task 2: "Origin-containing Triangle
+# Submitted by: Stuart Little
+# 
+# You are given three points in the plane, as a list of six co-ordinates:
+# A=(x1,y1), B=(x2,y2) and C=(x3,y3).
+# 
+# Write a script to find out if the triangle formed by the given three
+# co-ordinates contain origin (0,0).
+# 
+# Print 1 if found otherwise 0.
+# 
+# Example 1:
+# 
+# 	Input: A=(0,1), B=(1,0) and C=(2,2)
+# 
+# 	Output: 0 because that triangle does not contain (0,0).
+# 
+# Example 2:
+# 
+# 	Input: A=(1,1), B=(-1,1) and C=(0,-3)
+# 
+# 	Output: 1 because that triangle contains (0,0) in its interior.
+# 
+# Example 3:
+# 
+# 	Input: A=(0,1), B=(2,0) and C=(-6,0)
+# 
+# 	Output: 1 because (0,0) is on the edge connecting B and C.
+# "
+# 
+# My notes: oh, God.  Geometry.  I hate geometry.  Intuitively I've no
+# idea how to do this, so need to Google for solutions.  Many different
+# ways, vectors, cross products, etc.  Easiest to understand is from
+# www.geeksforgeeks.org/check-whether-a-given-point-lies-inside-a-triangle-or-not/
+# and it seems to work (even it compares areas with "==").  Hmm, this seems
+# easier than Task 1!
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+use Data::Dumper;
+
+my $debug=0;
+die "Usage: triangle-contains-origin x1 y1 x2 y2 x3 y3\n"
+	    unless @ARGV==6;
+
+my( $x1, $y1, $x2, $y2, $x3, $y3 ) = @ARGV;
+
+say "\nInput: A($x1,$y1), B($x2,$y2), C($x3,$y3)";
+
+my $isinside = isInside( $x1, $y1, $x2, $y2, $x3, $y3, 0, 0 );
+say "\nOutput: $isinside - ". ( $isinside ? "Inside" : "Outside" );
+
+
+#
+# my $area = area( $x1, $y1, $x2, $y2, $x3, $y3 );
+#	Calculate area of triangle formed by (x1, y1),  
+#	(x2, y2) and (x3, y3).
+#
+fun area( $x1, $y1, $x2, $y2, $x3, $y3 )
+{
+	return abs(($x1*($y2-$y3) + $x2*($y3-$y1)+ $x3*($y1-$y2))/2.0);
+}
+
+#
+# my $isinside = isInside( $x1, $y1, $x2, $y2, $x3, $y3, $x, $y );
+#	Check whether point P(x, y) lies inside the triangle formed  
+#	by A(x1, y1), B(x2, y2) and C(x3, y3)
+#
+fun isInside( $x1, $y1, $x2, $y2, $x3, $y3, $x, $y )
+{
+   # Calculate area of triangle ABC
+   my $A = area( $x1, $y1, $x2, $y2, $x3, $y3); 
+  
+   # Calculate area of triangle PBC
+   my $A1 = area( $x, $y, $x2, $y2, $x3, $y3); 
+  
+   # Calculate area of triangle PAC
+   my $A2 = area( $x1, $y1, $x, $y, $x3, $y3); 
+  
+   # Calculate area of triangle PAB
+   my $A3 = area( $x1, $y1, $x2, $y2, $x, $y); 
+    
+   # Check if sum of A1, A2 and A3 is same as A
+   return ($A == $A1 + $A2 + $A3) ? 1 : 0; 
+}
+