Merge pull request #3328 from tylerw/tw/challenge-096

Challenge 096

20 files changed, 372 insertions, 20 deletions

diff --git a/challenge-096/tyler-wardhaugh/clojure/README.md b/challenge-096/tyler-wardhaugh/clojure/README.md
index c83f0cfefa..0e314a09c0 100644
--- a/challenge-096/tyler-wardhaugh/clojure/README.md
+++ b/challenge-096/tyler-wardhaugh/clojure/README.md
@@ -1,13 +1,13 @@
-# tw.weekly.c92
+# tw.weekly.c96
 
 
-The Weekly Challenge - #092 - Tyler Wardhaugh
+The Weekly Challenge - #096 - Tyler Wardhaugh
 
 ## Usage
 
 Run the project directly (shows default output from both tasks):
 
-    $ clojure -M -m tw.weekly.c92.core
+    $ clojure -M -m tw.weekly.c96.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.c92.t1 A B
+    $ clojure -M -m tw.weekly.c96.t1 S
 
 Run Task #2:
 
-    $ clojure -M -m tw.weekly.c92.t2 N S
+    $ clojure -M -m tw.weekly.c96.t2 S1 S2
 
 ## Project Template
 
diff --git a/challenge-096/tyler-wardhaugh/clojure/deps.edn b/challenge-096/tyler-wardhaugh/clojure/deps.edn
index 12e0c0d36b..3702e967c4 100644
--- a/challenge-096/tyler-wardhaugh/clojure/deps.edn
+++ b/challenge-096/tyler-wardhaugh/clojure/deps.edn
@@ -1,6 +1,5 @@
 {:paths ["src" "resources"]
- :deps {org.clojure/clojure {:mvn/version "1.10.1"}
-        org.clojure/data.finger-tree {:mvn/version "0.0.3"}}
+ :deps {org.clojure/clojure {:mvn/version "1.10.1"}}
  :aliases
  {:test {:extra-paths ["test"]
          :extra-deps {org.clojure/test.check {:mvn/version "1.0.0"}}}
@@ -10,6 +9,6 @@
                  :sha "f7ef16dc3b8332b0d77bc0274578ad5270fbfedd"}}
    :main-opts ["-m" "cognitect.test-runner"
                "-d" "test"]}
-  :uberjar {:extra-deps {seancorfield/depstar {:mvn/version "1.0.95"}}
-            :main-opts ["-m" "hf.depstar.uberjar" "tw.weekly.c95.jar"
-                        "-C" "-m" "tw.weekly.c95"]}}}
+  :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"]}}}
diff --git a/challenge-096/tyler-wardhaugh/clojure/pom.xml b/challenge-096/tyler-wardhaugh/clojure/pom.xml
index 92317a848c..04154a698d 100644
--- a/challenge-096/tyler-wardhaugh/clojure/pom.xml
+++ b/challenge-096/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.c94</artifactId>
+  <artifactId>tw.weekly.c96</artifactId>
   <version>0.1.0-SNAPSHOT</version>
-  <name>tw.weekly.c94</name>
-  <description>Challenge #094</description>
-  <url>https://github.com/tw.weekly/tw.weekly.c94</url>
+  <name>tw.weekly.c96</name>
+  <description>Challenge #096</description>
+  <url>https://github.com/tw.weekly/tw.weekly.c96</url>
   <licenses>
     <license>
       <name>Eclipse Public License</name>
@@ -19,9 +19,9 @@
     </developer>
   </developers>
   <scm>
-    <url>https://github.com/tw.weekly/tw.weekly.c94</url>
-    <connection>scm:git:git://github.com/tw.weekly/tw.weekly.c94.git</connection>
-    <developerConnection>scm:git:ssh://git@github.com/tw.weekly/tw.weekly.c94.git</developerConnection>
+    <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>
     <tag>HEAD</tag>
   </scm>
   <dependencies>
