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

1 files changed, 52 insertions, 5 deletions

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];
 }