Node solution for week 87/part 2.

1 files changed, 108 insertions, 0 deletions

diff --git a/challenge-087/abigail/node/ch-2.js b/challenge-087/abigail/node/ch-2.js
new file mode 100644
index 0000000000..24c6c98040
--- /dev/null
+++ b/challenge-087/abigail/node/ch-2.js
@@ -0,0 +1,108 @@
+//
+// Challenge
+//
+// You are given matrix m x n with 0 and 1.
+//
+// Write a script to find the largest rectangle containing only 1.
+// Print 0 if none found.
+//
+
+//
+// For notes, see the perl solution: ../perl/ch-1.pl
+//
+
+//
+// A naive implementation would be a quartic algorithm. We can do better,
+// using a cubic algorithm.
+//
+// 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.
+//
+// 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 
+// cell (x, y + k) in the scan, we keep track of the minimum value in
+// points (x, y + m), 0 <= m <= k, as calculated in the step above.
+// Let this value be p. Then the maximum sized rectangle we can make
+// with the points (x, y) and (x, y + k) as (top) vertices of that
+// rectangle is (k + 1) x p.
+//
+
+
+//
+// Read STDIN. Split on newlines, then on whitespace, and turn the results
+// into numbers.
+//
+let matrix = require      ("fs")
+           . readFileSync (0)                 // Read all.
+           . toString     ()                  // Turn it into a string.
+           . split        ("\n")              // Split on newlines.
+           . filter       (_ => _ . length)   // Filter empty lines.
+           . map          (_ => _ . split (" ")       // Split lines on spaces
+                                  . map   (_ => +_))  // Numify.
+;
+
+//
+// Check whether all rows are the same size
+//
+for (let x = 1; x < matrix . length; x ++) {
+    if (matrix [x] . length != matrix [0] . length) {
+        process . stderr . write ("Not all rows are equal!\n");
+        process . exit (1);
+    }
+}
+
+//
+// Maps the 1s in the matrix to the number of consecutive 1s below
+// it (including this 1 itself).
+//
+for (let x = matrix . length - 2; x >= 0; x --) {
+    for (let y = 0; y < matrix [x] . length; y ++) {
+        matrix [x] [y] = matrix [x]     [y] *
+                        (matrix [x + 1] [y] + 1);
+    }
+}
+
+
+//
+// Iterate over all element of the matrix. For each element which
+// isn't 0, scan to the right, keeping track of minimum sequence
+// downward. For each point in the scan, find the largest rectangle
+// which can be made with these points as corner points.
+//
+// Remember the best one found.
+//
+let best = [0, 0];
+for (let x = 0; x < matrix . length; x ++) {
+    for (let y = 0; y < matrix [x] . length; y ++) {
+        if (matrix [x] [y] == 0) {
+            continue;
+        }
+        let min_depth = matrix [x] [y];
+        if (min_depth > best [0] * best [1]) {
+            best = [min_depth, 1];
+        }
+        for (w = 1; y + w < matrix [x] . length &&
+                    matrix [x] [y + w] > 0; w ++) {
+            if (matrix [x] [y + w] < min_depth) {
+                min_depth = matrix [x] [y + w];
+            }
+            if (min_depth * (w + 1) > best [0] * best [1]) {
+                best = [min_depth, w + 1];
+            }
+        }
+    }
+}
+
+
+//
+// Print solution. 
+//
+let output = "0";
+if (best [0] * best [1] > 1) {
+    let row = [... Array (best [1]) . keys ()] . map (_ => 1)   . join (" ");
+    output  = [... Array (best [0]) . keys ()] . map (_ => row) . join ("\n");
+}
+
+console . log (output);
+