Merge pull request #4845 from dcw803/master

imported my solutions to this week's challenge

3 files changed, 277 insertions, 39 deletions

diff --git a/challenge-128/duncan-c-white/README b/challenge-128/duncan-c-white/README
index bc6fe8dd99..aaac2e3ac2 100644
--- a/challenge-128/duncan-c-white/README
+++ b/challenge-128/duncan-c-white/README
@@ -1,57 +1,60 @@
-Task 1: "Disjoint Sets
+Task 1: "Maximum Sub-Matrix
 
-You are given two sets with unique integers.
+You are given m x n binary matrix having 0 or 1 elements.
 
-Write a script to figure out if they are disjoint.
+Write a script to find out maximum sub-matrix having only 0.
 
-The two sets are disjoint if they don't have any common members.
+Example 1:
 
-Example
+Input : [ 1 0 0 0 1 0 ]
+        [ 1 1 0 0 0 1 ]
+        [ 1 0 0 0 0 0 ]
 
-  Input: @S1 = (1, 2, 5, 3, 4)
-         @S2 = (4, 6, 7, 8, 9)
-  Output: 0 as the given two sets have common member 4.
+Output: [ 0 0 0 ]
+        [ 0 0 0 ]
 
-  Input: @S1 = (1, 3, 5, 7, 9)
-         @S2 = (0, 2, 4, 6, 8)
-  Output: 1 as the given two sets do not have common member.
+Example 2:
+
+Input : [ 0 0 1 1 ]
+        [ 0 0 0 1 ]
+        [ 0 0 1 0 ]
+
+Output: [ 0 0 ]
+        [ 0 0 ]
+        [ 0 0 ]
 "
 
-My notes: very easy:  Intersection is not empty.
+My notes: dull but easy.  No opportunity for cleverness.
 
 
-Task 2: "Conflict Intervals
+Task 2: "Minimum Platforms
 
-You are given a list of intervals.
+You are given two arrays of arrival and departure times of trains at a
+railway station.
 
-Write a script to find out if the current interval conflicts with any
-of the previous intervals.
+Write a script to find out the minimum number of platforms needed so
+that no train needs to wait.
 
-Example
+Example 1:
 
-Input: @Intervals = [ (1,4), (3,5), (6,8), (12, 13), (3,20) ]
-Output: [ (3,5), (3,20) ]
+Input: @arrivals   = (11:20, 14:30)
+       @departures = (11:50, 15:00)
+Output: 1
 
-    - The 1st interval (1,4) have no previous intervals to compare, skip it.
-    - The 2nd interval (3,5) conflicts with previous interval (1,4).
-    - The 3rd interval (6,8) does not conflict with any of the previous
-      intervals (1,4) and (3,5), so skip it.
-    - The 4th interval (12,13) again does not conflict with any of the
-      previous intervals (1,4), (3,5) and (6,8), so skip it.
-    - The 5th interval (3,20) conflicts with the first interval (1,4).
+The 1st arrival of train is at 11:20 and this is the only train at the station,
+so you need 1 platform.  Before the second arrival at 14:30, the first train
+left the station at 11:50, so you still need only 1 platform.
 
-Input: @Intervals = [ (3,4), (5,7), (6,9), (10, 12), (13,15) ]
-Output: [ (6,9) ]
+Example 2:
 
-    - The 1st interval (3,4) has no previous intervals to compare, skip it.
-    - The 2nd interval (5,7) does not conflict with the previous interval
-      (3,4), so skip it.
-    - The 3rd interval (6,9) does conflict with one of the previous intervals
-      (5,7).
-    - The 4th interval (10,12) do not conflicts with any of the previous
-      intervals (3,4), (5,7) and (6,9), so skip it.
-    - The 5th interval (13,15) do not conflicts with any of the previous
-      intervals (3,4), (5,7), (6,9) and (10,12), so skip it.
-"
+Input: @arrivals   = (10:20, 11:00, 11:10, 12:20, 16:20, 19:00)
+       @departures = (10:30, 13:20, 12:40, 12:50, 20:20, 21:20)
+Output: 3
+
+Between 12:20 and 12:40, there would be at least 3 trains at the station,
+so we need minimum 3 platforms."
 
