Merge pull request #2813 from tylerw/tw/challenge-087

Challenge 087 in Clojure

11 files changed, 181 insertions, 24 deletions

diff --git a/challenge-087/tyler-wardhaugh/clojure/README.md b/challenge-087/tyler-wardhaugh/clojure/README.md
index ada4806466..7a610a7578 100644
--- a/challenge-087/tyler-wardhaugh/clojure/README.md
+++ b/challenge-087/tyler-wardhaugh/clojure/README.md
@@ -1,13 +1,13 @@
-# tw.weekly.c86
+# tw.weekly.c87
 
 
-The Weekly Challenge - #086 - Tyler Wardhaugh
+The Weekly Challenge - #087 - Tyler Wardhaugh
 
 ## Usage
 
 Run the project directly (shows default output from both tasks):
 
-    $ clojure -M -m tw.weekly.c86.core
+    $ clojure -M -m tw.weekly.c87.core
 
 Run the project's tests (which are samples from the task descriptions):
 
@@ -15,11 +15,11 @@ Run the project's tests (which are samples from the task descriptions):
 
 Run Task #1 with input
 
-    $ clojure -M -m tw.weekly.c86.t1 A N1 N2 N3...
+    $ clojure -M -m tw.weekly.c87.t1 N1 N2 N3...
 
 Run Task #2 with input:
 
-    $ clojure -M -m tw.weekly.c86.t2 SUDOKO-FILE 
+    $ clojure -M -m tw.weekly.c87.t2 MATRIX-FILE
 
 ## Project Template
 
diff --git a/challenge-087/tyler-wardhaugh/clojure/deps.edn b/challenge-087/tyler-wardhaugh/clojure/deps.edn
index 18ea25ec63..096b24ac34 100644
--- a/challenge-087/tyler-wardhaugh/clojure/deps.edn
+++ b/challenge-087/tyler-wardhaugh/clojure/deps.edn
@@ -1,6 +1,5 @@
 {:paths ["src" "resources"]
  :deps {org.clojure/clojure {:mvn/version "1.10.1"}
-        org.clojure/core.logic {:mvn/version "1.0.0"}
         net.mikera/core.matrix {:mvn/version "0.62.0"}}
  :aliases
  {:test {:extra-paths ["test"]
@@ -12,5 +11,5 @@
    :main-opts ["-m" "cognitect.test-runner"
                "-d" "test"]}
   :uberjar {:extra-deps {seancorfield/depstar {:mvn/version "1.0.94"}}
-            :main-opts ["-m" "hf.depstar.uberjar" "tw.weekly.c86.jar"
-                        "-C" "-m" "tw.weekly.c86"]}}}
+            :main-opts ["-m" "hf.depstar.uberjar" "tw.weekly.c87.jar"
+                        "-C" "-m" "tw.weekly.c87"]}}}
diff --git a/challenge-087/tyler-wardhaugh/clojure/pom.xml b/challenge-087/tyler-wardhaugh/clojure/pom.xml
index cc507f3605..2eeb46cb8c 100644
--- a/challenge-087/tyler-wardhaugh/clojure/pom.xml
+++ b/challenge-087/tyler-wardhaugh/clojure/pom.xml
@@ -2,11 +2,11 @@
 <project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
   <modelVersion>4.0.0</modelVersion>
   <groupId>tw.weekly</groupId>
-  <artifactId>tw.weekly.c86</artifactId>
+  <artifactId>tw.weekly.c87</artifactId>
   <version>0.1.0-SNAPSHOT</version>
-  <name>tw.weekly.c86</name>
-  <description>Challenge #086</description>
-  <url>https://github.com/tw.weekly/tw.weekly.c86</url>
+  <name>tw.weekly.c87</name>
+  <description>Challenge #087</description>
+  <url>https://github.com/tw.weekly/tw.weekly.c87</url>
   <licenses>
     <license>
       <name>Eclipse Public License</name>
@@ -19,9 +19,9 @@
     </developer>
   </developers>
   <scm>
-    <url>https://github.com/tw.weekly/tw.weekly.c86</url>
-    <connection>scm:git:git://github.com/tw.weekly/tw.weekly.c86.git</connection>
-    <developerConnection>scm:git:ssh://git@github.com/tw.weekly/tw.weekly.c86.git</developerConnection>
+    <url>https://github.com/tw.weekly/tw.weekly.c87</url>
+    <connection>scm:git:git://github.com/tw.weekly/tw.weekly.c87.git</connection>
+    <developerConnection>scm:git:ssh://git@github.com/tw.weekly/tw.weekly.c87.git</developerConnection>
     <tag>HEAD</tag>
   </scm>
   <dependencies>
@@ -31,11 +31,6 @@
       <version>1.10.1</version>
     </dependency>
     <dependency>
-      <groupId>org.clojure</groupId>
-      <artifactId>core.logic</artifactId>
-      <version>1.0.0</version>
-    </dependency>
-    <dependency>
       <groupId>net.mikera</groupId>
       <artifactId>core.matrix</artifactId>
       <version>0.62.0</version>
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/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)))))
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
new file mode 100644
index 0000000000..1bc995e6c6
--- /dev/null
+++ b/challenge-087/tyler-wardhaugh/clojure/test/tw/weekly/c87_test.clj
@@ -0,0 +1,21 @@
+(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.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")))))
diff --git a/challenge-087/tyler-wardhaugh/lua/README.md b/challenge-087/tyler-wardhaugh/lua/README.md
index ad70c646d1..62141395f2 100644
--- a/challenge-087/tyler-wardhaugh/lua/README.md
+++ b/challenge-087/tyler-wardhaugh/lua/README.md
@@ -1,17 +1,17 @@
 
 # The Weekly Challenge
 
-The Weekly Challenge - #086 - Tyler Wardhaugh
+The Weekly Challenge - #087 - Tyler Wardhaugh
 
 ## Usage
 
 Run Task 1:
 
-    $ ./run.lua ch-1 A N1 N2 N3...
+    $ ./run.lua ch-1 N1 N2 N3...
 
 Run Task 2:
 
-    $ ./run.lua ch-2 SUDOKO-FILE
+    $ ./run.lua ch-2 MATRIX-FILE
 
 Run the project's tests (all the samples from the task descriptions plus some others):
 
@@ -21,4 +21,3 @@ Run the project's tests (all the samples from the task descriptions plus some ot
 *   [Lua](https://www.lua.org/) 5.3
 *   [LuaRocks](https://luarocks.org/)
 *   [busted](https://olivinelabs.com/busted/) (a unit testing framework)
-*   [Moses](https://yonaba.github.io/Moses/) (a Lua utility-belt library)