From f7bcdd4005929c02b722029a7621018d7694b6c9 Mon Sep 17 00:00:00 2001 From: Tyler Wardhaugh Date: Wed, 14 Oct 2020 10:29:10 -0700 Subject: Ch82/Task 1: improve algorithm using gcd(m, n) One of the great things about the PWC is seeing others' code and gleaning insights from them. --- challenge-082/tyler-wardhaugh/clojure/deps.edn | 3 ++- challenge-082/tyler-wardhaugh/clojure/pom.xml | 5 +++++ .../tyler-wardhaugh/clojure/src/tw/weekly/c82/t1.clj | 11 ++++++----- 3 files changed, 13 insertions(+), 6 deletions(-) diff --git a/challenge-082/tyler-wardhaugh/clojure/deps.edn b/challenge-082/tyler-wardhaugh/clojure/deps.edn index 4010bedaeb..c692c74c45 100644 --- a/challenge-082/tyler-wardhaugh/clojure/deps.edn +++ b/challenge-082/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"} + org.clojure/math.numeric-tower {:mvn/version "0.0.4"}} :aliases {:test {:extra-paths ["test"] :extra-deps {org.clojure/test.check {:mvn/version "1.0.0"}}} diff --git a/challenge-082/tyler-wardhaugh/clojure/pom.xml b/challenge-082/tyler-wardhaugh/clojure/pom.xml index 6fead6ac04..92eb55d64a 100644 --- a/challenge-082/tyler-wardhaugh/clojure/pom.xml +++ b/challenge-082/tyler-wardhaugh/clojure/pom.xml @@ -30,6 +30,11 @@ clojure 1.10.1 + + org.clojure + math.numeric-tower + 0.0.4 + src diff --git a/challenge-082/tyler-wardhaugh/clojure/src/tw/weekly/c82/t1.clj b/challenge-082/tyler-wardhaugh/clojure/src/tw/weekly/c82/t1.clj index 1b2713d772..7d7e3288c7 100644 --- a/challenge-082/tyler-wardhaugh/clojure/src/tw/weekly/c82/t1.clj +++ b/challenge-082/tyler-wardhaugh/clojure/src/tw/weekly/c82/t1.clj @@ -1,5 +1,6 @@ (ns tw.weekly.c82.t1 - (:require [clojure.edn :as edn])) + (:require [clojure.edn :as edn]) + (:require [clojure.math.numeric-tower :as math])) ;;; Task description for TASK #1 › Common Factors ; Submitted by: Niels van Dijke @@ -11,10 +12,10 @@ (defn common-factors "Determine the common factors for m and n." [m n] - (let [[m n] (sort [m n]) - source (concat (range 1 (inc (quot n 2))) [n]) - xf (filter (fn [x] (= 0 (rem n x) (rem m x))))] - (into (sorted-set) xf source))) + (let [gcd (math/gcd m n) + source (range 1 (inc (quot gcd 2))) + xf (filter (fn [x] (zero? (rem gcd x))))] + (into (sorted-set gcd) xf source))) (defn -main "Run Task 1 with two strings A and B, defaulting to the first example given in the task description." -- cgit From b8eac8546d3665386c8959b39a2a34a30edbf1f1 Mon Sep 17 00:00:00 2001 From: Tyler Wardhaugh Date: Wed, 14 Oct 2020 16:01:49 -0700 Subject: Ch82 (Lua): Task 1 --- challenge-082/tyler-wardhaugh/lua/README.md | 5 ++- challenge-082/tyler-wardhaugh/lua/ch-1.lua | 41 +++++++++++++++++++++++ challenge-082/tyler-wardhaugh/lua/resources/input | 3 -- challenge-082/tyler-wardhaugh/lua/run.lua | 9 +++++ challenge-082/tyler-wardhaugh/lua/test.lua | 11 ++++++ 5 files changed, 63 insertions(+), 6 deletions(-) create mode 100755 challenge-082/tyler-wardhaugh/lua/ch-1.lua delete mode 100644 challenge-082/tyler-wardhaugh/lua/resources/input create mode 100755 challenge-082/tyler-wardhaugh/lua/run.lua create mode 100755 challenge-082/tyler-wardhaugh/lua/test.lua diff --git a/challenge-082/tyler-wardhaugh/lua/README.md b/challenge-082/tyler-wardhaugh/lua/README.md index e629f5866f..8247d79487 100644 --- a/challenge-082/tyler-wardhaugh/lua/README.md +++ b/challenge-082/tyler-wardhaugh/lua/README.md @@ -7,11 +7,11 @@ The Weekly Challenge - #081 - Tyler Wardhaugh Run Task 1: - $ ./run.lua ch-1 S1 S2 + $ ./run.lua ch-1 M N Run Task 2: - $ ./run.lua ch-2 INPUT + $ ./run.lua ch-2 A B C Run the project's tests (all the samples from the task descriptions plus some others): @@ -20,5 +20,4 @@ Run the project's tests (all the samples from the task descriptions plus some ot ## Requirements: * [Lua](https://www.lua.org/) 5.3 * [LuaRocks](https://luarocks.org/) -* [LPeg](http://www.inf.puc-rio.br/~roberto/lpeg/) (for parsing expression grammars) * [busted](https://olivinelabs.com/busted/) (a unit testing framework) diff --git a/challenge-082/tyler-wardhaugh/lua/ch-1.lua b/challenge-082/tyler-wardhaugh/lua/ch-1.lua new file mode 100755 index 0000000000..cd6aea10ff --- /dev/null +++ b/challenge-082/tyler-wardhaugh/lua/ch-1.lua @@ -0,0 +1,41 @@ +#!/usr/bin/env lua + +local t1 = {} + +-- Greatest Common Divisor +-- source: https://www.rosettacode.org/wiki/Greatest_common_divisor#Lua +function t1.gcd(a, b) + while b ~= 0 do + a, b = b, a % b + end + return math.floor(math.abs(a)) +end + +function t1.common_factors(m, n) + local gcd = t1.gcd(m, n) + local factors = {[1]=true, [gcd]=true} -- 1 and gcd are always factors + + for i = 2, gcd // 2 do + if math.fmod(gcd, i) == 0 then + factors[i] = true + end + end + + local results = {} + for k, _ in pairs(factors) do table.insert(results, k) end + table.sort(results) + return results +end + +function t1.run(args) + local m, n = math.floor(tonumber(args[1])), math.floor(tonumber(args[2])) + if not m or not n then + io.stderr:write("error: must supply two integers\n") + os.exit(2) + end + + local factors = t1.common_factors(m, n) + print(table.concat(factors, " ")) +end + +return t1 diff --git a/challenge-082/tyler-wardhaugh/lua/resources/input b/challenge-082/tyler-wardhaugh/lua/resources/input deleted file mode 100644 index 37001629ad..0000000000 --- a/challenge-082/tyler-wardhaugh/lua/resources/input +++ /dev/null @@ -1,3 +0,0 @@ -West Side Story - -The award-winning adaptation of the classic romantic tragedy "Romeo and Juliet". The feuding families become two warring New York City gangs, the white Jets led by Riff and the Latino Sharks, led by Bernardo. Their hatred escalates to a point where neither can coexist with any form of understanding. But when Riff's best friend (and former Jet) Tony and Bernardo's younger sister Maria meet at a dance, no one can do anything to stop their love. Maria and Tony begin meeting in secret, planning to run away. Then the Sharks and Jets plan a rumble under the highway--whoever wins gains control of the streets. Maria sends Tony to stop it, hoping it can end the violence. It goes terribly wrong, and before the lovers know what's happened, tragedy strikes and doesn't stop until the climactic and heartbreaking ending. diff --git a/challenge-082/tyler-wardhaugh/lua/run.lua b/challenge-082/tyler-wardhaugh/lua/run.lua new file mode 100755 index 0000000000..c6e7473bee --- /dev/null +++ b/challenge-082/tyler-wardhaugh/lua/run.lua @@ -0,0 +1,9 @@ +#!/usr/bin/env lua + +local filename = arg[1] +local run_args = table.move(arg, 2, #arg, 1, {}) + +io.write(string.format("Running task from '%s' with {%s}:\n", + filename, table.concat(run_args, ", "))) + +require(filename).run(run_args) diff --git a/challenge-082/tyler-wardhaugh/lua/test.lua b/challenge-082/tyler-wardhaugh/lua/test.lua new file mode 100755 index 0000000000..23b3a4e063 --- /dev/null +++ b/challenge-082/tyler-wardhaugh/lua/test.lua @@ -0,0 +1,11 @@ +#!/usr/bin/env lua + +require 'busted.runner'() + +describe("Task 1, Common Factors", function() + local t1 = require'ch-1' + it("produces correct results for the examples", function() + assert.are.same(t1.common_factors(12, 18), {1, 2, 3, 6}) + assert.are.same(t1.common_factors(18, 23), {1}) + end) +end) -- cgit From d597407285896782e8654f36f1c2f1bad2f7fdeb Mon Sep 17 00:00:00 2001 From: Tyler Wardhaugh Date: Wed, 14 Oct 2020 16:35:06 -0700 Subject: Ch82 (Lua): Task 2 --- challenge-082/tyler-wardhaugh/lua/ch-2.lua | 30 ++++++++++++++++++++++++++++++ challenge-082/tyler-wardhaugh/lua/test.lua | 9 +++++++++ 2 files changed, 39 insertions(+) create mode 100755 challenge-082/tyler-wardhaugh/lua/ch-2.lua diff --git a/challenge-082/tyler-wardhaugh/lua/ch-2.lua b/challenge-082/tyler-wardhaugh/lua/ch-2.lua new file mode 100755 index 0000000000..b92e26bffd --- /dev/null +++ b/challenge-082/tyler-wardhaugh/lua/ch-2.lua @@ -0,0 +1,30 @@ +#!/usr/bin/env lua + +local t2 = {} + +function t2.interleave_string(a, b, c) + if a:len() == 0 then return b == c end + if b:len() == 0 then return a == c end + if c:len() ~= a:len() + b:len() then return end + + -- get heads (1st char) and tails (the rest) + local ah, at = a:match("^(%a)(%a*)$") + local bh, bt = b:match("^(%a)(%a*)$") + local ch, ct = c:match("^(%a)(%a*)$") + + return ((ah == ch) and t2.interleave_string(at, b, ct)) + or ((bh == ch) and t2.interleave_string(a, bt, ct)) +end + +function t2.run(args) + if #args ~= 3 then + io.stderr:write("error: must supply three strings\n") + os.exit(2) + end + + local a, b, c = table.unpack(args, 1, 3) + local result = t2.interleave_string(a, b, c) + if result then print(1) else print(0) end +end + +return t2 diff --git a/challenge-082/tyler-wardhaugh/lua/test.lua b/challenge-082/tyler-wardhaugh/lua/test.lua index 23b3a4e063..20f0d33d27 100755 --- a/challenge-082/tyler-wardhaugh/lua/test.lua +++ b/challenge-082/tyler-wardhaugh/lua/test.lua @@ -9,3 +9,12 @@ describe("Task 1, Common Factors", function() assert.are.same(t1.common_factors(18, 23), {1}) end) end) + +describe("Task 2, Interleave Strings", function() + local t2 = require'ch-2' + it("produces correct results for the examples", function() + assert.are.same(t2.interleave_string("XY", "X", "XXY"), true) + assert.are.same(t2.interleave_string("XXY", "XXZ", "XXXXZY"), true) + assert.are.same(t2.interleave_string("YX", "X", "XXY"), false) + end) +end) -- cgit