Task 1

6 files changed, 50 insertions, 56 deletions

diff --git a/challenge-075/tyler-wardhaugh/clojure/README.md b/challenge-075/tyler-wardhaugh/clojure/README.md
index d87bacccd2..8c07634ced 100644
--- a/challenge-075/tyler-wardhaugh/clojure/README.md
+++ b/challenge-075/tyler-wardhaugh/clojure/README.md
@@ -13,9 +13,9 @@ Run the project's tests (which are samples from the task descriptions):
 
     $ clojure -A:test:runner
 
-Run Task #1 with input:
+Run Task #1 with input (SUM COIN [COIN]...)
 
-    $ clojure -m tw.weekly.ch-1 8 8 8 7 9
+    $ clojure -m tw.weekly.ch-1 6 1 2 4
 
 Run Task #2 with input:
 
@@ -25,8 +25,6 @@ Run Task #2 with input:
 
 I used Sean Corfield's clj-new to generate the project template
 
-    $ clj -A:new app tw.weekly.c75
-
 See [seancorfield/clj-new: Generate new projects based on clj, Boot, or Leiningen Templates!](https://github.com/seancorfield/clj-new) for more information.
 
 ## License
diff --git a/challenge-075/tyler-wardhaugh/clojure/deps.edn b/challenge-075/tyler-wardhaugh/clojure/deps.edn
index 3ba8910a4a..6f74027036 100644
--- a/challenge-075/tyler-wardhaugh/clojure/deps.edn
+++ b/challenge-075/tyler-wardhaugh/clojure/deps.edn
@@ -1,5 +1,6 @@
 {:paths ["src" "resources"]
- :deps {org.clojure/clojure {:mvn/version "1.10.1"}}
+ :deps {org.clojure/clojure {:mvn/version "1.10.1"}
+        metametadata/multiset {:mvn/version "0.1.1"}}
  :aliases
  {:test {:extra-paths ["test"]
          :extra-deps {org.clojure/test.check {:mvn/version "1.0.0"}}}
diff --git a/challenge-075/tyler-wardhaugh/clojure/pom.xml b/challenge-075/tyler-wardhaugh/clojure/pom.xml
index a76bd6e5cd..7e0da3dd93 100644
--- a/challenge-075/tyler-wardhaugh/clojure/pom.xml
+++ b/challenge-075/tyler-wardhaugh/clojure/pom.xml
@@ -24,6 +24,11 @@
       <artifactId>clojure</artifactId>
       <version>1.10.1</version>
     </dependency>
+    <dependency>
+      <groupId>metametadata</groupId>
+      <artifactId>multiset</artifactId>
+      <version>0.1.1</version>
+    </dependency>
   </dependencies>
   <build>
     <build>
diff --git a/challenge-075/tyler-wardhaugh/clojure/src/tw/weekly/ch_1.clj b/challenge-075/tyler-wardhaugh/clojure/src/tw/weekly/ch_1.clj
index 416d2a1d85..930fb0106e 100644
--- a/challenge-075/tyler-wardhaugh/clojure/src/tw/weekly/ch_1.clj
+++ b/challenge-075/tyler-wardhaugh/clojure/src/tw/weekly/ch_1.clj
@@ -1,20 +1,32 @@
-(ns tw.weekly.ch-1)
+(ns tw.weekly.ch-1
+  (:require [clojure.edn :as edn])
+  (:require [multiset.core :as ms]))
 
-(defn majority
-  "Calculate the majority element, which is the element in a list that appears more than floor(size_of_list/2), prefering the least significant digit that matches that criteria. Returns -1 if no such element is found."
-  [coll]
-  (let [minimum (Math/floor (/ (count coll) 2))
-        maj (->> coll
-              frequencies
-              (filter (comp #(> % minimum) second))
-              (sort second)
-              ffirst)]
-    (or maj -1)))
+(declare memsolve)
+(defn- solve
+  "Recursively find solutions and return them in a list. This is the main worker function designed to be called only from find-coin-sum."
+  [sum coins ci curr sols]
+  (cond
+    (= sum 0) (conj sols curr)
+    (< sum 0) sols
+    (and (< ci 0) (> sum 0)) sols
+    :else (concat
+            (memsolve sum coins (- ci 1) curr sols)
+            (memsolve (- sum (get coins ci)) coins ci (conj curr (get coins ci)) sols))))
+
+(def memsolve (memoize solve))
+
+(defn find-coin-sum
+  "Find the valid coin combinations to achieve the specified sum."
+  [sum coins]
+  (memsolve sum coins (- (count coins) 1) (ms/multiset) []))
 
 (defn -main
-  "Run Task 1 with a list of integers, defaulting to the sample given in the task description."
+  "Run Task 1 with a sum list of coin denominations, defaulting to the sample given in the task description."
   [& args]
-  (let [N (if (not-empty args)
-            (map clojure.edn/read-string args)
-            [2, 2, 2, 3, 2, 4, 2])]
-    (println (majority N))))
+  (let [[S C] (if (not-empty args)
+                [(-> args first edn/read-string) (->> (rest args) (mapv edn/read-string))]
+                [6 [1, 2, 4]])]
+    (let [solutions (find-coin-sum S C)]
+      (printf "There are %d possible way(s) to make sum %d using %s\n" (count solutions) S C)
+      (println solutions))))
diff --git a/challenge-075/tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj b/challenge-075/tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj
index 299ab63690..a71ab930c4 100644
--- a/challenge-075/tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj
+++ b/challenge-075/tyler-wardhaugh/clojure/src/tw/weekly/ch_2.clj
@@ -1,33 +1,10 @@
 (ns tw.weekly.ch-2
-  (:require [clojure.string :as str])
-  (:require [flatland.ordered.map :as fo]))
-
-(defn ordered-frequencies
-  "A modification of clojure.core/frequencies that guarantees the map returns keys in the order seen in the collection. Thus it returns an ordered map from distinct items in coll to the number of times they appear."
-  [coll]
-  (persistent!
-   (reduce (fn [counts x]
-             (assoc! counts x (inc (get counts x 0))))
-           (transient (fo/ordered-map)) coll)))
-
-(defn find-fnr [string]
-  "Find the first non-repeating character (FNR) for a string."
-  (let [counts (ordered-frequencies string)
-        non-repeaters (filter (comp #(= 1 %) second) counts)]
-    (-> non-repeaters last first)))
-
-(defn find-fnr-over-string
-  "Generate a string comprised of the first non-repeating character (FNR) for successive substrings of a given string."
-  [string]
-  (->> string
-       (reductions str "")
-       (drop 1)
-       (map find-fnr)
-       (map #(or % \#))
-       str/join))
+  (:require [clojure.edn :as edn]))
 
 (defn -main
-  "Run Task 2 with a string, defaulting to the sample given in the task description."
+  "Run Task 2 with a list of integers, defaulting to the sample given in the task description."
   [& args]
-  (let [S (or (-> args first) "ababc")]
-    (println (find-fnr-over-string S))))
+  (let [A (if (not-empty args) (map edn/read-string args) [2, 1, 4, 5, 3, 7])]
+    (println A)))
+
+(-main)
diff --git a/challenge-075/tyler-wardhaugh/clojure/test/tw/weekly/c75_test.clj b/challenge-075/tyler-wardhaugh/clojure/test/tw/weekly/c75_test.clj
index 888e219c22..856991c00c 100644
--- a/challenge-075/tyler-wardhaugh/clojure/test/tw/weekly/c75_test.clj
+++ b/challenge-075/tyler-wardhaugh/clojure/test/tw/weekly/c75_test.clj
@@ -1,14 +1,15 @@
 (ns tw.weekly.c75-test
   (:require [clojure.test :refer :all]
-            [tw.weekly.ch-1 :refer [majority]]
-            [tw.weekly.ch-2 :refer [find-fnr-over-string]]))
+            [multiset.core :as ms]
+            [tw.weekly.ch-1 :refer [find-coin-sum]]
+            [tw.weekly.ch-2 :refer []]))
 
 (deftest ch-1
   (testing "Task 1"
-    (is (= 2 (majority (list 1, 2, 2, 3, 2, 4, 2))))
-    (is (= -1 (majority (list 1, 3, 1, 2, 4, 5))))))
+    (let [expected (map (partial into (ms/multiset)) (list [1 1 1 1 1 1] [2 1 1 1 1] [2 2 1 1] [2 2 2] [4 1 1] [4 2]))]
+      (is (= (find-coin-sum 6 [1 2 4]) expected)))))
 
 (deftest ch-2
   (testing "Task 2"
-    (is (= "abb#c" (find-fnr-over-string "ababc")))
-    (is (= "xyzyx#" (find-fnr-over-string "xyzzyx")))))
+    
+    ))