From 6ee7fd41be52d089f3aff1a9f211da73565ad35a Mon Sep 17 00:00:00 2001 From: Tyler Wardhaugh Date: Thu, 1 Oct 2020 10:18:48 -0700 Subject: Ch80/Task 1 (clj): add third algorithm Also add benchmarking for this newest algorithm. --- .../tyler-wardhaugh/clojure/src/tw/weekly/c80/t1.clj | 12 ++++++++++-- .../tyler-wardhaugh/clojure/src/tw/weekly/c80/t1_bench.clj | 13 ++++++++----- 2 files changed, 18 insertions(+), 7 deletions(-) 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 ed1cc0d665..440d3cb7df 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,7 +9,7 @@ ;Write a script to find out the smallest positive number missing. ;;;; -(defn smallest-missing-by-set +(defn smallest-missing-by-set-intersection "Determine the smallest positive integer missing in a sequence (by set difference)." [coll] (if-let [missing (->> coll @@ -30,7 +30,15 @@ (inc (last sorted))) 1)) -(def smallest-missing smallest-missing-by-sorting) +(defn smallest-missing-by-set-membership + "Determine the smallest positive integer missing in a sequence (by set membership)." + [coll] + (let [scoll (->> coll (filter pos-int?) set)] + (->> (iterate inc 1) + (remove scoll) + first))) + +(def smallest-missing smallest-missing-by-set-membership) (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 index 14331d11f0..35c7d2b4f2 100644 --- 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 @@ -7,10 +7,13 @@ (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)) + (cl-format true "~2%===~a~60,1,0,'=a" t "=") - (Thread/sleep 1000) + (cl-format true "~2%Benchmarking ~a by set-intersection:~%" t) + (cc/quick-bench (t1/smallest-missing-by-set-intersection t)) - (cl-format true "Benchmarking ~a by-sorting~%" t) - (cc/quick-bench (t1/smallest-missing-by-sorting t)))) + (cl-format true "~2%Benchmarking ~a by sorting:~%" t) + (cc/quick-bench (t1/smallest-missing-by-sorting t)) + + (cl-format true "~2%Benchmarking ~a by set-membership:~%" t) + (cc/quick-bench (t1/smallest-missing-by-set-membership t)))) -- cgit From 86de64b235e0caf3191db46a5885550ffbf93036 Mon Sep 17 00:00:00 2001 From: Tyler Wardhaugh Date: Thu, 1 Oct 2020 10:18:49 -0700 Subject: Ch80/Task 2 (clj): improve algorithm --- challenge-080/tyler-wardhaugh/clojure/src/tw/weekly/c80/t2.clj | 6 ++---- challenge-080/tyler-wardhaugh/clojure/test/tw/weekly/c80_test.clj | 5 +++-- 2 files changed, 5 insertions(+), 6 deletions(-) diff --git a/challenge-080/tyler-wardhaugh/clojure/src/tw/weekly/c80/t2.clj b/challenge-080/tyler-wardhaugh/clojure/src/tw/weekly/c80/t2.clj index 8d12ce4e14..55586b34a8 100644 --- a/challenge-080/tyler-wardhaugh/clojure/src/tw/weekly/c80/t2.clj +++ b/challenge-080/tyler-wardhaugh/clojure/src/tw/weekly/c80/t2.clj @@ -14,10 +14,8 @@ (defn count-candies "Determine the number of candies needed according to the rules in the task description." [coll] - (let [xf (comp (map (juxt (fn [[a b _]] (if (> b a) 1 0)) - (fn [[_ b c]] (if (> b c) 1 0)))) - (map (partial apply + 1))) - source (partition 3 1 (repeat ##Inf) (concat [##Inf] coll))] + (let [xf (map #(inc (if (apply not= %) 1 0))) + source (partition 2 1 (list (last coll)) coll)] (transduce xf + source))) (defn -main 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 7c88e71f6b..32251e39f5 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 @@ -14,5 +14,6 @@ (deftest task-2 (testing "Task 2, Count Candies" - (is (= (count-candies [1, 2, 2]) 4)) - (is (= (count-candies [1, 4, 3, 2]) 7)))) + (is (= (count-candies [1 2 2]) 4)) + (is (= (count-candies [1 4 3 2]) 7)) + (is (= (count-candies [2 1 4 3 1 2]) 11)))) -- cgit From f710b934d57ead36f286d46027b6f427f8efbd12 Mon Sep 17 00:00:00 2001 From: Tyler Wardhaugh Date: Thu, 1 Oct 2020 10:18:49 -0700 Subject: Ch80/Task 2 (lua): improve algorithm --- challenge-080/tyler-wardhaugh/lua/ch-2.lua | 10 +++------- challenge-080/tyler-wardhaugh/lua/test.lua | 1 + 2 files changed, 4 insertions(+), 7 deletions(-) diff --git a/challenge-080/tyler-wardhaugh/lua/ch-2.lua b/challenge-080/tyler-wardhaugh/lua/ch-2.lua index 54d355d037..2378d1b18b 100755 --- a/challenge-080/tyler-wardhaugh/lua/ch-2.lua +++ b/challenge-080/tyler-wardhaugh/lua/ch-2.lua @@ -4,14 +4,10 @@ local t2 = {} function t2.count_candies(coll) local count = #coll - local maybe_inc = function(i, j) - if (coll[i] > coll[j]) then count = count + 1 end - end - -- sweep left-to-right - for i=1,#coll-1 do maybe_inc(i, i+1) end - -- sweep right-to-left - for i=#coll,2,-1 do maybe_inc(i, i-1) end + for i=1,#coll-1 do + if (coll[i] ~= coll[i+1]) then count = count + 1 end + end return count end diff --git a/challenge-080/tyler-wardhaugh/lua/test.lua b/challenge-080/tyler-wardhaugh/lua/test.lua index 44d03f8844..44f80e3459 100755 --- a/challenge-080/tyler-wardhaugh/lua/test.lua +++ b/challenge-080/tyler-wardhaugh/lua/test.lua @@ -19,5 +19,6 @@ describe("Task 2, Count Candies", function() it("produces correct results for the examples", function() assert.are.same(t2.count_candies({1, 2, 2}), 4) assert.are.same(t2.count_candies({1, 4, 3, 2}), 7) + assert.are.same(t2.count_candies({2, 1, 4, 3, 1, 2}), 11) end) end) -- cgit