Merge pull request #4347 from tylerw/tw/challenge-118

Challenge 118

9 files changed, 194 insertions, 24 deletions

diff --git a/challenge-118/tyler-wardhaugh/clojure/README.md b/challenge-118/tyler-wardhaugh/clojure/README.md
index 46dde45ce4..de2edc3f59 100644
--- a/challenge-118/tyler-wardhaugh/clojure/README.md
+++ b/challenge-118/tyler-wardhaugh/clojure/README.md
@@ -1,7 +1,7 @@
-# tw.weekly.c117
+# tw.weekly.c118
 
 
-The Weekly Challenge - #117 - Tyler Wardhaugh
+The Weekly Challenge - #118 - Tyler Wardhaugh
 
 ## Usage
 
@@ -9,7 +9,7 @@ Clojure ([installation instructions](https://clojure.org/guides/getting_started#
 
 Run the project directly (shows default output from both tasks):
 
-    $ clojure -M -m tw.weekly.c117.core
+    $ clojure -M -m tw.weekly.c118.core
     # ... or ...
     $ bb run both
 
@@ -21,15 +21,15 @@ Run the project's tests (which are samples from the task descriptions):
 
 Run Task #1 with input
 
-    $ clojure -M -m tw.weekly.c117.t1 FILE
+    $ clojure -M -m tw.weekly.c118.t1 N
     # ... or ...
-    $ bb run task-1 FILE
+    $ bb run task-1 N
 
 Run Task #2 with input:
 
-    $ clojure -M -m tw.weekly.c117.t2 N
+    $ clojure -M -m tw.weekly.c118.t2
     # ... or ...
-    $ bb run task-2 N
+    $ bb run task-2
 
 ## Project Template
 
diff --git a/challenge-118/tyler-wardhaugh/clojure/bb.edn b/challenge-118/tyler-wardhaugh/clojure/bb.edn
index 0409645368..284d01a194 100644
--- a/challenge-118/tyler-wardhaugh/clojure/bb.edn
+++ b/challenge-118/tyler-wardhaugh/clojure/bb.edn
@@ -63,15 +63,15 @@
           :task (run-task :t1 *command-line-args*)}
 
   task-1-bb {:doc "Run Task 1 (via Babashka)"
-             :task (binding [*out* *err*]
-                      (println "error: can't run Task 1 via Babashka because it depends on an incompatible library.")
-                      (System/exit 1))}
+             :task (run-task-bb :t1 *command-line-args*)}
 
   task-2 {:doc "Run Task 2 (via clojure)"
           :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
@@ -84,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 b971f3081f..e3b48fe4eb 100644
--- a/challenge-118/tyler-wardhaugh/clojure/deps.edn
+++ b/challenge-118/tyler-wardhaugh/clojure/deps.edn
@@ -1,6 +1,9 @@
 {:paths ["src" "resources"]
- :deps {org.clojure/clojure {:mvn/version "1.10.3"}
-        net.cgrand/xforms {:mvn/version "0.19.2"}}
+ :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/pom.xml b/challenge-118/tyler-wardhaugh/clojure/pom.xml
index ed74b5497a..ca25679f9e 100644
--- a/challenge-118/tyler-wardhaugh/clojure/pom.xml
+++ b/challenge-118/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.c117</artifactId>
+  <artifactId>tw.weekly.c118</artifactId>
   <version>0.1.0-SNAPSHOT</version>
-  <name>tw.weekly.c117</name>
-  <description>Challenge #117</description>
-  <url>https://github.com/tw.weekly/tw.weekly.c117</url>
+  <name>tw.weekly.c118</name>
+  <description>Challenge #118</description>
+  <url>https://github.com/tw.weekly/tw.weekly.c118</url>
   <licenses>
     <license>
       <name>Eclipse Public License</name>
@@ -24,11 +24,6 @@
       <artifactId>clojure</artifactId>
       <version>1.10.3</version>
     </dependency>
-    <dependency>
-      <groupId>net.cgrand</groupId>
-      <artifactId>xforms</artifactId>
-      <version>0.19.2</version>
-    </dependency>
   </dependencies>
   <build>
     <sourceDirectory>src</sourceDirectory>
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/core.clj b/challenge-118/tyler-wardhaugh/clojure/src/tw/weekly/c118/core.clj
new file mode 100644
index 0000000000..a138d86127
--- /dev/null
+++ b/challenge-118/tyler-wardhaugh/clojure/src/tw/weekly/c118/core.clj
@@ -0,0 +1,12 @@
+(ns tw.weekly.c118.core
+  (:require [tw.weekly.c118.t1 :as t1])
+  (:require [tw.weekly.c118.t2 :as t2])
+  (:gen-class))
+
+(defn -main
+  "Run all tasks"
+  [& _]
+  (println "Task #1:")
+  (t1/-main)
+  (println "\nTask #2:")
+  (t2/-main))
diff --git a/challenge-118/tyler-wardhaugh/clojure/src/tw/weekly/c118/t1.clj b/challenge-118/tyler-wardhaugh/clojure/src/tw/weekly/c118/t1.clj
new file mode 100644
index 0000000000..4b8f62cdb3
--- /dev/null
+++ b/challenge-118/tyler-wardhaugh/clojure/src/tw/weekly/c118/t1.clj
@@ -0,0 +1,26 @@
+(ns tw.weekly.c118.t1
+  (:require [clojure.edn :as edn]
+            [clojure.string :as str]))
+
+;;;
+; Task description for TASK #1 › Binary Palindrom
+;;;
+(def DEFAULT-INPUT [5])
+
+(defn bin-parse
+  "Parse a string as a binary representation of an integer."
+  [s]
+  (Integer/parseInt s 2))
+
+(defn binary-palindrome
+  "Determine if the binary representation of an integer is a palindrome."
+  [n]
+  (let [rev (-> n Integer/toBinaryString str/reverse bin-parse)]
+    (zero? (bit-xor n rev))))
+
+(defn -main
+  "Run Task 1 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)]
+    (println (if (binary-palindrome N) 1 0))))
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
new file mode 100644
index 0000000000..bad00754ac
--- /dev/null
+++ b/challenge-118/tyler-wardhaugh/clojure/src/tw/weekly/c118/t2.clj
@@ -0,0 +1,111 @@
+(ns tw.weekly.c118.t2
+  (: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 [(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 [[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
new file mode 100644
index 0000000000..6aff519db7
--- /dev/null
+++ b/challenge-118/tyler-wardhaugh/clojure/test/tw/weekly/c118_test.clj
@@ -0,0 +1,16 @@
+(ns tw.weekly.c118-test
+  (:require [clojure.core.matrix :as m]
+            [clojure.test :refer [deftest is testing]]
+            [tw.weekly.c118.t1 :refer [binary-palindrome]]
+            [tw.weekly.c118.t2 :as t2]))
+
+(deftest task-1
+  (testing "Task 1, Binary Palindrom"
+    (is (true? (binary-palindrome 5)))
+    (is (false? (binary-palindrome 4)))))
+
+(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)))))