Merge pull request #3503 from tylerw/tw/challenge-099

Challenge 099

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()