Ch87 (Clojure): Task 2

6 files changed, 124 insertions, 2 deletions

diff --git a/challenge-087/tyler-wardhaugh/clojure/resources/matrix-1 b/challenge-087/tyler-wardhaugh/clojure/resources/matrix-1
new file mode 100644
index 0000000000..14c0fc6cf9
--- /dev/null
+++ b/challenge-087/tyler-wardhaugh/clojure/resources/matrix-1
@@ -0,0 +1,5 @@
+[ 0 0 0 1 0 0 ]
+[ 1 1 1 0 0 0 ]
+[ 0 0 1 0 0 1 ]
+[ 1 1 1 1 1 0 ]
+[ 1 1 1 1 1 0 ]
diff --git a/challenge-087/tyler-wardhaugh/clojure/resources/matrix-2 b/challenge-087/tyler-wardhaugh/clojure/resources/matrix-2
new file mode 100644
index 0000000000..34863d95ed
--- /dev/null
+++ b/challenge-087/tyler-wardhaugh/clojure/resources/matrix-2
@@ -0,0 +1,4 @@
+[ 1 0 1 0 1 0 ]
+[ 0 1 0 1 0 1 ]
+[ 1 0 1 0 1 0 ]
+[ 0 1 0 1 0 1 ]
diff --git a/challenge-087/tyler-wardhaugh/clojure/resources/matrix-3 b/challenge-087/tyler-wardhaugh/clojure/resources/matrix-3
new file mode 100644
index 0000000000..b34017aebc
--- /dev/null
+++ b/challenge-087/tyler-wardhaugh/clojure/resources/matrix-3
@@ -0,0 +1,5 @@
+[ 0 0 0 1 1 1 ]
+[ 1 1 1 1 1 1 ]
+[ 0 0 1 0 0 1 ]
+[ 0 0 1 1 1 1 ]
+[ 0 0 1 1 1 1 ]
diff --git a/challenge-087/tyler-wardhaugh/clojure/src/tw/weekly/c87/core.clj b/challenge-087/tyler-wardhaugh/clojure/src/tw/weekly/c87/core.clj
new file mode 100644
index 0000000000..a27a2b4dbd
--- /dev/null
+++ b/challenge-087/tyler-wardhaugh/clojure/src/tw/weekly/c87/core.clj
@@ -0,0 +1,12 @@
+(ns tw.weekly.c87.core
+  (:require [tw.weekly.c87.t1 :as t1])
+  (:require [tw.weekly.c87.t2 :as t2])
+  (:gen-class))
+
+(defn -main
+  "Run all tasks"
+  [& _]
+  (println "Task #1:")
+  (t1/-main)
+  (println "\nTask #2:")
+  (t2/-main))
diff --git a/challenge-087/tyler-wardhaugh/clojure/src/tw/weekly/c87/t2.clj b/challenge-087/tyler-wardhaugh/clojure/src/tw/weekly/c87/t2.clj
new file mode 100644
index 0000000000..f10eb56aef
--- /dev/null
+++ b/challenge-087/tyler-wardhaugh/clojure/src/tw/weekly/c87/t2.clj
@@ -0,0 +1,85 @@
+(ns tw.weekly.c87.t2
+  (:require [clojure.edn :as edn])
+  (:require [clojure.java.io :as io])
+  (:require [clojure.pprint :refer [cl-format]])
+  (:require [clojure.core.matrix :as m]))
+
+;;; algorithm sources:
+;     GeeksforGeeks, https://www.geeksforgeeks.org/maximum-size-rectangle-binary-sub-matrix-1s/
+;     Abigail, https://programmingblog702692439.wordpress.com/2020/11/20/perl-weekly-challenge-87-part-2/
+
+
+;;;
+; Task description for TASK #2 › Largest Rectangle
+;;;
+
+(defn parse-matrix-file
+  "Parse a matrix file and return a matrix"
+  [matrix-file]
+  (with-open [in (io/reader matrix-file)]
+    (-> (slurp in)
+        (as-> x (str \[ x \]))
+        edn/read-string
+        m/matrix)))
+
+(defn populate-sum-matrix
+  "Create a matrix where each cell represents a sum of continuous 1s below it."
+  [matrix]
+  (let [sums (-> matrix reverse m/mutable)
+        rows (m/rows sums)]
+    (loop [prev (first rows)
+           [curr & remaining] (rest rows)]
+      (if curr
+        (do 
+          (m/emap-indexed! (fn [[y] v] (* v (inc (nth prev y)))) curr)
+          (recur curr remaining))
+        (reverse sums)))))
+
+(defn non-zero-coords-and-vals
+  "Generate a seq of coordinates and values in the form [x y value] for every
+  non-zero value in the given matrix"
+  [matrix]
+  (->> (m/coerce [] matrix)
+       (m/emap-indexed (fn [[x y] v] (when (pos? v) (vector x y v))))
+       (apply concat)
+       (keep identity)))
+
+(def area ^{:doc "Calculate the area of a rectangle"} (partial apply *))
+
+(defn best-rect-helper
+  "A helper function to find the best (largest) rectangle"
+  [[s n best] [x y value]]
+  (let [initial [value (if (< (area best) value) [value 1] best)]
+        f (fn [[min-depth best] w]
+            (if (and (< (+ y w) n) (pos? (m/mget s x (+ y w))))
+              (let [md-cand (m/mget s x (+ y w))]
+                (vector (min md-cand min-depth)
+                        (max-key area [min-depth (inc w)] best)))
+              (reduced [min-depth best])))]
+    [s n (->> (iterate inc 1) (reduce f initial) second)]))
+
+(defn find-largest-rectangle
+  "Find the largest rectangle in the given matrix"
+  [matrix]
+  (let [too-wide (apply < (m/shape matrix))
+        sums (populate-sum-matrix (if too-wide (m/transpose matrix) matrix))
+        largest (->> (non-zero-coords-and-vals sums)
+                     (reduce best-rect-helper [sums (m/dimension-count sums 1) [0 0]])
+                     last)]
+    (if too-wide (reverse largest) largest)))
+
+(defn flesh-out
+  "Expand [m n] to a matrix of 1s"
+  [[m n]]
+  (m/to-nested-vectors (m/assign (m/zero-matrix m n) 1)))
+
+(defn -main
+  "Run Task 2 with a given file containing a matrix, defaulting
+  to the example given in the task description."
+  [& args]
+  (let [matrix-file (or (some-> args first io/file) (io/resource "matrix-1"))
+        matrix (parse-matrix-file matrix-file)
+        solution (find-largest-rectangle matrix)]
+    (if (<= (area solution) 1)
+      (println 0)
+      (cl-format true "~{~a~^~%~}~%" (flesh-out solution)))))
diff --git a/challenge-087/tyler-wardhaugh/clojure/test/tw/weekly/c87_test.clj b/challenge-087/tyler-wardhaugh/clojure/test/tw/weekly/c87_test.clj
index d99a5699c9..1bc995e6c6 100644
--- a/challenge-087/tyler-wardhaugh/clojure/test/tw/weekly/c87_test.clj
+++ b/challenge-087/tyler-wardhaugh/clojure/test/tw/weekly/c87_test.clj
@@ -1,10 +1,21 @@
-(ns tw.weekly.c86-test
+(ns tw.weekly.c87-test
   (:require [clojure.test :refer [deftest is testing]]
             [clojure.java.io :as io]
-            [tw.weekly.c87.t1 :refer [find-lcs]]))
+            [tw.weekly.c87.t1 :refer [find-lcs]]
+            [tw.weekly.c87.t2 :refer [find-largest-rectangle parse-matrix-file]]))
 
 (deftest task-1
   (testing "Task 1 Longest Consecutive Sequence"
     (is (= [2 4] (find-lcs [100 4 50 3 2])))
     (is (= [0 0] (find-lcs [20 30 10 40 50])))
     (is (= [9 11] (find-lcs [20 19 9 11 10])))))
+
+(def task-2-helper
+  ^{:doc "Solve Task 2, returning a vector of the largest (height, width)"}
+  (comp find-largest-rectangle parse-matrix-file io/resource))
+
+(deftest task-2
+  (testing "Task 2 Largest Rectangle"
+    (is (= [2 5] (task-2-helper "matrix-1")))
+    (is (= [1 1] (task-2-helper "matrix-2")))
+    (is (= [2 4] (task-2-helper "matrix-3")))))