-My notes: also looks pretty easy.  I think "conflict" means "overlap".
+My notes: nice problem - looks like a tiny discrete event simulation.
+Build a DIARY: an array of (time, type) pairs - where type == 'A' for
+an arrival, or type == 'D' for a departure.  Then walk the diary,
+simulating "train arrival" and "train departure" events.
diff --git a/challenge-128/duncan-c-white/perl/ch-1.pl b/challenge-128/duncan-c-white/perl/ch-1.pl
new file mode 100755
index 0000000000..425c49cc15
--- /dev/null
+++ b/challenge-128/duncan-c-white/perl/ch-1.pl
@@ -0,0 +1,123 @@
+#!/usr/bin/perl
+# 
+# Task 1: "Maximum Sub-Matrix
+# 
+# You are given m x n binary matrix having 0 or 1 elements.
+# 
+# Write a script to find out maximum sub-matrix having only 0.
+# 
+# Example 1:
+# 
+# Input : [ 1 0 0 0 1 0 ]
+#         [ 1 1 0 0 0 1 ]
+#         [ 1 0 0 0 0 0 ]
+# 
+# Output: [ 0 0 0 ]
+#         [ 0 0 0 ]
+# 
+# Note that:  [ 0 0 ]
+#	      [ 0 0 ]
+#	      [ 0 0 ]
+# is an equally good answer: both have area 6.
+#
+# Example 2:
+# 
+# Input : [ 0 0 1 1 ]
+#         [ 0 0 0 1 ]
+#         [ 0 0 1 0 ]
+# 
+# Output: [ 0 0 ]
+#         [ 0 0 ]
+#         [ 0 0 ]
+# "
+# 
+# My notes: dull but easy.  No opportunity for cleverness.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Getopt::Long;
+use Data::Dumper;
+
+my $debug=0;
+die "Usage: max-sub-matrix [-d|--debug] binary_matrix_in_row_order\n".
+    "       eg. 0011 0001 0010\n" unless
+	GetOptions( "debug"=>\$debug ) && @ARGV>0;
+
+my @m = map { die "bad row $_\n" unless /^[01]+$/; [ split( //, $_ ) ] } @ARGV;
+#die Dumper \@m;
+
+my( $topr, $topc, $nr, $nc ) = maxsubmatrix( @m );
+print "topr=$topr, topc=$topc, nr=$nr, nc=$nc\n";
+
+for( my $r=$topr; $r<$topr+$nr; $r++ )
+{
+	print "[ ";
+	for( my $c=$topc; $c<$topc+$nc; $c++ )
+	{
+		print "$m[$r][$c] ";
+	}
+	print "]\n";
+}
+
+
+#
+# my $isallzero = allzero($r,$c,$r2,$c2,@m);
+#	Return 1 iff all element of @m[r..r2][c..c2] are zero, 0 otherwise.
+#
+sub allzero
+{
+	my( $r1, $c1, $r2, $c2, @m ) = @_;
+	for( my $r=$r1; $r<=$r2; $r++ )
+	{
+		for( my $c=$c1; $c<=$c2; $c++ )
+		{
+			return 0 unless $m[$r][$c] == 0;
+		}
+	}
+	return 1;
+}
+
+
+#
+# my( $topr, $topc, $nr, $nc ) = maxsubmatrix( @m );
+#	Find the biggest sub matrix of 0s in @m [2-d binary array]
+#	and return the ( $topr, $topc ) top corner of the 0-sub-matrix
+#	and number of rows ($nr) and number of columns ($nc).
+#
+sub maxsubmatrix
+{
+	my( @m ) = @_;
+	my $bestarea = 0;
+	my $best_topr = my $best_topc = 0;
+	my $best_nr = 1; my $best_nc = 1;
+	my $ncols = @{$m[0]};
+
+	for( my $r = 0; $r < @m; $r++ )
+	{
+		for( my $c = 0; $c < $ncols; $c++ )
+		{
+			next unless $m[$r][$c] == 0;
+			for( my $r2 = $r+1; $r2 < @m; $r2++ )
+			{
+				my $nr = 1+$r2-$r;
+				for( my $c2 = $c+1; $c2 < $ncols; $c2++ )
+				{
+					next unless allzero($r,$c,$r2,$c2,@m);
+					my $nc = 1+$c2-$c;
+					my $area = $nr * $nc;
+					if( $area > $bestarea )
+					{
+						$bestarea  = $area;
+						$best_topr = $r;
+						$best_topc = $c;
+						$best_nr   = $nr;
+						$best_nc   = $nc;
+					}
+				}
+			}
+		}
+	}
+	return( $best_topr, $best_topc, $best_nr, $best_nc );
+}
diff --git a/challenge-128/duncan-c-white/perl/ch-2.pl b/challenge-128/duncan-c-white/perl/ch-2.pl
new file mode 100755
index 0000000000..a964a70fed
--- /dev/null
+++ b/challenge-128/duncan-c-white/perl/ch-2.pl
@@ -0,0 +1,112 @@
+#!/usr/bin/perl
+# 
+# Task 2: "Minimum Platforms
+# 
+# You are given two arrays of arrival and departure times of trains at a
+# railway station.
+# 
+# Write a script to find out the minimum number of platforms needed so
+# that no train needs to wait.
+# 
+# Example 1:
+# 
+# Input: @arrivals   = (11:20, 14:30)
+#        @departures = (11:50, 15:00)
+# Output: 1
+# 
+# The 1st arrival of train is at 11:20 and this is the only train at the
+# station, so you need 1 platform.  Before the second arrival at 14:30, the
+# first train left the station at 11:50, so you still need only 1 platform.
+# 
+# Example 2:
+# 
+# Input: @arrivals   = (10:20, 11:00, 11:10, 12:20, 16:20, 19:00)
+#        @departures = (10:30, 13:20, 12:40, 12:50, 20:20, 21:20)
+# Output: 3
+# 
+# Between 12:20 and 12:40, there would be at least 3 trains at the station,
+# so we need minimum 3 platforms."
+# 
+# My notes: nice problem - looks like a tiny discrete event simulation.
+# Build a DIARY: an array of (time, type) pairs - where type == 'A' for
+# an arrival, or type == 'D' for a departure.  Then walk the diary,
+# simulating "train arrival" and "train departure" events.
+# 
+
+use strict;
+use warnings;
+use feature 'say';
+use Function::Parameters;
+use Getopt::Long;
+use Data::Dumper;
+
+my $debug = 0;
+
+die "Usage: platforms [-d|--debug] list(arrive,depart) pairs\n"
+	unless GetOptions( "debug"=>\$debug ) && @ARGV>0;
+my @diary = make_diary( @ARGV );
+#die Dumper \@diary;
+
+# do the simulation - walk over the diary, counting
+# the number of trains at any one point
+
+my $ntrains = 0;
+my $max_ntrains = 0;
+foreach my $dp (@diary)
+{
+	my( $t, $type ) = @$dp;
+	say "debug: t=$t, type=$type" if $debug;
+	if( $type eq "A" )
+	{
+		$ntrains++;
+		if( $ntrains > $max_ntrains )
+		{
+			$max_ntrains = $ntrains;
+			say "debug @ $t: max ntrains=$max_ntrains" if $debug;
+		}
+	} else
+	{
+		$ntrains--;
+	}
+}
+
+say $max_ntrains;
+
+
+
+#
+# my $t = parsetime($hhmm);
+#	Take $hhmm, an hh:mm time string, and compute an integer minutes
+#	date; return that.
+#
+fun parsetime( $hhmm )
+{
+	$hhmm =~ /^(\d\d):(\d\d)$/;
+	return 60*$1 + $2;
+}
+
+
+#
+# my @diary = make_diary( @ad );
+#	Parse and construct a diary (array of [HHMM,TYPE] pairs)
+#	from the arrival,departure pairs in @ad.  Return the diary.
+#
+my %hhmm2t;
+fun make_diary( @ad )
+{
+	my @diary;
+	foreach my $ad (@ad)
+	{
+		my( $a, $d ) = split( /,/, $ad );
+		$hhmm2t{$a} = parsetime($a);
+		$hhmm2t{$d} = parsetime($d);
+		push @diary, [ $a, 'A' ];
+		push @diary, [ $d, 'D' ];
+	}
+	#die Dumper \@diary;
+	#die Dumper \%hhmm2t;
+	return sort { my $at = $a->[0]; my $bt = $b->[0];
+		      #say "debug: at=$at, hm{$at}=$hhmm2t{$at}, bt=$bt, hm{$bt}=$hhmm2t{$bt}";
+		      $hhmm2t{$at} <=> $hhmm2t{$bt} }
+		      @diary;
+}