From bf55bacf05338e510937a11abd0850b00bfa0307 Mon Sep 17 00:00:00 2001 From: Tyler Wardhaugh Date: Thu, 19 Nov 2020 22:39:46 -0800 Subject: Ch87: prep for challenge --- challenge-087/tyler-wardhaugh/clojure/README.md | 10 +++++----- challenge-087/tyler-wardhaugh/clojure/deps.edn | 5 ++--- challenge-087/tyler-wardhaugh/clojure/pom.xml | 19 +++++++------------ challenge-087/tyler-wardhaugh/lua/README.md | 7 +++---- 4 files changed, 17 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 @@ 4.0.0 tw.weekly - tw.weekly.c86 + tw.weekly.c87 0.1.0-SNAPSHOT - tw.weekly.c86 - Challenge #086 - https://github.com/tw.weekly/tw.weekly.c86 + tw.weekly.c87 + Challenge #087 + https://github.com/tw.weekly/tw.weekly.c87 Eclipse Public License @@ -19,9 +19,9 @@ - https://github.com/tw.weekly/tw.weekly.c86 - scm:git:git://github.com/tw.weekly/tw.weekly.c86.git - scm:git:ssh://git@github.com/tw.weekly/tw.weekly.c86.git + https://github.com/tw.weekly/tw.weekly.c87 + scm:git:git://github.com/tw.weekly/tw.weekly.c87.git + scm:git:ssh://git@github.com/tw.weekly/tw.weekly.c87.git HEAD @@ -30,11 +30,6 @@ clojure 1.10.1 - - org.clojure - core.logic - 1.0.0 - net.mikera core.matrix 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) -- cgit From 982caeafb3eaa7d4b19a061acfd134235d72785f Mon Sep 17 00:00:00 2001 From: Tyler Wardhaugh Date: Fri, 20 Nov 2020 00:32:35 -0800 Subject: Ch87 (Clojure): Task 1 --- .../clojure/src/tw/weekly/c87/t1.clj | 32 ++++++++++++++++++++++ .../clojure/test/tw/weekly/c87_test.clj | 10 +++++++ 2 files changed, 42 insertions(+) create mode 100644 challenge-087/tyler-wardhaugh/clojure/src/tw/weekly/c87/t1.clj create mode 100644 challenge-087/tyler-wardhaugh/clojure/test/tw/weekly/c87_test.clj 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/test/tw/weekly/c87_test.clj b/challenge-087/tyler-wardhaugh/clojure/test/tw/weekly/c87_test.clj new file mode 100644 index 0000000000..d99a5699c9 --- /dev/null +++ b/challenge-087/tyler-wardhaugh/clojure/test/tw/weekly/c87_test.clj @@ -0,0 +1,10 @@ +(ns tw.weekly.c86-test + (:require [clojure.test :refer [deftest is testing]] + [clojure.java.io :as io] + [tw.weekly.c87.t1 :refer [find-lcs]])) + +(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]))))) -- cgit From 597b554bb290608a656e583ee502adbb05e6fb25 Mon Sep 17 00:00:00 2001 From: Tyler Wardhaugh Date: Fri, 20 Nov 2020 15:20:30 -0800 Subject: Ch87 (Clojure): Task 2 --- .../tyler-wardhaugh/clojure/resources/matrix-1 | 5 ++ .../tyler-wardhaugh/clojure/resources/matrix-2 | 4 + .../tyler-wardhaugh/clojure/resources/matrix-3 | 5 ++ .../clojure/src/tw/weekly/c87/core.clj | 12 +++ .../clojure/src/tw/weekly/c87/t2.clj | 85 ++++++++++++++++++++++ .../clojure/test/tw/weekly/c87_test.clj | 15 +++- 6 files changed, 124 insertions(+), 2 deletions(-) create mode 100644 challenge-087/tyler-wardhaugh/clojure/resources/matrix-1 create mode 100644 challenge-087/tyler-wardhaugh/clojure/resources/matrix-2 create mode 100644 challenge-087/tyler-wardhaugh/clojure/resources/matrix-3 create mode 100644 challenge-087/tyler-wardhaugh/clojure/src/tw/weekly/c87/core.clj create mode 100644 challenge-087/tyler-wardhaugh/clojure/src/tw/weekly/c87/t2.clj 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"))))) -- cgit