Merge pull request #2676 from dcw803/master

committed my solutions for this week's exercises

4 files changed, 324 insertions, 30 deletions

diff --git a/challenge-084/duncan-c-white/README b/challenge-084/duncan-c-white/README
index fd29cd1f34..45d0cc6f4e 100644
--- a/challenge-084/duncan-c-white/README
+++ b/challenge-084/duncan-c-white/README
@@ -1,54 +1,91 @@
-Task 1: "Words Length
+Task 1: "Reverse Integer
 
-You are given a string $S with 3 or more words.
+You are given an integer $N.
 
-Write a script to find the length of the string except the first and last words ignoring whitespace.
+Write a script to reverse the given integer and print the result. Print
+0 if the result doesn't fit in 32-bit signed integer.
+
+The number 2,147,483,647 is the maximum positive value for a 32-bit
+signed binary integer in computing.
 
 Example 1:
-	Input: $S = "The Weekly Challenge"
-	Output: 6
+
+	Input: 1234
+	Output: 4321
 
 Example 2:
-	Input: $S = "The purpose of our lives is to be happy"
- 	Output: 23
-	ME: WRONG! length(purpose of our lives is to be)==29
 
-My notes: simple, clearly defined: use the power of regexes.
+	Input: -1234
+	Output: -4321
+
+Example 3:
+
+	Input: 1231230512
+	Output: 0
 
 
-Task 2: "Flip Array
+My notes: simple, clearly defined: only tricky bit is the overflow detection
+as Perl **doesn't** use 32bit integers.
 
-You are given an array @A of positive numbers.
 
-Write a script to flip the sign of some members of the given array so
-that the sum of the all members is minimum non-negative.
+Task 2: "Find Square
 
-Given an array of positive elements, you have to flip the sign of some
-of its elements such that the resultant sum of the elements of array
-should be minimum non-negative(as close to zero as possible). Return
-the minimum no. of elements whose sign needs to be flipped such that
-the resultant sum is minimum non-negative.
+You are given a binary matrix of size m x n (all elements are 1 or 0).
+
+Write a script to find the count of squares having all four corners set as 1.
 
 Example 1:
-	Input: @A = (3, 10, 8)
-	Output: 1
+
+Input: [ 0 1 0 1 ]
+       [ 0 0 1 0 ]
+       [ 1 1 0 1 ]
+       [ 1 0 0 1 ]
+
+Output: 1
 
 Explanation:
+	There is one square (3x3) in the given matrix with four corners
+	as 1 starts at r=1;c=2.
 
-Flipping the sign of just one element 10 gives the result 1 i.e. (3) +
-(-10) + (8) = 1
+	[ 1 0 1 ]
+	[ 0 1 0 ]
+	[ 1 0 1 ]
 
 Example 2:
-	Input: @A = (12, 2, 10)
-	Output: 1
+
+Input: [ 1 1 0 1 ]
+       [ 1 1 0 0 ]
+       [ 0 1 1 1 ]
+       [ 1 0 1 1 ]
+
+Output: 4
 
 Explanation:
+	There is one square (4x4) in the given matrix with four corners
+	as 1 starts at r=1;c=1.
+	There is one square (3x3) in the given matrix with four corners as 1
+	starts at r=1;c=2.
+	There are two squares (2x2) in the given matrix with four corners as
+	1. First starts at r=1;c=1 and second starts at r=3;c=3.
+
+Example 3:
+
+Input: [ 0 1 0 1 ]
+       [ 1 0 1 0 ]
+       [ 0 1 0 0 ]
+       [ 1 0 0 1 ]
+
+Output: 0
+
+My notes: clearly defined, seems straightforward.
 
-Flipping the sign of just one element 12 gives the result 0 i.e. (-12) +
-(2) + (10) = 0
+Have to define the Input format: CSV rows on command line so example 3 is:
+./ch-2.pl 0,1,0,1 1,0,1,0 0,1,0,0 1,0,0,1
 
+Initially, I found all RECTANGLES inside the matrix, then rejected those that
+weren't SQUARES - before ever checking whether the corner elements were all 1.
+Find that in ch-2-firstattempt.pl
 
