Ch80/Task 1: introduce a more efficient algorithm

Constructing a set is elegant but not memory-efficient when dealing with
large numbers.

Add benchmarking to demonstrate the difference.

Also, change the original algorithm (and add a test) to ensure 1 is
returned when no positive integers are provided.

5 files changed, 42 insertions, 6 deletions

diff --git a/challenge-080/tyler-wardhaugh/clojure/README.md b/challenge-080/tyler-wardhaugh/clojure/README.md
index 57a8bbe6c2..27344ef9cb 100644
--- a/challenge-080/tyler-wardhaugh/clojure/README.md
+++ b/challenge-080/tyler-wardhaugh/clojure/README.md
@@ -17,6 +17,10 @@ Run Task #1 with input
 
     $ clojure -m tw.weekly.c80.t1 A1 A2 A3 [...]
 
+Benchmark both methods defined in Task #1:
+
+    $ clojure -m tw.weekly.c80.t1-bench
+
 Run Task #2 with input:
 
     $ clojure -m tw.weekly.c80.t2 A1 A2 A3 [...]
diff --git a/challenge-080/tyler-wardhaugh/clojure/deps.edn b/challenge-080/tyler-wardhaugh/clojure/deps.edn
index 35e57a9092..c572dcdfc7 100644
--- a/challenge-080/tyler-wardhaugh/clojure/deps.edn
+++ b/challenge-080/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"}
+        criterium/criterium {:mvn/version "0.4.6"}}
  :aliases
  {:test {:extra-paths ["test"]
          :extra-deps {org.clojure/test.check {:mvn/version "1.0.0"}}}
diff --git a/challenge-080/tyler-wardhaugh/clojure/src/tw/weekly/c80/t1.clj b/challenge-080/tyler-wardhaugh/clojure/src/tw/weekly/c80/t1.clj
index 8540ad4d0a..993eb06292 100644
--- a/challenge-080/tyler-wardhaugh/clojure/src/tw/weekly/c80/t1.clj
+++ b/challenge-080/tyler-wardhaugh/clojure/src/tw/weekly/c80/t1.clj
@@ -9,14 +9,27 @@
 ;Write a script to find out the smallest positive number missing.
 ;;;;
 
-(defn smallest-missing
-  "Determine the smallest positive integer missing in a sequence."
+(defn smallest-missing-by-set
+  "Determine the smallest positive integer missing in a sequence (by set difference)."
   [coll]
-  (when-let [missing (->> coll
+  (if-let [missing (->> coll
                         ((juxt #(set (range 1 (inc (apply max %)))) set))
                         (apply set/difference)
                         seq)]
-      (apply min missing)))
+      (apply min missing)
+      1))
+
+(defn smallest-missing-by-sorting
+  "Determine the smallest positive integer missing in a sequence (by sorting)."
+  [coll]
+  (if-let [sorted (->> coll (filter pos-int?) sort seq)]
+    (->> (map vector (iterate inc 1) sorted)
+         (filter (partial apply not=))
+         (take 1)
+         ffirst)
+    1))
+
+(def smallest-missing smallest-missing-by-sorting)
 
 (defn -main
   "Run Task 1 with a list of integers N, defaulting to the first one given in the examples."
diff --git a/challenge-080/tyler-wardhaugh/clojure/src/tw/weekly/c80/t1_bench.clj b/challenge-080/tyler-wardhaugh/clojure/src/tw/weekly/c80/t1_bench.clj
new file mode 100644
index 0000000000..14331d11f0
--- /dev/null
+++ b/challenge-080/tyler-wardhaugh/clojure/src/tw/weekly/c80/t1_bench.clj
@@ -0,0 +1,16 @@
+(ns tw.weekly.c80.t1-bench
+  (:require [clojure.pprint :refer [cl-format]])
+  (:require [tw.weekly.c80.t1 :as t1])
+  (:require [criterium.core :as cc]))
+
+
+(defn -main
+  [& _]
+  (doseq [t [[1 -2 8] [1 2 3] [1 2 3 (int 1e7)]]]
+    (cl-format true "Benchmarking ~a by-set:~%" t)
+    (cc/quick-bench (t1/smallest-missing-by-set t))
+
+    (Thread/sleep 1000)
+
+    (cl-format true "Benchmarking ~a by-sorting~%" t)
+    (cc/quick-bench (t1/smallest-missing-by-sorting t))))
diff --git a/challenge-080/tyler-wardhaugh/clojure/test/tw/weekly/c80_test.clj b/challenge-080/tyler-wardhaugh/clojure/test/tw/weekly/c80_test.clj
index f940c2dc50..bd5520ea19 100644
--- a/challenge-080/tyler-wardhaugh/clojure/test/tw/weekly/c80_test.clj
+++ b/challenge-080/tyler-wardhaugh/clojure/test/tw/weekly/c80_test.clj
@@ -8,7 +8,9 @@
     (is (= (smallest-missing [5 2 -2 0]) 1))
     (is (= (smallest-missing [1 8 -1]) 2))
     (is (= (smallest-missing [2 0 -1]) 1))
-    (is (nil? (smallest-missing [1 2 3])))))
+    (is (= (smallest-missing [-5 -4 -3]) 1))
+    (is (= (smallest-missing [1 2 3 (int 1e7)]) 4))
+    (is (nil? (smallest-missing [1 4 2 3])))))
 
 (deftest task-2
   (testing "Task 2, Count Candies"