diff options
5 files changed, 124 insertions, 12 deletions
diff --git a/challenge-118/tyler-wardhaugh/clojure/bb.edn b/challenge-118/tyler-wardhaugh/clojure/bb.edn index d6814eab4a..284d01a194 100644 --- a/challenge-118/tyler-wardhaugh/clojure/bb.edn +++ b/challenge-118/tyler-wardhaugh/clojure/bb.edn @@ -69,7 +69,9 @@ :task (run-task :t2 *command-line-args*)} task-2-bb {:doc "Run Task 2 (via Babashka)" - :task (run-task-bb :t2 *command-line-args*)} + :task (binding [*out* *err*] + (println "error: can't run Task 2 via Babashka because it depends on some incompatible libraries.") + (System/exit 1))} both {:doc "Run both tasks (via clojure)" :task (do @@ -82,8 +84,7 @@ :task (do (println "Task 1:") (run 'task-1-bb) - (println "\nTask 2:") - (run 'task-2-bb))} + (println "\n [Skipping Task 2]"))} } } diff --git a/challenge-118/tyler-wardhaugh/clojure/deps.edn b/challenge-118/tyler-wardhaugh/clojure/deps.edn index 803cdffd33..e3b48fe4eb 100644 --- a/challenge-118/tyler-wardhaugh/clojure/deps.edn +++ b/challenge-118/tyler-wardhaugh/clojure/deps.edn @@ -1,5 +1,9 @@ {:paths ["src" "resources"] - :deps {org.clojure/clojure {:mvn/version "1.10.3"}} + :deps {aysylu/loom {:mvn/version "1.0.2"} + net.mikera/core.matrix {:mvn/version "0.62.0"} + org.clojure/clojure {:mvn/version "1.10.3"} + org.clojure/math.combinatorics {:mvn/version "0.1.6"} + org.clojure/math.numeric-tower {:mvn/version "0.0.4"}} :aliases {:test {:extra-paths ["test"] diff --git a/challenge-118/tyler-wardhaugh/clojure/resources/input.txt b/challenge-118/tyler-wardhaugh/clojure/resources/input.txt new file mode 100644 index 0000000000..50b4ac1b66 --- /dev/null +++ b/challenge-118/tyler-wardhaugh/clojure/resources/input.txt @@ -0,0 +1,8 @@ +N * * * * * * * +* * * * * * * * +* * * * x * * * +* * * * * * * * +* * x * * * * * +* x * * * * * * +x x * * * * * * +* x * * * * * * diff --git a/challenge-118/tyler-wardhaugh/clojure/src/tw/weekly/c118/t2.clj b/challenge-118/tyler-wardhaugh/clojure/src/tw/weekly/c118/t2.clj index a9d990ccd5..bad00754ac 100644 --- a/challenge-118/tyler-wardhaugh/clojure/src/tw/weekly/c118/t2.clj +++ b/challenge-118/tyler-wardhaugh/clojure/src/tw/weekly/c118/t2.clj @@ -1,15 +1,111 @@ (ns tw.weekly.c118.t2 - (:require [clojure.edn :as edn] - [clojure.pprint :refer [cl-format]])) + (:require [clojure.core.matrix :as m] + [clojure.edn :as edn] + [clojure.java.io :as io] + [clojure.math.combinatorics :as combo] + [clojure.pprint :refer [cl-format]] + [clojure.string :as str] + [loom.alg :as la] + [loom.graph :as lg])) ;;; ; Task description for TASK #2 › Adventure of Knight ;;; -(def DEFAULT-INPUT []) +(def DEFAULT-INPUT [(io/resource "input.txt")]) +(def SIZE 8) +(def LEGEND {\* 0, \x 1, \N 2}) + +(defn parse-matrix + "Parse a matrix file and return a matrix" + [matrix-file] + (with-open [in (io/reader matrix-file)] + (let [xf (map (comp + edn/read-string + #(str \[ % \]) + #(str/escape % LEGEND)))] + (into [] xf (line-seq in))))) + +(def NOTATED-BOARD + (->> (for [row (range SIZE 0 -1) + col "abcdefgh"] + (str col row)) + (partition SIZE) + to-array-2d)) + +(defn coord->notation + [[x y]] + (aget NOTATED-BOARD x y)) + +(defn find-indexes-of-vals + [board val] + (let [xf (comp cat (keep identity)) + source (m/emap-indexed (fn [[x y] v] (when (= v val) [x y])) board)] + (sequence xf source))) + +; cf. https://en.wikipedia.org/wiki/Night_Moves_(Bob_Seger_song) +(defn knight-moves + [x y size] + (let [source [[1 2] [-1 2] [2 1] [2 -1]] + xf (comp (map (fn [[dx dy]] [(+ x dx) (+ y dy)])) + (filter (fn [[x y]] (and (<= 0 x (dec size)) + (<= 0 y (dec size))))))] + (sequence xf source))) + +(defn build-knights-graph + "Build a Knight's graph (see https://en.wikipedia.org/wiki/Knight%27s_graph)." + [size] + (let [rng (range size) + source (combo/cartesian-product rng rng) + xf (map (fn [[x y]] [[x y] (knight-moves x y size)]))] + (->> source + (into {} xf) + lg/weighted-graph))) + +(defn build-treasure-graph + [g board start] + (let [treasures (find-indexes-of-vals board (LEGEND \x)) + source (concat + (map (fn [end] [start end]) treasures) + (combo/cartesian-product treasures treasures)) + xf (comp + (filter (fn [[n1 n2]] (not= n1 n2))) + (map (fn [[n1 n2]] [n1 n2 (count (la/dijkstra-path g n1 n2))]))) + paths (sequence xf source)] + (apply lg/weighted-digraph paths))) + +(defn hamiltonian + [g start knights-graph] + (let [nodes (remove #{start} (lg/nodes g)) + source (combo/permutations nodes) + xf (map (fn [arrangement] + (reduce + (fn [[path len] v] + (let [dist (lg/weight g (peek path) v) + pp (la/dijkstra-path knights-graph (peek path) v)] + [(into path (rest pp)) (+ len dist)])) + [[start] 0] + arrangement))) + f (fn [[min-path min-len] [path len]] + (if (< len min-len) + [path len] + [min-path min-len]))] + (-> (transduce xf (completing f) [[] ##Inf] source) + first))) + +(defn adventure-of-knight + [board] + (let [start (first (find-indexes-of-vals board (LEGEND \N))) + knights-graph (build-knights-graph SIZE) + treasure-map (build-treasure-graph knights-graph board start) + min-path (hamiltonian treasure-map start knights-graph)] + (map coord->notation min-path))) (defn -main "Run Task 2 with a given input N, defaulting to the first example from the task description." [& args] - (let [[N] (or (some->> args (map edn/read-string)) DEFAULT-INPUT)] - )) + (let [[FILE] (or (some->> args (map (comp io/file edn/read-string))) + DEFAULT-INPUT) + board (-> FILE parse-matrix m/matrix) + adventure (adventure-of-knight board)] + (cl-format true "~{~a~^, ~}~%" adventure))) diff --git a/challenge-118/tyler-wardhaugh/clojure/test/tw/weekly/c118_test.clj b/challenge-118/tyler-wardhaugh/clojure/test/tw/weekly/c118_test.clj index e827c5a801..6aff519db7 100644 --- a/challenge-118/tyler-wardhaugh/clojure/test/tw/weekly/c118_test.clj +++ b/challenge-118/tyler-wardhaugh/clojure/test/tw/weekly/c118_test.clj @@ -1,7 +1,8 @@ (ns tw.weekly.c118-test - (:require [clojure.test :refer [deftest is testing]] + (:require [clojure.core.matrix :as m] + [clojure.test :refer [deftest is testing]] [tw.weekly.c118.t1 :refer [binary-palindrome]] - #_[tw.weekly.c118.t2 :refer []])) + [tw.weekly.c118.t2 :as t2])) (deftest task-1 (testing "Task 1, Binary Palindrom" @@ -10,4 +11,6 @@ (deftest task-2 (testing "Task 2, Adventure of Knight" - )) + (is (= ["a8" "c7" "e6" "d4" "b3" "c1" "a2" "c3" "b1" "d2" "c4" "b2"] + (-> t2/DEFAULT-INPUT first t2/parse-matrix m/matrix + t2/adventure-of-knight))))) |