-My notes: clearly defined, but how to go about this one? several
-possible approaches.  brute force: each element may either be
-negated or not; try all combinations:-)  not very elegant, but does
-the job..
+But then I improved that, by directly finding all SQUARES inside the
+matrix, then checked whether their corner elements were all 1.
+This reduces 4 nested loops to 3..
diff --git a/challenge-084/duncan-c-white/perl/ch-1.pl b/challenge-084/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..3f83ef2320
--- /dev/null
+++ b/challenge-084/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,54 @@
+#!/usr/bin/perl
+#
+# Task 1: "Reverse Integer
+#
+# You are given an integer $N.
+# 
+# Write a script to reverse the given integer and print the result. Print
+# 0 if the result doesn't fit in 32-bit signed integer.
+# 
+# The number 2,147,483,647 is the maximum positive value for a 32-bit
+# signed binary integer in computing.
+# 
+# Example 1:
+# 
+# 	Input: 1234
+# 	Output: 4321
+# 
+# Example 2:
+# 
+# 	Input: -1234
+# 	Output: -4321
+# 
+# Example 3:
+# 
+# 	Input: 1231230512
+# 	Output: 0
+# 
+# My notes: simple, clearly defined: only tricky bit is the overflow detection
+# as Perl **doesn't** use 32bit integers.
+#
+
+use strict;
+use warnings;
+use feature 'say';
+use Data::Dumper;
+
+die "Usage: reverse-integer N\n" unless @ARGV==1;
+my $n = shift;
+
+my $maxint = 2147483647;
+
+my $result = "";
+if( $n < 0 )
+{
+	$n = -$n;
+	$result = "-";
+}
+die "n bigger than maxint\n" if $n > $maxint;
+
+my $rev = join('', reverse split(//,$n) );
+
+$result .= $rev;
+$result = 0 if $rev > $maxint;
+say $result;
diff --git a/challenge-084/duncan-c-white/perl/ch-2-firstattempt.pl b/challenge-084/duncan-c-white/perl/ch-2-firstattempt.pl
new file mode 100755
index 0000000000..a01c36f83f
--- /dev/null
+++ b/challenge-084/duncan-c-white/perl/ch-2-firstattempt.pl
@@ -0,0 +1,100 @@
+#!/usr/bin/perl
+#
+# Task 2: "Find Square
+#
+# You are given a binary matrix of size m x n (all elements are 1 or 0).
+# 
+# Write a script to find the count of squares having all four corners set as 1.
+# 
+# Example 1:
+# 
+# Input: [ 0 1 0 1 ]
+#        [ 0 0 1 0 ]
+#        [ 1 1 0 1 ]
+#        [ 1 0 0 1 ]
+# 
+# Output: 1
+# 
+# Explanation:
+# 	There is one square (3x3) in the given matrix with four corners
+# 	as 1 starts at r=1;c=2.
+# 
+# 	[ 1 0 1 ]
+# 	[ 0 1 0 ]
+# 	[ 1 0 1 ]
+# 
+# Example 2:
+# 
+# Input: [ 1 1 0 1 ]
+#        [ 1 1 0 0 ]
+#        [ 0 1 1 1 ]
+#        [ 1 0 1 1 ]
+# 
+# Output: 4
+# 
+# Explanation:
+# 	There is one square (4x4) in the given matrix with four corners
+# 	as 1 starts at r=1;c=1.
+# 	There is one square (3x3) in the given matrix with four corners as 1
+# 	starts at r=1;c=2.
+# 	There are two squares (2x2) in the given matrix with four corners as
+# 	1. First starts at r=1;c=1 and second starts at r=3;c=3.
+# 
+# Example 3:
+# 
+# Input: [ 0 1 0 1 ]
+#        [ 1 0 1 0 ]
+#        [ 0 1 0 0 ]
+#        [ 1 0 0 1 ]
+# 
+# Output: 0
+# 
+# My notes: clearly defined, seems straightforward.
+#
+# Input format: CSV rows on command line so example 3 is:
+# ./ch-2.pl 0,1,0,1 1,0,1,0 0,1,0,0 1,0,0,1
+#
+# This is my first attempt, where I found all RECTANGLES inside the
+# matrix and then rejected those that weren't SQUARES
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+use List::Util 'sum';
+use Data::Dumper;
+
+die "Usage: count-squares list_of_csvrows\n" unless @ARGV;
+my @m;
+foreach my $row (@ARGV)
+{
+	my @r = split(/,/, $row);
+	push @m, \@r;
+}
+#say Dumper(\@m);
+
+my $rows = @m;
+my $cols = @{$m[0]};
+
+my $nsquares = 0;
+foreach my $startr (0..$rows-2)
+{
+	foreach my $startc (0..$cols-2)
+	{
+		next unless $m[$startr][$startc] == 1;
+		foreach my $endr ($startr+1..$rows-1)
+		{
+			foreach my $endc ($startc+1..$cols-1)
+			{
+				next unless $m[$startr][$endc] == 1;
+				next unless $m[$endr][$startc] == 1;
+				next unless $m[$endr][$endc] == 1;
+				next unless $endr-$startr == $endc-$startc;
+				$nsquares++;
+				#say "found square: sr=$startr, sc=$startc, er=$endr, ec=$endc";
+			}
+		}
+	}
+}
+
+say $nsquares;
diff --git a/challenge-084/duncan-c-white/perl/ch-2.pl b/challenge-084/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..25b655e6fd
--- /dev/null
+++ b/challenge-084/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,103 @@
+#!/usr/bin/perl
+#
+# Task 2: "Find Square
+#
+# You are given a binary matrix of size m x n (all elements are 1 or 0).
+# 
+# Write a script to find the count of squares having all four corners set as 1.
+# 
+# Example 1:
+# 
+# Input: [ 0 1 0 1 ]
+#        [ 0 0 1 0 ]
+#        [ 1 1 0 1 ]
+#        [ 1 0 0 1 ]
+# 
+# Output: 1
+# 
+# Explanation:
+# 	There is one square (3x3) in the given matrix with four corners
+# 	as 1 starts at r=1;c=2.
+# 
+# 	[ 1 0 1 ]
+# 	[ 0 1 0 ]
+# 	[ 1 0 1 ]
+# 
+# Example 2:
+# 
+# Input: [ 1 1 0 1 ]
+#        [ 1 1 0 0 ]
+#        [ 0 1 1 1 ]
+#        [ 1 0 1 1 ]
+# 
+# Output: 4
+# 
+# Explanation:
+# 	There is one square (4x4) in the given matrix with four corners
+# 	as 1 starts at r=1;c=1.
+# 	There is one square (3x3) in the given matrix with four corners as 1
+# 	starts at r=1;c=2.
+# 	There are two squares (2x2) in the given matrix with four corners as
+# 	1. First starts at r=1;c=1 and second starts at r=3;c=3.
+# 
+# Example 3:
+# 
+# Input: [ 0 1 0 1 ]
+#        [ 1 0 1 0 ]
+#        [ 0 1 0 0 ]
+#        [ 1 0 0 1 ]
+# 
+# Output: 0
+# 
+# My notes: clearly defined, seems straightforward.
+#
+# Input format: CSV rows on command line so example 3 is:
+# ./ch-2.pl 0,1,0,1 1,0,1,0 0,1,0,0 1,0,0,1
+#
+# This is my second attempt, where I found all SQUARES inside the
+# matrix (rather than all RECTANGLES, checking which were squares)
+# reduces 4 nested loops to 3..
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+use List::Util 'min';
+use Data::Dumper;
+
+die "Usage: count-squares list_of_csvrows\n" unless @ARGV;
+my @m;
+foreach my $row (@ARGV)
+{
+	my @r = split(/,/, $row);
+	push @m, \@r;
+}
+#say Dumper(\@m);
+
+my $rows = @m;
+my $cols = @{$m[0]};
+
+my $nsquares = 0;
+foreach my $startr (0..$rows-2)
+{
+	foreach my $startc (0..$cols-2)
+	{
+		next unless $m[$startr][$startc] == 1;
+		for( my $w=1; ; $w++ )
+		{
+			my $endc = $startc + $w;
+			last if $endc >= $cols;
+
+			my $endr = $startr + $w;
+			last if $endr >= $rows;
+
+			next unless $m[$startr][$endc] == 1;
+			next unless $m[$endr][$startc] == 1;
+			next unless $m[$endr][$endc] == 1;
+			$nsquares++;
+			#say "found 1-square: sr=$startr, sc=$startc, er=$endr, ec=$endc";
+		}
+	}
+}
+
+say $nsquares;