3 files changed, 129 insertions, 0 deletions
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/t1.clj b/challenge-087/tyler-wardhaugh/clojure/src/tw/weekly/c87/t1.clj
new file mode 100644
index 0000000000..e2f550af08
--- /dev/null
+++ b/challenge-087/tyler-wardhaugh/clojure/src/tw/weekly/c87/t1.clj
@@ -0,0 +1,32 @@
+(ns tw.weekly.c87.t1
+  (:require [clojure.edn :as edn])
+  (:require [clojure.set :as set])
+  (:require [clojure.pprint :refer [cl-format]]))
+
+;;;
+; Task description for TASK #1 › Longest Consecutive Sequence
+;;;
+
+(defn find-lcs
+  "Find the longest consecutive sequence (with 2 or more elements)"
+  [coll]
+  (loop [s (set coll)
+         lcs-diff 0
+         lcs [0 0]]
+    (if (empty? s)
+      lcs
+      (let [elem (first s)
+            low (last (take-while s (iterate dec elem)))
+            high (last (take-while s (iterate inc elem)))
+            diff (- high low)]
+        (if (and (not (zero? diff)) (> diff lcs-diff))
+          (recur (set/difference s (set (range low (inc high)))) diff [low high])
+          (recur (set/difference s #{elem}) lcs-diff lcs))))))
+
+(defn -main
+  "Run Task 1 with a list of numbers N, defaulting to the
+  first example given in the task description."
+  [& args]
+  (let [N (or (some->> args (map edn/read-string)) [100 4 50 3 2])
+       [low high] (find-lcs N)]
+    (cl-format true "~{~a~^, ~}" (range low (inc high)))))
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)))))