diff options
6 files changed, 100 insertions, 3 deletions
diff --git a/challenge-128/tyler-wardhaugh/clojure/deps.edn b/challenge-128/tyler-wardhaugh/clojure/deps.edn index 5b1400b27e..54198fdfe8 100644 --- a/challenge-128/tyler-wardhaugh/clojure/deps.edn +++ b/challenge-128/tyler-wardhaugh/clojure/deps.edn @@ -1,5 +1,6 @@ {:paths ["src" "resources"] - :deps {org.clojure/clojure {:mvn/version "1.10.3"}} + :deps {org.clojure/clojure {:mvn/version "1.10.3"} + net.mikera/core.matrix {:mvn/version "0.62.0"}} :aliases {:test {:extra-paths ["test"] :extra-deps {org.clojure/test.check {:mvn/version "1.1.0"} diff --git a/challenge-128/tyler-wardhaugh/clojure/resources/matrix1.txt b/challenge-128/tyler-wardhaugh/clojure/resources/matrix1.txt new file mode 100644 index 0000000000..109dd5b3d6 --- /dev/null +++ b/challenge-128/tyler-wardhaugh/clojure/resources/matrix1.txt @@ -0,0 +1,3 @@ +[ 1 0 0 0 1 0 ] +[ 1 1 0 0 0 1 ] +[ 1 0 0 0 0 0 ] diff --git a/challenge-128/tyler-wardhaugh/clojure/resources/matrix2.txt b/challenge-128/tyler-wardhaugh/clojure/resources/matrix2.txt new file mode 100644 index 0000000000..3ee68404d8 --- /dev/null +++ b/challenge-128/tyler-wardhaugh/clojure/resources/matrix2.txt @@ -0,0 +1,3 @@ +[ 0 0 1 1 ] +[ 0 0 0 1 ] +[ 0 0 1 0 ] diff --git a/challenge-128/tyler-wardhaugh/clojure/src/tw/weekly/c128/matrix_util.clj b/challenge-128/tyler-wardhaugh/clojure/src/tw/weekly/c128/matrix_util.clj new file mode 100644 index 0000000000..4ef66ead6e --- /dev/null +++ b/challenge-128/tyler-wardhaugh/clojure/src/tw/weekly/c128/matrix_util.clj @@ -0,0 +1,44 @@ +(ns tw.weekly.c128.matrix-util + (:require [clojure.java.io :as io] + [clojure.pprint :as pp] + [clojure.string :as str] + [clojure.core.matrix :as m])) + +(defn parse-matrix-file + "Parse a matrix file and return a matrix" + ([matrix-file] + (parse-matrix-file matrix-file (comp))) + ([matrix-file xf] + (with-open [in (io/reader matrix-file)] + (into [] xf (line-seq in))))) + +(defn extend-matrix + "Surround the matrix in a 'border' of 0s. That is, add rows before the first and after the last rows and add columns before + the first and after the last columns." + [mat] + (let [n (m/dimension-count mat 1) + blank-row (vec (repeat (+ n 2) 0)) + step-1 (reduce (fn [mat v] (conj mat (vec (concat [0] v [0])))) [blank-row] mat)] + (conj step-1 blank-row))) + +(defn rotate-matrix + "Rotate a matrix counterclockwise" + [mat] + (-> mat m/transpose reverse)) + +(defn print-matrix + ([mat] + (print-matrix mat true)) + ([mat stream] + (pp/cl-format stream "~{[ ~{~a~^ ~} ]~%~}" mat))) + +(defn pprint-matrix + "Pretty print a matrix" + [mat] + (let [ks (range (m/dimension-count mat 1)) + tbl (with-out-str + (pp/print-table ks (map (partial zipmap ks) mat)))] + (-> tbl + (str/split #"\n") + (->> (drop 3) + (run! println))))) diff --git a/challenge-128/tyler-wardhaugh/clojure/src/tw/weekly/c128/t1.clj b/challenge-128/tyler-wardhaugh/clojure/src/tw/weekly/c128/t1.clj new file mode 100644 index 0000000000..b535021f51 --- /dev/null +++ b/challenge-128/tyler-wardhaugh/clojure/src/tw/weekly/c128/t1.clj @@ -0,0 +1,40 @@ +(ns tw.weekly.c128.t1 + (:require [clojure.edn :as edn] + [clojure.java.io :as io] + [clojure.string :as str] + [clojure.pprint :refer [cl-format]] + [clojure.core.matrix :as m] + [tw.weekly.c128.matrix-util :as mu])) + +;;; +; Task description for TASK #1 › Maximum Sub-Matrix +;;; +(def DEFAULT-INPUT [(io/resource "matrix1.txt")]) + +(defn parse + [f] + (->> (mu/parse-matrix-file f (map edn/read-string)) + (m/array :ndarry))) + +(defn find-max-submatrix + [mat] + (let [source (m/index-seq mat) + [m n] (m/shape mat) + gen-subm (fn [[i j]] + (when (zero? (m/mget mat i j)) + (for [x (range i (inc m)) + y (range j (inc n)) + :let [subm (m/submatrix mat i (- x i) j (- y j))] + :when (m/zero-matrix? subm)] + (m/shape subm)))) + xf (comp (map gen-subm) (filter seq) cat) + f (completing (fn [w v] (max-key (partial apply *) w v)))] + (transduce xf f [0 0] source))) + +(defn -main + "Run Task 1 with a given input M, defaulting to the first example from the + task description." + [& args] + (let [[F] (or (some->> args (map (comp io/file edn/read-string))) DEFAULT-INPUT) + [m n] (-> F parse find-max-submatrix)] + (-> (m/zero-matrix :ndarry m n) (m/fill 0) mu/print-matrix))) diff --git a/challenge-128/tyler-wardhaugh/clojure/test/tw/weekly/c128_test.clj b/challenge-128/tyler-wardhaugh/clojure/test/tw/weekly/c128_test.clj index f89be58ecd..940922fab4 100644 --- a/challenge-128/tyler-wardhaugh/clojure/test/tw/weekly/c128_test.clj +++ b/challenge-128/tyler-wardhaugh/clojure/test/tw/weekly/c128_test.clj @@ -1,11 +1,17 @@ (ns tw.weekly.c128-test (:require [clojure.test :refer [deftest is testing]] - #_[tw.weekly.c128.t1 :refer []] + [clojure.java.io :as io] + [tw.weekly.c128.t1 :as t1] #_[tw.weekly.c128.t2 :as t2])) +(defn solve-t1 + [f] + (-> f io/resource t1/parse t1/find-max-submatrix)) + (deftest task-1 (testing "Task 1, Maximum Sub-Matrix" - )) + (is (= [2 3] (solve-t1 "matrix1.txt"))) + (is (= [3 2] (solve-t1 "matrix2.txt"))))) (deftest task-2 (testing "Task 2, Minimum Platforms" |