Transpose the matrix if it's wider than it's high.

2 files changed, 103 insertions, 10 deletions

diff --git a/challenge-087/abigail/node/ch-2.js b/challenge-087/abigail/node/ch-2.js
index 24c6c98040..5dedf7c4ce 100644
--- a/challenge-087/abigail/node/ch-2.js
+++ b/challenge-087/abigail/node/ch-2.js
@@ -12,12 +12,42 @@
 //
 
 //
-// A naive implementation would be a quartic algorithm. We can do better,
-// using a cubic algorithm.
+// A naive implementation would be a for each pair of points see whether
+// there's a rectangle with 1s, with the pair of points opposite vertices
+// of the array.
 //
-// First, we replace every 1 in the matrix with the number of from the
-// current position to the first 0 below it. We can do this in a single
-// pass, working bottom to top.
+// If done correctly, that leads to an Omega (l^2 * m^2) algorithm,
+// if the size of the input is an l x m matrix. So, Omega (N^2)
+// where N = l * m.
+//
+// But we can do better. We can use an algorithm which runs in
+// O (l * m * min (l, m)) time, or O (N sqrt (N)) time, since
+// min (l, m) <= sqrt (N).
+//
+// Assume the matrix is not wider than it is high (otherwise, first
+// transpose the matrix -- which can be done in O (l * m) time).
+//
+// First, we replace every 1 in the matrix with how many 1's (including
+// the 1 in the current position) it takes the hit the first 0 below it.
+// We can do this in a single pass, working bottom to top.
+//
+// So, the matrix 
+//
+//          0 1 0 1 1
+//          0 1 0 1 1
+//          0 1 1 1 1
+//          1 0 0 1 1
+//          0 0 0 1 1
+//          0 0 1 0 0
+//
+// becomes
+//
+//          0 3 0 5 5
+//          0 2 0 4 4
+//          0 1 1 3 3
+//          1 0 0 2 2
+//          0 0 0 1 1
+//          0 0 1 0 0
 //
 // Then, for each cell (x, y) in the matrix, we scan to the right (in the
 // y direction), until we hit a zero (or the end of the row). For each 
@@ -52,6 +82,19 @@ for (let x = 1; x < matrix . length; x ++) {
     }
 }
 
+let X = matrix     . length;
+let Y = matrix [0] . length;
+
+//
+// Transpose if the matrix is wider than it is high.
+//
+let transposed = 0;
+if (X < Y) {
+    matrix = matrix [0] . map ((col, i) => matrix . map (row => row [i]));
+    [X, Y] = [Y, X];
+    transposed = 1;
+}
+
 //
 // Maps the 1s in the matrix to the number of consecutive 1s below
 // it (including this 1 itself).
@@ -100,6 +143,9 @@ for (let x = 0; x < matrix . length; x ++) {
 //
 let output = "0";
 if (best [0] * best [1] > 1) {
+    if (transposed) {
+        best = [best [1], best [0]];
+    }
     let row = [... Array (best [1]) . keys ()] . map (_ => 1)   . join (" ");
     output  = [... Array (best [0]) . keys ()] . map (_ => row) . join ("\n");
 }
diff --git a/challenge-087/abigail/perl/ch-2.pl b/challenge-087/abigail/perl/ch-2.pl
index b2bf30348d..8cdb86227e 100644
--- a/challenge-087/abigail/perl/ch-2.pl
+++ b/challenge-087/abigail/perl/ch-2.pl
@@ -47,12 +47,42 @@ use experimental 'lexical_subs';
 #
 
 #
-# A naive implementation would be a quartic algorithm. We can do better,
-# using a cubic algorithm.
+# A naive implementation would be a for each pair of points see whether
+# there's a rectangle with 1s, with the pair of points opposite vertices
+# of the array.
 #
-# First, we replace every 1 in the matrix with the number of from the
-# current position to the first 0 below it. We can do this in a single
-# pass, working bottom to top.
+# If done correctly, that leads to an Omega (l^2 * m^2) algorithm,
+# if the size of the input is an l x m matrix. So, Omega (N^2)
+# where N = l * m.
+#
+# But we can do better. We can use an algorithm which runs in
+# O (l * m * min (l, m)) time, or O (N sqrt (N)) time, since
+# min (l, m) <= sqrt (N).
+#
+# Assume the matrix is not wider than it is high (otherwise, first
+# transpose the matrix -- which can be done in O (l * m) time).
+#
+# First, we replace every 1 in the matrix with how many 1's (including
+# the 1 in the current position) it takes the hit the first 0 below it.
+# We can do this in a single pass, working bottom to top.
+#
+# So, the matrix 
+#
+#          0 1 0 1 1
+#          0 1 0 1 1
+#          0 1 1 1 1
+#          1 0 0 1 1
+#          0 0 0 1 1
+#          0 0 1 0 0
+#
+# becomes
+#
+#          0 3 0 5 5
+#          0 2 0 4 4
+#          0 1 1 3 3
+#          1 0 0 2 2
+#          0 0 0 1 1
+#          0 0 1 0 0
 #
 # Then, for each cell (x, y) in the matrix, we scan to the right (in the
 # y direction), until we hit a zero (or the end of the row). For each 
@@ -77,6 +107,22 @@ my $X =   @matrix;
 my $Y = @{$matrix [0]};
 
 #
+# Transpose if necessary
+#
+my $transpose;
+if ($X < $Y) {
+    my @matrix_t;
+    for (my $x = 0; $x < $X; $x ++) {
+        for (my $y = 0; $y < $Y; $y ++) {
+            $matrix_t [$y] [$x] = $matrix [$x] [$y];
+        }
+    }
+    @matrix = @matrix_t;
+   ($X, $Y) = ($Y, $X);
+    $transpose = 1;
+}
+
+#
 # Fill the matrix with runs.
 #
 for (my $x = $X - 2; $x >= 0; $x --) {
@@ -113,6 +159,7 @@ if ($$best [0] * $$best [1] <= 1) {
     say 0;
 }
 else {
+    $best = [$$best [1], $$best [0]] if $transpose;
     say join " ", (1) x $$best [1] for 1 .. $$best [0];
 }