diff --git a/challenge-096/tyler-wardhaugh/clojure/src/tw/weekly/c96/core.clj b/challenge-096/tyler-wardhaugh/clojure/src/tw/weekly/c96/core.clj
new file mode 100644
index 0000000000..63aeb35497
--- /dev/null
+++ b/challenge-096/tyler-wardhaugh/clojure/src/tw/weekly/c96/core.clj
@@ -0,0 +1,12 @@
+(ns tw.weekly.c96.core
+  (:require [tw.weekly.c96.t1 :as t1])
+  (:require [tw.weekly.c96.t2 :as t2])
+  (:gen-class))
+
+(defn -main
+  "Run all tasks"
+  [& _]
+  (println "Task #1:")
+  (t1/-main)
+  (println "\nTask #2:")
+  (t2/-main))
diff --git a/challenge-096/tyler-wardhaugh/clojure/src/tw/weekly/c96/t1.clj b/challenge-096/tyler-wardhaugh/clojure/src/tw/weekly/c96/t1.clj
new file mode 100644
index 0000000000..9d5ab76cb5
--- /dev/null
+++ b/challenge-096/tyler-wardhaugh/clojure/src/tw/weekly/c96/t1.clj
@@ -0,0 +1,25 @@
+(ns tw.weekly.c96.t1
+  (:require [clojure.edn :as edn]
+            [clojure.string :as str]))
+
+;;;
+; Task description for TASK #1 › Reverse Words
+;;;
+
+(def DEFAULT-INPUT "The Weekly Challenge")
+
+(defn reverse-words
+  "Split a string by spaces and reassemble in reverse word order."
+  [s]
+  (-> s
+      str/trim
+      (str/split #"\s+")
+      reverse
+      (->> (str/join " "))))
+
+(defn -main
+  "Run Task 1 using a string S, defaulting to the example given in
+  the task description."
+  [& args]
+  (let [S (or (some-> args first edn/read-string) DEFAULT-INPUT)]
+    (println (reverse-words S))))
diff --git a/challenge-096/tyler-wardhaugh/clojure/src/tw/weekly/c96/t2.clj b/challenge-096/tyler-wardhaugh/clojure/src/tw/weekly/c96/t2.clj
new file mode 100644
index 0000000000..95e3d9d76e
--- /dev/null
+++ b/challenge-096/tyler-wardhaugh/clojure/src/tw/weekly/c96/t2.clj
@@ -0,0 +1,31 @@
+(ns tw.weekly.c96.t2
+  (:require [clojure.edn :as edn]))
+
+;;;
+; Task description for TASK #2 › Edit Distance
+;;;
+
+(def DEFAULT-INPUT ["kitten" "sitting"])
+
+(defn edit-distance
+  "Compute the minimum operations required to convert S1 to S2."
+  [s1 s2]
+  (let [ed (fn [f [h1 & t1 :as s1] [h2 & t2 :as s2]]
+             (cond
+               (empty? s1) (count s2)
+               (empty? s2) (count s1)
+               (= h1 h2) (f f t1 t2)
+               :else (->> [[t1 s2]
+                           [s1 t2]
+                           [t1 t2]]
+                          (transduce (map (partial apply f f)) min ##Inf)
+                          inc)))
+        ed' (memoize ed)]
+    (ed' ed' (seq s1) (seq s2))))
+
+(defn -main
+  "Run Task 2 using strings S1 and S2, defaulting to the example given in
+  the task description."
+  [& args]
+  (let [[S1 S2] (or (some->> args (take 2) (map edn/read-string)) DEFAULT-INPUT)]
+    (println (edit-distance S1 S2))))
diff --git a/challenge-096/tyler-wardhaugh/clojure/test/tw/weekly/c96_test.clj b/challenge-096/tyler-wardhaugh/clojure/test/tw/weekly/c96_test.clj
new file mode 100644
index 0000000000..1a3eb10dfe
--- /dev/null
+++ b/challenge-096/tyler-wardhaugh/clojure/test/tw/weekly/c96_test.clj
@@ -0,0 +1,16 @@
+(ns tw.weekly.c96-test
+  (:require [clojure.test :refer [deftest is testing]]
+            [tw.weekly.c96.t1 :refer [reverse-words]]
+            [tw.weekly.c96.t2 :refer [edit-distance]]))
+
+(deftest task-1
+  (testing "Task 1, Reverse Words"
+    (is (= "Challenge Weekly The" (reverse-words "The Weekly Challenge")))
+    (is (= "family same the of part are Raku and Perl"
+           (reverse-words
+             "    Perl and   Raku are  part of the same family  ")))))
+
+(deftest task-2
+  (testing "Task 2, Edit Distance"
+    (is (= 3 (edit-distance "kitten" "sitting")))
+    (is (= 2 (edit-distance "sunday" "monday")))))
diff --git a/challenge-096/tyler-wardhaugh/lua/README.md b/challenge-096/tyler-wardhaugh/lua/README.md
index 4898f791cd..b916c3c458 100644
--- a/challenge-096/tyler-wardhaugh/lua/README.md
+++ b/challenge-096/tyler-wardhaugh/lua/README.md
@@ -1,17 +1,17 @@
 
 # The Weekly Challenge
 
-The Weekly Challenge - #095 - Tyler Wardhaugh
+The Weekly Challenge - #096 - Tyler Wardhaugh
 
 ## Usage
 
 Run Task 1:
 
-    $ ./run.lua ch-1 N
+    $ ./run.lua ch-1 S
 
 Run Task 2:
 
-    $ ./run.lua ch-2
+    $ ./run.lua ch-2 S1 S2
 
 Run the project's tests (all the samples from the task descriptions plus some others):
 
diff --git a/challenge-096/tyler-wardhaugh/lua/ch-1.lua b/challenge-096/tyler-wardhaugh/lua/ch-1.lua
new file mode 100755
index 0000000000..6538be9718
--- /dev/null
+++ b/challenge-096/tyler-wardhaugh/lua/ch-1.lua
@@ -0,0 +1,25 @@
+#!/usr/bin/env lua
+
+local t1 = {}
+t1.DEFAULT_INPUT = 'The Weekly Challenge'
+
+function t1.reverse_words(s)
+  local words = {}
+  for word in s:gmatch('%S+') do
+    table.insert(words, 1, word)
+  end
+  return table.concat(words, ' ')
+end
+
+function t1.run(args)
+  local s
+  if #args > 0 then
+    s = args[1]
+  else
+    s = t1.DEFAULT_INPUT
+  end
+
+  print(t1.reverse_words(s))
+end
+
+return t1
diff --git a/challenge-096/tyler-wardhaugh/lua/ch-2.lua b/challenge-096/tyler-wardhaugh/lua/ch-2.lua
new file mode 100755
index 0000000000..c94022f48c
--- /dev/null
+++ b/challenge-096/tyler-wardhaugh/lua/ch-2.lua
@@ -0,0 +1,50 @@
+local t2 = {}
+t2.DEFAULT_INPUT = {'kitten', 'sitting'}
+
+function t2.zeros_matrix(m, n)
+  local matrix = {}
+  for i = 1, m  do
+    matrix[i] = {}
+    for j = 1, n do
+      matrix[i][j] = 0
+    end
+  end
+  return matrix
+  end
+
+function t2.edit_distance(s1, s2)
+  local m = #s1
+  local n = #s2
+  local dp = t2.zeros_matrix(m, n)
+
+  for i = 1, m do
+    for j = 1, n do
+      if i == 1 then
+        dp[i][j] = j
+      elseif j == 1 then
+        dp[i][j] = i
+      elseif s1:sub(i, i) == s2:sub(j, j) then
+        dp[i][j] = dp[i - 1][j - 1]
+      else
+        dp[i][j] = 1 + math.min(dp[i][j - 1],
+                                dp[i - 1][j],
+                                dp[i - 1][j - 1])
+      end
+    end
+  end
+
+  return dp[m][n]
+end
+
+function t2.run(args)
+  local s1, s2
+  if #args > 0 then
+    s1, s2 = args[1], args[2]
+  else
+    s1, s2 = table.unpack(t2.DEFAULT_INPUT)
+  end
+
+  print(t2.edit_distance(s1, s2))
+end
+
+return t2
diff --git a/challenge-096/tyler-wardhaugh/lua/run.lua b/challenge-096/tyler-wardhaugh/lua/run.lua
new file mode 100755
index 0000000000..c6e7473bee
--- /dev/null
+++ b/challenge-096/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-096/tyler-wardhaugh/lua/test.lua b/challenge-096/tyler-wardhaugh/lua/test.lua
new file mode 100755
index 0000000000..f2071e44f2
--- /dev/null
+++ b/challenge-096/tyler-wardhaugh/lua/test.lua
@@ -0,0 +1,21 @@
+#!/usr/bin/env lua
+
+require 'busted.runner'()
+
+describe("Task 1, Reverse Words", function()
+  local t1 = require'ch-1'
+  it("produces correct results for the examples", function()
+    assert.are.same("Challenge Weekly The", t1.reverse_words("The Weekly Challenge"))
+    assert.are.same("family same the of part are Raku and Perl",
+      t1.reverse_words("    Perl and   Raku are  part of the same family  "))
+  end)
+end)
+
+
+describe("Task 2, Edit Distance", function()
+  local t2 = require'ch-2'
+  it("produces correct results for the examples", function()
+    assert.are.same(3, t2.edit_distance("kitten", "sitting"))
+    assert.are.same(2, t2.edit_distance("sunday", "monday"))
+  end)
+end)
diff --git a/challenge-096/tyler-wardhaugh/python/.gitignore b/challenge-096/tyler-wardhaugh/python/.gitignore
new file mode 100644
index 0000000000..b1d9e2517e
--- /dev/null
+++ b/challenge-096/tyler-wardhaugh/python/.gitignore
@@ -0,0 +1,24 @@
+### Python
+# Byte-compiled / optimized / DLL files
+__pycache__/
+*.py[cod]
+*$py.class
+
+# IPython
+profile_default/
+ipython_config.py
+
+# mypy
+.mypy_cache/
+.dmypy.json
+dmypy.json
+
+# Environments
+.env
+.venv
+env/
+venv/
+ENV/
+env.bak/
+venv.bak/
+pythonenv*
diff --git a/challenge-096/tyler-wardhaugh/python/Makefile b/challenge-096/tyler-wardhaugh/python/Makefile
new file mode 100644
index 0000000000..bf7573b58a
--- /dev/null
+++ b/challenge-096/tyler-wardhaugh/python/Makefile
@@ -0,0 +1,13 @@
+.PHONEY: help
+help:
+	@grep -E '^[0-9a-zA-Z_-]+:.*?## .*$$' $(MAKEFILE_LIST) | \
+   sort | \
+   awk 'BEGIN {FS = ":.*?## "}; {printf "\033[36m%-30s\033[0m %s\n", $$1, $$2}'
+
+.PHONEY: test
+test: ## run the test suite
+	@python -m unittest
+
+.PHONEY: satisfy-reqs
+satisfy-reqs: ## ensure the requirements are installed
+	@python -m pip install -r requirements.txt
diff --git a/challenge-096/tyler-wardhaugh/python/README.md b/challenge-096/tyler-wardhaugh/python/README.md
new file mode 100644
index 0000000000..976f770899
--- /dev/null
+++ b/challenge-096/tyler-wardhaugh/python/README.md
@@ -0,0 +1,25 @@
+
+# The Weekly Challenge
+
+The Weekly Challenge - #096 - Tyler Wardhaugh
+
+## Usage
+
+Ensure requirements are satified (ideally in venv):
+    $ make satisfy-reqs
+
+Run Task 1:
+
+    $ ./ch1.py S
+
+Run Task 2:
+
+    $ ./ch2.py S1 S2
+
+Run the project's tests (all the samples from the task descriptions plus some others):
+
+    $ make test
+
+## Requirements:
+*   [Python 3](https://www.python.org/)
+*   [NumPy](https://numpy.org/)
diff --git a/challenge-096/tyler-wardhaugh/python/ch1.py b/challenge-096/tyler-wardhaugh/python/ch1.py
new file mode 100755
index 0000000000..37272382cb
--- /dev/null
+++ b/challenge-096/tyler-wardhaugh/python/ch1.py
@@ -0,0 +1,25 @@
+#!/usr/bin/env python3
+"""Challenge 96, Task 1"""
+
+import sys
+import re
+
+DEFAULT_INPUT = "The Weekly Challenge"
+
+def reverse_words(s):
+    """Split a string s into words and reverse their order."""
+    words = re.split(r'\s+', s.strip())
+    return ' '.join(words[::-1])
+
+
+def main(args=None):
+    """Run the task"""
+    if args is None:
+        args = sys.argv[1:]
+
+    s = args[0] if args else DEFAULT_INPUT
+    print(reverse_words(s))
+
+
+if __name__ == '__main__':
+    sys.exit(main())
diff --git a/challenge-096/tyler-wardhaugh/python/ch2.py b/challenge-096/tyler-wardhaugh/python/ch2.py
new file mode 100755
index 0000000000..e55363e938
--- /dev/null
+++ b/challenge-096/tyler-wardhaugh/python/ch2.py
@@ -0,0 +1,43 @@
+#!/usr/bin/env python3
+"""Challenge 96, Task 2"""
+
+import sys
+import numpy as np
+
+
+DEFAULT_INPUT = ["kitten", "sitting"]
+
+
+def edit_distance(s1, s2):
+    """Determine the edit distance between two strings."""
+    dp = np.zeros((len(s1), len(s2)), dtype=np.int)
+    for i, j in np.ndindex(dp.shape):
+        if i == 0:
+            dp[i][j] = j
+        elif j == 0:
+            dp[i][j] = i
+        elif s1[i - 1] == s2[j - 1]:
+            dp[i][j] = dp[i - 1][j - 1]
+        else:
+            dp[i][j] = 1 + min(dp[i][j - 1],
+                               dp[i - 1][j],
+                               dp[i - 1][j - 1])
+
+    return dp[-1][-1]
+
+
+def main(args=None):
+    """Run the task"""
+    if args is None:
+        args = sys.argv[1:]
+
+    if args:
+        s1, s2 = args[0:2]
+    else:
+        s1, s2 = DEFAULT_INPUT
+
+    print(edit_distance(s1, s2))
+
+
+if __name__ == '__main__':
+    sys.exit(main())
diff --git a/challenge-096/tyler-wardhaugh/python/requirements.txt b/challenge-096/tyler-wardhaugh/python/requirements.txt
new file mode 100644
index 0000000000..1e99151eb7
--- /dev/null
+++ b/challenge-096/tyler-wardhaugh/python/requirements.txt
@@ -0,0 +1 @@
+numpy==1.19.5
diff --git a/challenge-096/tyler-wardhaugh/python/test_ch1.py b/challenge-096/tyler-wardhaugh/python/test_ch1.py
new file mode 100755
index 0000000000..5f27496224
--- /dev/null
+++ b/challenge-096/tyler-wardhaugh/python/test_ch1.py
@@ -0,0 +1,18 @@
+#!/usr/bin/env python3
+
+import unittest
+from ch1 import reverse_words
+
+class TestTask1(unittest.TestCase):
+
+
+    def test_example_cases(self):
+        self.assertEqual(
+                "Challenge Weekly The", reverse_words("The Weekly Challenge"))
+        self.assertEqual(
+                "family same the of part are Raku and Perl",
+                reverse_words("    Perl and   Raku are  part of the same family  "))
+
+
+if __name__ == '__main__':
+    unittest.main()
diff --git a/challenge-096/tyler-wardhaugh/python/test_ch2.py b/challenge-096/tyler-wardhaugh/python/test_ch2.py
new file mode 100755
index 0000000000..4341cbded4
--- /dev/null
+++ b/challenge-096/tyler-wardhaugh/python/test_ch2.py
@@ -0,0 +1,15 @@
+#!/usr/bin/env python3
+
+import unittest
+from ch2 import edit_distance
+
+class TestTask2(unittest.TestCase):
+
+
+    def test_example_cases(self):
+        self.assertEqual(3, edit_distance("kitten", "sitting"))
+        self.assertEqual(2, edit_distance("sunday", "monday"))
+
+
+if __name__ == '__main__':
+    unittest.main()