diff options
20 files changed, 377 insertions, 22 deletions
diff --git a/challenge-099/tyler-wardhaugh/clojure/README.md b/challenge-099/tyler-wardhaugh/clojure/README.md index dbeaac833c..74a213f563 100644 --- a/challenge-099/tyler-wardhaugh/clojure/README.md +++ b/challenge-099/tyler-wardhaugh/clojure/README.md @@ -1,13 +1,13 @@ -# tw.weekly.c98 +# tw.weekly.c99 -The Weekly Challenge - #098 - Tyler Wardhaugh +The Weekly Challenge - #099 - Tyler Wardhaugh ## Usage Run the project directly (shows default output from both tasks): - $ clojure -M -m tw.weekly.c98.core + $ clojure -M -m tw.weekly.c99.core Run the project's tests (which are samples from the task descriptions): @@ -15,11 +15,11 @@ Run the project's tests (which are samples from the task descriptions): Run Task #1 with input - $ clojure -M -m tw.weekly.c98.t1 FILE N + $ clojure -M -m tw.weekly.c99.t1 S P Run Task #2 with input: - $ clojure -M -m tw.weekly.c98.t2 NS N + $ clojure -M -m tw.weekly.c99.t2 S T ## Project Template diff --git a/challenge-099/tyler-wardhaugh/clojure/deps.edn b/challenge-099/tyler-wardhaugh/clojure/deps.edn index 3702e967c4..4234dbc188 100644 --- a/challenge-099/tyler-wardhaugh/clojure/deps.edn +++ b/challenge-099/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"} + net.mikera/core.matrix {:mvn/version "0.62.0"}} :aliases {:test {:extra-paths ["test"] :extra-deps {org.clojure/test.check {:mvn/version "1.0.0"}}} @@ -9,6 +10,6 @@ :sha "f7ef16dc3b8332b0d77bc0274578ad5270fbfedd"}} :main-opts ["-m" "cognitect.test-runner" "-d" "test"]} - :uberjar {:extra-deps {seancorfield/depstar {:mvn/version "1.0.96"}} - :main-opts ["-m" "hf.depstar.uberjar" "tw.weekly.c96.jar" - "-C" "-m" "tw.weekly.c96"]}}} + :uberjar {:extra-deps {seancorfield/depstar {:mvn/version "1.0.99"}} + :main-opts ["-m" "hf.depstar.uberjar" "tw.weekly.c99.jar" + "-C" "-m" "tw.weekly.c99"]}}} diff --git a/challenge-099/tyler-wardhaugh/clojure/pom.xml b/challenge-099/tyler-wardhaugh/clojure/pom.xml index 04154a698d..aafdb47364 100644 --- a/challenge-099/tyler-wardhaugh/clojure/pom.xml +++ b/challenge-099/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.c96</artifactId> + <artifactId>tw.weekly.c99</artifactId> <version>0.1.0-SNAPSHOT</version> - <name>tw.weekly.c96</name> - <description>Challenge #096</description> - <url>https://github.com/tw.weekly/tw.weekly.c96</url> + <name>tw.weekly.c99</name> + <description>Challenge #099</description> + <url>https://github.com/tw.weekly/tw.weekly.c99</url> <licenses> <license> <name>Eclipse Public License</name> @@ -19,9 +19,9 @@ </developer> </developers> <scm> - <url>https://github.com/tw.weekly/tw.weekly.c96</url> - <connection>scm:git:git://github.com/tw.weekly/tw.weekly.c96.git</connection> - <developerConnection>scm:git:ssh://git@github.com/tw.weekly/tw.weekly.c96.git</developerConnection> + <url>https://github.com/tw.weekly/tw.weekly.c99</url> + <connection>scm:git:git://github.com/tw.weekly/tw.weekly.c99.git</connection> + <developerConnection>scm:git:ssh://git@github.com/tw.weekly/tw.weekly.c99.git</developerConnection> <tag>HEAD</tag> </scm> <dependencies> @@ -30,6 +30,11 @@ <artifactId>clojure</artifactId> <version>1.10.1</version> </dependency> + <dependency> + <groupId>net.mikera</groupId> + <artifactId>core.matrix</artifactId> + <version>0.62.0</version> + </dependency> </dependencies> <build> <sourceDirectory>src</sourceDirectory> diff --git a/challenge-099/tyler-wardhaugh/clojure/src/tw/weekly/c99/core.clj b/challenge-099/tyler-wardhaugh/clojure/src/tw/weekly/c99/core.clj new file mode 100644 index 0000000000..6dddb00c0b --- /dev/null +++ b/challenge-099/tyler-wardhaugh/clojure/src/tw/weekly/c99/core.clj @@ -0,0 +1,12 @@ +(ns tw.weekly.c99.core + (:require [tw.weekly.c99.t1 :as t1]) + (:require [tw.weekly.c99.t2 :as t2]) + (:gen-class)) + +(defn -main + "Run all tasks" + [& _] + (println "Task #1:") + (t1/-main) + (println "\nTask #2:") + (t2/-main)) diff --git a/challenge-099/tyler-wardhaugh/clojure/src/tw/weekly/c99/t1.clj b/challenge-099/tyler-wardhaugh/clojure/src/tw/weekly/c99/t1.clj new file mode 100644 index 0000000000..c00e69c46f --- /dev/null +++ b/challenge-099/tyler-wardhaugh/clojure/src/tw/weekly/c99/t1.clj @@ -0,0 +1,24 @@ +(ns tw.weekly.c99.t1 + (:import (java.nio.file FileSystems Paths)) + (:require [clojure.edn :as edn])) + +;;; +; Task description for TASK #1 › Pattern Match +;;; + +(def DEFAULT-INPUT ["abcde" "a*e"]) +(def FILESYSTEM (FileSystems/getDefault)) + +(defn pattern-match + "Determine if string s matches the given (glob) pattern." + [s pattern] + (let [matcher (.getPathMatcher FILESYSTEM (str "glob:" pattern)) + s-path (Paths/get s (into-array String ""))] + (.matches matcher s-path))) + +(defn -main + "Run Task 1 using a string S and a pattern P, defaulting to the example + given in the task description." + [& args] + (let [[S P] (or (some->> args (take 2) (map edn/read-string)) DEFAULT-INPUT)] + (println (if (pattern-match S P) 1 0)))) diff --git a/challenge-099/tyler-wardhaugh/clojure/src/tw/weekly/c99/t2.clj b/challenge-099/tyler-wardhaugh/clojure/src/tw/weekly/c99/t2.clj new file mode 100644 index 0000000000..3f8e6888db --- /dev/null +++ b/challenge-099/tyler-wardhaugh/clojure/src/tw/weekly/c99/t2.clj @@ -0,0 +1,44 @@ +(ns tw.weekly.c99.t2 + (:require [clojure.edn :as edn] + [clojure.core.matrix :as m])) + +;;; +; Task description for TASK #2 › Unique Subsequence +;;; + +(def DEFAULT-INPUT ["littleit" "lit"]) + +(defn- uniq-subseq-dp + "Use a dynamic programming algorithm to solve unique subsequences. + Source: https://www.geeksforgeeks.org/count-distinct-occurrences-as-a-subsequence/" + [s t m n] + (let [m+1 (inc m) + n+1 (inc n) + dp (m/mutable (m/zero-matrix :ndarray m+1 n+1))] + (m/set-column! dp 0 (repeat m+1 0)) + (m/set-row! dp 0 (repeat n+1 1)) + (dorun (for [i (range 1 m+1) + j (range 1 n+1)] + (let [schar (nth s (dec j)) + tchar (nth t (dec i))] + (if (not= schar tchar) + (m/mset! dp i j (m/mget dp i (dec j))) + (m/mset! dp i j (+ (m/mget dp i (dec j)) + (m/mget dp (dec i) (dec j)))))))) + (m/mget dp m n))) + +(defn unique-subsequences + "Count the unique subsequences of string t in string s" + [s t] + (let [m (count t) + n (count s)] + (if (> m n) + 0 + (uniq-subseq-dp s t m n)))) + +(defn -main + "Run Task 2 using a sorted sequence of integers NS and a target N, + defaulting to the example given in the task description." + [& args] + (let [[S T] (or (some->> args (take 2) (map edn/read-string)) DEFAULT-INPUT)] + (println (unique-subsequences S T)))) diff --git a/challenge-099/tyler-wardhaugh/clojure/test/tw/weekly/c99_test.clj b/challenge-099/tyler-wardhaugh/clojure/test/tw/weekly/c99_test.clj new file mode 100644 index 0000000000..4ef774679c --- /dev/null +++ b/challenge-099/tyler-wardhaugh/clojure/test/tw/weekly/c99_test.clj @@ -0,0 +1,16 @@ +(ns tw.weekly.c99-test + (:require [clojure.test :refer [deftest is testing]] + [tw.weekly.c99.t1 :refer [pattern-match]] + [tw.weekly.c99.t2 :refer [unique-subsequences]])) + +(deftest task-1 + (testing "Task 1, Pattern Match" + (is (true? (pattern-match "abcde" "a*e"))) + (is (false? (pattern-match "abcde" "a*d"))) + (is (false? (pattern-match "abcde" "?b*d"))) + (is (true? (pattern-match "abcde" "a*c?e"))))) + +(deftest task-2 + (testing "Task 2, Unique Subsequences" + (is (= 5 (unique-subsequences "littleit" "lit"))) + (is (= 3 (unique-subsequences "london" "lon"))))) diff --git a/challenge-099/tyler-wardhaugh/lua/README.md b/challenge-099/tyler-wardhaugh/lua/README.md index b653496267..2d19587df0 100644 --- a/challenge-099/tyler-wardhaugh/lua/README.md +++ b/challenge-099/tyler-wardhaugh/lua/README.md @@ -1,17 +1,17 @@ # The Weekly Challenge -The Weekly Challenge - #098 - Tyler Wardhaugh +The Weekly Challenge - #099 - Tyler Wardhaugh ## Usage Run Task 1 with input: - $ ./run.lua ch-1 FILE N + $ ./run.lua ch-1 S P Run Task 2: - $ ./run.lua ch-2 + $ ./run.lua ch-2 S T Run the project's tests (all the samples from the task descriptions plus some others): diff --git a/challenge-099/tyler-wardhaugh/lua/ch-1.lua b/challenge-099/tyler-wardhaugh/lua/ch-1.lua new file mode 100755 index 0000000000..837e8e848f --- /dev/null +++ b/challenge-099/tyler-wardhaugh/lua/ch-1.lua @@ -0,0 +1,49 @@ +#!/usr/bin/env lua + +local t1 = {} +t1.DEFAULT_INPUT = {'abcde', 'a*e'} + +--[[ +-- Lua does not have a built-in globbing function, but there are 3rd party +-- libraries. Instead we will simply stick to the task's description of the +-- two wild characters and no escape mechanism. We can accomplish that pretty +-- easily with Lua's patterns, which have a small number of special characters +-- to escape and straight-forward translations of the wild characters. +--]] +function t1.pattern_match(s, p) + local specials = '^[%^%$%(%)%%%.%[%]%+%-]$' + + local pats = {'^'} + for c in p:gmatch('.') do + if c == '?' then + table.insert(pats, '.') + elseif c == '*' then + table.insert(pats, '.+') + elseif c:match(specials) then + table.insert(pats, '%' .. c) + else + table.insert(pats, c) + end + end + table.insert(pats, '$') + + local luapat = table.concat(pats) + return s:match(luapat) +end + +function t1.run(args) + local s, p + if #args > 0 then + s, p = args[1], args[2] + else + s, p = table.unpack(t1.DEFAULT_INPUT) + end + + if t1.pattern_match(s, p) then + print(1) + else + print(0) + end +end + +return t1 diff --git a/challenge-099/tyler-wardhaugh/lua/ch-2.lua b/challenge-099/tyler-wardhaugh/lua/ch-2.lua new file mode 100755 index 0000000000..6ec5f2b551 --- /dev/null +++ b/challenge-099/tyler-wardhaugh/lua/ch-2.lua @@ -0,0 +1,56 @@ +local t2 = {} +t2.DEFAULT_INPUT = {'littleit', 'lit'} + +--[[ + Use a dynamic programming algorithm to solve unique subsequences. + Source: https://www.geeksforgeeks.org/count-distinct-occurrences-as-a-subsequence/ +--]] +function t2.unique_subsequences(s, t) + local m = #t + local n = #s + + if m > n then + return 0 + end + + local dp = {} + do + local zeros, ones = {}, {} + for _ = 1, n + 1 do + table.insert(zeros, 0) + table.insert(ones, 1) + end + for i = 1, m + 1 do + if i == 1 then + table.insert(dp, {table.unpack(ones)}) + else + table.insert(dp, {table.unpack(zeros)}) + end + end + end + + for i = 2, m + 1 do + for j = 2, n + 1 do + if t:sub(i - 1, i - 1) ~= s:sub(j - 1, j - 1) then + dp[i][j] = dp[i][j - 1] + else + dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] + end + end + end + + return dp[m + 1][n + 1] +end + +function t2.run(args) + local s, t + if #args > 0 then + s, t = args[1], args[2] + else + s, t = table.unpack(t2.DEFAULT_INPUT) + end + + print(t2.unique_subsequences(s, t)) +end + +return t2 diff --git a/challenge-099/tyler-wardhaugh/lua/run.lua b/challenge-099/tyler-wardhaugh/lua/run.lua new file mode 100755 index 0000000000..c6e7473bee --- /dev/null +++ b/challenge-099/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-099/tyler-wardhaugh/lua/test.lua b/challenge-099/tyler-wardhaugh/lua/test.lua new file mode 100755 index 0000000000..997d732f23 --- /dev/null +++ b/challenge-099/tyler-wardhaugh/lua/test.lua @@ -0,0 +1,22 @@ +#!/usr/bin/env lua + +require 'busted.runner'() + +describe("Task 1, Pattern Match", function() + local t1 = require'ch-1' + it("produces correct results for the examples", function() + assert.are.truthy(t1.pattern_match("abcde", "a*e")) + assert.are.falsy(t1.pattern_match("abcde", "a*d")) + assert.are.falsy(t1.pattern_match("abcde", "?b*d")) + assert.are.truthy(t1.pattern_match("abcde", "a*c?e")) + end) +end) + + +describe("Task 2, Unique Subsequences", function() + local t2 = require'ch-2' + it("produces correct results for the examples", function() + assert.are.same(5, t2.unique_subsequences("littleit", "lit")) + assert.are.same(3, t2.unique_subsequences("london", "lon")) + end) +end) diff --git a/challenge-099/tyler-wardhaugh/python/README.md b/challenge-099/tyler-wardhaugh/python/README.md index 976f770899..da9be25946 100644 --- a/challenge-099/tyler-wardhaugh/python/README.md +++ b/challenge-099/tyler-wardhaugh/python/README.md @@ -1,7 +1,7 @@ # The Weekly Challenge -The Weekly Challenge - #096 - Tyler Wardhaugh +The Weekly Challenge - #099 - Tyler Wardhaugh ## Usage @@ -10,11 +10,11 @@ Ensure requirements are satified (ideally in venv): Run Task 1: - $ ./ch1.py S + $ ./ch1.py S P Run Task 2: - $ ./ch2.py S1 S2 + $ ./ch2.py S T Run the project's tests (all the samples from the task descriptions plus some others): diff --git a/challenge-099/tyler-wardhaugh/python/ch-1.py b/challenge-099/tyler-wardhaugh/python/ch-1.py new file mode 100755 index 0000000000..99cab7c794 --- /dev/null +++ b/challenge-099/tyler-wardhaugh/python/ch-1.py @@ -0,0 +1,29 @@ +#!/usr/bin/env python3 +"""Challenge 99, Task 1""" + +import sys +from fnmatch import fnmatch + + +DEFAULT_INPUT = ('abcde', 'a*e') + + +def pattern_match(string, pattern): + """Return true if pattern p matches string s, according to glob rules.""" + return fnmatch(string, pattern) + + +def main(args=None): + """Run the task""" + if args is None: + args = sys.argv[1:] + + s, p = args[0:1] if args else DEFAULT_INPUT + if pattern_match(s, p): + print(1) + else: + print(0) + + +if __name__ == '__main__': + sys.exit(main()) diff --git a/challenge-099/tyler-wardhaugh/python/ch-2.py b/challenge-099/tyler-wardhaugh/python/ch-2.py new file mode 100755 index 0000000000..5bceca3c51 --- /dev/null +++ b/challenge-099/tyler-wardhaugh/python/ch-2.py @@ -0,0 +1,53 @@ +#!/usr/bin/env python3 +"""Challenge 99, Task 2""" + +import sys +import numpy as np + + +DEFAULT_INPUT = ('littleit', 'lit') + + +def unique_subsequences(s, t): + """Use a dynamic programming algorithm to solve unique subsequences. + Source: https://www.geeksforgeeks.org/count-distinct-occurrences-as-a-subsequence/""" + + m = len(t) + n = len(s) + + if m > n: + return 0 + + # NumPy is overkill for this use case, especially since we're not taking + # advantage of any high-performance array manipulations, but I wanted to + # show its use. + dp = np.zeros((m + 1, n + 1), dtype=int) + dp[0, :] = np.ones(n + 1) + + with np.nditer(dp, flags=['multi_index'], order='C') as it: + while not it.finished: + i, j = it.multi_index + it.iternext() + + if i == 0 or j == 0: + continue + + if t[i - 1] != s[j - 1]: + dp[i][j] = dp[i][j - 1] + else: + dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1] + + return dp[m][n] + + +def main(args=None): + """Run the task""" + if args is None: + args = sys.argv[1:] + + s, t = args[0:1] if args else DEFAULT_INPUT + print(unique_subsequences(s, t)) + + +if __name__ == '__main__': + sys.exit(main()) diff --git a/challenge-099/tyler-wardhaugh/python/ch1.py b/challenge-099/tyler-wardhaugh/python/ch1.py new file mode 120000 index 0000000000..7680b02e4f --- /dev/null +++ b/challenge-099/tyler-wardhaugh/python/ch1.py @@ -0,0 +1 @@ +ch-1.py
\ No newline at end of file diff --git a/challenge-099/tyler-wardhaugh/python/ch2.py b/challenge-099/tyler-wardhaugh/python/ch2.py new file mode 120000 index 0000000000..13a132b99f --- /dev/null +++ b/challenge-099/tyler-wardhaugh/python/ch2.py @@ -0,0 +1 @@ +ch-2.py
\ No newline at end of file diff --git a/challenge-099/tyler-wardhaugh/python/requirements.txt b/challenge-099/tyler-wardhaugh/python/requirements.txt new file mode 100644 index 0000000000..a39ae54275 --- /dev/null +++ b/challenge-099/tyler-wardhaugh/python/requirements.txt @@ -0,0 +1 @@ +numpy==1.20.1 diff --git a/challenge-099/tyler-wardhaugh/python/test_ch1.py b/challenge-099/tyler-wardhaugh/python/test_ch1.py new file mode 100755 index 0000000000..94e18be7b3 --- /dev/null +++ b/challenge-099/tyler-wardhaugh/python/test_ch1.py @@ -0,0 +1,17 @@ +#!/usr/bin/env python3 + +import unittest +from ch1 import pattern_match + +class TestTask1(unittest.TestCase): + + + def test_example_cases(self): + self.assertTrue(pattern_match("abcde", "a*e")) + self.assertFalse(pattern_match("abcde", "a*d")) + self.assertFalse(pattern_match("abcde", "?b*d")) + self.assertTrue(pattern_match("abcde", "a*c?e")) + + +if __name__ == '__main__': + unittest.main() diff --git a/challenge-099/tyler-wardhaugh/python/test_ch2.py b/challenge-099/tyler-wardhaugh/python/test_ch2.py new file mode 100755 index 0000000000..968a4fe8e4 --- /dev/null +++ b/challenge-099/tyler-wardhaugh/python/test_ch2.py @@ -0,0 +1,15 @@ +#!/usr/bin/env python3 + +import unittest +from ch2 import unique_subsequences + +class TestTask2(unittest.TestCase): + + + def test_example_cases(self): + self.assertEqual(5, unique_subsequences('littleit', 'lit')) + self.assertEqual(3, unique_subsequences('london', 'lon')) + + +if __name__ == '__main__': + unittest.main() |