Merge pull request #3619 from tylerw/tw/challenge-101

Challenge 101

16 files changed, 312 insertions, 15 deletions

diff --git a/challenge-101/tyler-wardhaugh/clojure/README.md b/challenge-101/tyler-wardhaugh/clojure/README.md
index f978c858a6..372957fa28 100644
--- a/challenge-101/tyler-wardhaugh/clojure/README.md
+++ b/challenge-101/tyler-wardhaugh/clojure/README.md
@@ -1,13 +1,13 @@
-# tw.weekly.c100
+# tw.weekly.c101
 
 
-The Weekly Challenge - #100 - Tyler Wardhaugh
+The Weekly Challenge - #101 - Tyler Wardhaugh
 
 ## Usage
 
 Run the project directly (shows default output from both tasks):
 
-    $ clojure -M -m tw.weekly.c100.core
+    $ clojure -M -m tw.weekly.c101.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.c100.t1 T
+    $ clojure -M -m tw.weekly.c101.t1 A
 
 Run Task #2 with input:
 
-    $ clojure -M -m tw.weekly.c100.t2 T
+    $ clojure -M -m tw.weekly.c101.t2 A B C
 
 ## Project Template
 
diff --git a/challenge-101/tyler-wardhaugh/clojure/deps.edn b/challenge-101/tyler-wardhaugh/clojure/deps.edn
index c245240206..5a7bdda9e2 100644
--- a/challenge-101/tyler-wardhaugh/clojure/deps.edn
+++ b/challenge-101/tyler-wardhaugh/clojure/deps.edn
@@ -1,6 +1,7 @@
 {:paths ["src" "resources"]
  :deps {org.clojure/clojure {:mvn/version "1.10.1"}
-        clojure.java-time {:mvn/version "0.3.2"}}
+        org.clojure/math.numeric-tower {:mvn/version "0.0.4"}
+        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"}}}
diff --git a/challenge-101/tyler-wardhaugh/clojure/pom.xml b/challenge-101/tyler-wardhaugh/clojure/pom.xml
index eb6b9afc9c..f3c877ab99 100644
--- a/challenge-101/tyler-wardhaugh/clojure/pom.xml
+++ b/challenge-101/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.c100</artifactId>
+  <artifactId>tw.weekly.c101</artifactId>
   <version>0.1.0-SNAPSHOT</version>
-  <name>tw.weekly.c100</name>
-  <description>Challenge #100</description>
-  <url>https://github.com/tw.weekly/tw.weekly.c100</url>
+  <name>tw.weekly.c101</name>
+  <description>Challenge #101</description>
+  <url>https://github.com/tw.weekly/tw.weekly.c101</url>
   <licenses>
     <license>
       <name>Eclipse Public License</name>
@@ -19,9 +19,9 @@
     </developer>
   </developers>
   <scm>
-    <url>https://github.com/tw.weekly/tw.weekly.c100</url>
-    <connection>scm:git:git://github.com/tw.weekly/tw.weekly.c100.git</connection>
-    <developerConnection>scm:git:ssh://git@github.com/tw.weekly/tw.weekly.c100.git</developerConnection>
+    <url>https://github.com/tw.weekly/tw.weekly.c101</url>
+    <connection>scm:git:git://github.com/tw.weekly/tw.weekly.c101.git</connection>
+    <developerConnection>scm:git:ssh://git@github.com/tw.weekly/tw.weekly.c101.git</developerConnection>
     <tag>HEAD</tag>
   </scm>
   <dependencies>
@@ -30,6 +30,16 @@
       <artifactId>clojure</artifactId>
       <version>1.10.1</version>
     </dependency>
+    <dependency>
+      <groupId>org.clojure</groupId>
+      <artifactId>math.numeric-tower</artifactId>
+      <version>0.0.4</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-101/tyler-wardhaugh/clojure/src/tw/weekly/c101/core.clj b/challenge-101/tyler-wardhaugh/clojure/src/tw/weekly/c101/core.clj
new file mode 100644
index 0000000000..216602a2a6
--- /dev/null
+++ b/challenge-101/tyler-wardhaugh/clojure/src/tw/weekly/c101/core.clj
@@ -0,0 +1,12 @@
+(ns tw.weekly.c101.core
+  (:require [tw.weekly.c101.t1 :as t1])
+  (:require [tw.weekly.c101.t2 :as t2])
+  (:gen-class))
+
+(defn -main
+  "Run all tasks"
+  [& _]
+  (println "Task #1:")
+  (t1/-main)
+  (println "\nTask #2:")
+  (t2/-main))
diff --git a/challenge-101/tyler-wardhaugh/clojure/src/tw/weekly/c101/t1.clj b/challenge-101/tyler-wardhaugh/clojure/src/tw/weekly/c101/t1.clj
new file mode 100644
index 0000000000..be5ec63b41
--- /dev/null
+++ b/challenge-101/tyler-wardhaugh/clojure/src/tw/weekly/c101/t1.clj
@@ -0,0 +1,47 @@
+(ns tw.weekly.c101.t1
+  (:require [clojure.edn :as edn]
+            [clojure.core.matrix :as m]
+            [clojure.math.numeric-tower :as math]
+            [tw.weekly.util.matrix :as um]))
+
+;;;
+; Task description for TASK #1 › Pack a Spiral
+;;;
+
+(def DEFAULT-INPUT [1 2 3 4])
+
+(defn get-min-size
+  "Determine the minimum shape necessary for a matrix to hold len items."
+  [len]
+  (let [source (range 1 (inc (quot len 2)))
+        xf (comp
+             (filter #(zero? (mod len %1)))
+             (map (juxt #(math/abs (- % (quot len %))) identity)))
+        f (partial min-key first)]
+    (->> source
+         (transduce xf (completing f) [len len])
+         second
+         ((juxt identity (partial quot len))))))
+
+(defn- pack
+  "Recursively pack an incoming coll into an m x n spiral matrix. This is a
+  helper function for pack-spiral, not meant to be called directly."
+  [coll m n]
+  (condp = 1
+    m (vector coll)
+    n (map vector (reverse coll))
+    (m/join (um/rotate-matrix (pack (drop n coll) n (dec m)))
+            (vector (take n coll)))))
+
+(defn pack-spiral
+  "Return coll as a packed spiral matrix."
+  [coll]
+  (let [[m n] (get-min-size (count coll))]
+    (m/matrix (pack coll m n))))
+
+(defn -main
+  "Run Task 1 using a list A, defaulting to the example given in the task
+  description."
+  [& args]
+  (let [A (or (some-> args first edn/read-string) DEFAULT-INPUT)]
+    (um/print-matrix (pack-spiral A))))
diff --git a/challenge-101/tyler-wardhaugh/clojure/src/tw/weekly/c101/t2.clj b/challenge-101/tyler-wardhaugh/clojure/src/tw/weekly/c101/t2.clj
new file mode 100644
index 0000000000..a74ca720f4
--- /dev/null
+++ b/challenge-101/tyler-wardhaugh/clojure/src/tw/weekly/c101/t2.clj
@@ -0,0 +1,28 @@
+(ns tw.weekly.c101.t2
+  (:require [clojure.edn :as edn]))
+
+;;;
+; Task description for TASK #2 › Origin-containing Triangle
+;;;
+
+(def DEFAULT-INPUT [[0 1] [1 0] [2 2]])
+
+(defn contains-origin
+  "Determine if the triangle formed by the given three points cover the (0,0)
+  origin on a 2D plane, using the Barycentric Coordinate Sytem method from
+  https://totologic.blogspot.com/2014/01/accurate-point-in-triangle-test.html"
+  [[x1 y1] [x2 y2] [x3 y3]]
+  (let [denominator (+ (* (- y2 y3) (- x1 x3)) (* (- x3 x2) (- y1 y3)))
+        A (/ (+ (* (- y2 y3) (- x3)) (* (- x3 x2) (- y3))) denominator)
+        B (/ (+ (* (- y3 y1) (- x3)) (* (- x1 x3) (- y3))) denominator)
+        C (- 1 A B)]
+    (and (<= 0 A) (<= A 1)
+         (<= 0 B) (<= B 1)
+         (<= 0 C) (<= C 1))))
+
+(defn -main
+  "Run Task 2 points A, B, and C; defaulting to the example given in the
+  task description."
+  [& args]
+  (let [[A B C] (or (some->> args (take 3) (map edn/read-string)) DEFAULT-INPUT)]
+    (println (if (contains-origin A B C) 1 0))))
diff --git a/challenge-101/tyler-wardhaugh/clojure/src/tw/weekly/util/matrix.clj b/challenge-101/tyler-wardhaugh/clojure/src/tw/weekly/util/matrix.clj
new file mode 100644
index 0000000000..1754c558c5
--- /dev/null
+++ b/challenge-101/tyler-wardhaugh/clojure/src/tw/weekly/util/matrix.clj
@@ -0,0 +1,20 @@
+(ns tw.weekly.util.matrix
+  (:require [clojure.pprint :as pp]
+            [clojure.string :as str]
+            [clojure.core.matrix :as m]))
+
+(defn rotate-matrix
+  "Rotate a matrix counterclockwise"
+  [mat]
+  (-> mat m/transpose reverse))
+
+(defn print-matrix
+  "Pretty print a matrix"
+  [mat]
+  (let [ks (range (m/dimension-count mat 1))
+        tbl (with-out-str
+              (pp/print-table ks (map (partial zipmap ks) mat)))]
+    (-> tbl
+        (str/split #"\n")
+        (->> (drop 3)
+             (run! println)))))
diff --git a/challenge-101/tyler-wardhaugh/clojure/test/tw/weekly/c101_test.clj b/challenge-101/tyler-wardhaugh/clojure/test/tw/weekly/c101_test.clj
new file mode 100644
index 0000000000..8535bdf99d
--- /dev/null
+++ b/challenge-101/tyler-wardhaugh/clojure/test/tw/weekly/c101_test.clj
@@ -0,0 +1,16 @@
+(ns tw.weekly.c101-test
+  (:require [clojure.test :refer [deftest is testing]]
+            [tw.weekly.c101.t1 :refer [pack-spiral]]
+            [tw.weekly.c101.t2 :refer [contains-origin]]))
+
+(deftest task-1
+  (testing "Task 1, Pack a Spiral"
+    (is (= [[4 3] [1 2]] (pack-spiral [1 2 3 4])))
+    (is (= [[5 4] [6 3] [1 2]] (pack-spiral (range 1 7))))
+    (is (= [[8 7 6] [9 12 5] [10 11 4] [1 2 3]] (pack-spiral (range 1 13))))))
+
+(deftest task-2
+  (testing "Task 2, Origin-containing Triangle"
+    (is (false? (apply contains-origin [[0 1] [1 0] [2 2]])))
+    (is (true? (apply contains-origin [[1 1] [-1 1] [0 -3]])))
+    (is (true? (apply contains-origin [[0 1] [2 0] [-6 0]])))))
diff --git a/challenge-101/tyler-wardhaugh/python/README.md b/challenge-101/tyler-wardhaugh/python/README.md
index d540b43280..3b9306245e 100644
--- a/challenge-101/tyler-wardhaugh/python/README.md
+++ b/challenge-101/tyler-wardhaugh/python/README.md
@@ -10,11 +10,16 @@ Ensure requirements are satified (ideally in venv):
 
 Run Task 1:
 
-    $ ./ch1.py T
+    $ ./ch1.py COLL
+    # e.g.:
+    $ ./ch-1.py "[1, 2, 3, 4, 5, 6]"
+
 
 Run Task 2:
 
-    $ ./ch2.py T
+    $ ./ch2.py POINTS
+    # e.g.:
+    $ ./ch2.py "[[0, 1], [2,0], [-6, 0]]"
 
 Run the project's tests (all the samples from the task descriptions plus some others):
 
diff --git a/challenge-101/tyler-wardhaugh/python/ch-1.py b/challenge-101/tyler-wardhaugh/python/ch-1.py
new file mode 100755
index 0000000000..963f7ef319
--- /dev/null
+++ b/challenge-101/tyler-wardhaugh/python/ch-1.py
@@ -0,0 +1,74 @@
+#!/usr/bin/env python3
+"""Challenge 101, Task 1"""
+
+import sys
+
+
+DEFAULT_INPUT = [1, 2, 3, 4]
+
+
+def print_matrix(mat, colsep=' '):
+    """Pretty print a matrix (list of lists)"""
+    strs = [[str(x) for x in row] for row in mat]
+    lens = [max(len(x) for x in col) for col in zip(*strs)]
+    fmt = colsep.join(f'{{:{x}}}' for x in lens)
+    tbl = (fmt.format(*row) for row in strs)
+
+    for row in tbl:
+        print(row)
+
+
+def get_min_size(coll_len):
+    """Determine the minimum shape necessary for a matrix to hold len items."""
+    f = lambda x: abs(x - coll_len // x)
+    candidates = {x: f(x) for x in range(1, 1+coll_len) if coll_len % x == 0}
+
+    rows = min(candidates, key=candidates.get)
+    cols = coll_len // rows
+    return rows, cols
+
+
+def rotate_matrix(mat):
+    """Rotate the matrix counterclockwise"""
+    rotated_mat = [list(x) for x in zip(*mat)]
+    rotated_mat.reverse()
+    return rotated_mat
+
+
+
+def _pack(coll, m, n):
+    """Recursively pack an incoming coll into an m x n spiral matrix. This is a
+    helper function for pack_spiral, not meant to be called directly."""
+    if m == 1:
+        yield [coll]
+    elif n == 1:
+        yield from ([x] for x in reversed(coll))
+    else:
+        result = rotate_matrix(list(_pack(coll[n:], n, m-1))) + [coll[:n]]
+        yield from result
+
+
+def pack_spiral(coll):
+    """Return coll as a packed spiral matrix."""
+    m, n = get_min_size(len(coll))
+    spiral = list(_pack(coll, m, n))
+    return spiral
+
+
+def main(args=None):
+    """Run the task"""
+    if args is None:
+        args = sys.argv[1:]
+
+    coll = None
+    if args:
+        import json
+        coll = json.loads(args[0])
+    else:
+        coll = DEFAULT_INPUT
+
+    print_matrix(pack_spiral(coll))
+
+
+if __name__ == '__main__':
+    sys.exit(main())
diff --git a/challenge-101/tyler-wardhaugh/python/ch-2.py b/challenge-101/tyler-wardhaugh/python/ch-2.py
new file mode 100755
index 0000000000..2f38f93038
--- /dev/null
+++ b/challenge-101/tyler-wardhaugh/python/ch-2.py
@@ -0,0 +1,41 @@
+#!/usr/bin/env python3
+"""Challenge 101, Task 2"""
+
+import sys
+
+
+DEFAULT_INPUT = [[0, 1], [1, 0], [2, 2]]
+
+
+def contains_origin(triangle):
+    """Determine if the triangle formed by the given three points cover the (0,0)
+    origin on a 2D plane, using the Barycentric Coordinate Sytem method from
+    https://totologic.blogspot.com/2014/01/accurate-point-in-triangle-test.html"""
+    (x1, y1), (x2, y2), (x3, y3) = triangle
+
+    denominator = (y2 - y3) * (x1 - x3) + (x3 - x2) * (y1 - y3)
+    A = ((y2 - y3) * (0 - x3) + (x3 - x2) * (0 - y3)) / denominator
+    B = ((y3 - y1)*(0 - x3) + (x1 - x3)*(0 - y3)) / denominator
+    C = 1 - A - B
+
+    return all(0 <= x <= 1 for x in [A, B, C])
+
+
+def main(args=None):
+    """Run the task"""
+    if args is None:
+        args = sys.argv[1:]
+
+    triangle = None
+    if args:
+        import json
+        triangle = json.loads(args[0])
+    else:
+        triangle = DEFAULT_INPUT
+
+    result = 1 if contains_origin(triangle) else 0
+    print(result)
+
+
+if __name__ == '__main__':
+    sys.exit(main())
diff --git a/challenge-101/tyler-wardhaugh/python/ch1.py b/challenge-101/tyler-wardhaugh/python/ch1.py
new file mode 120000
index 0000000000..7680b02e4f
--- /dev/null
+++ b/challenge-101/tyler-wardhaugh/python/ch1.py
@@ -0,0 +1 @@
+ch-1.py
\ No newline at end of file
diff --git a/challenge-101/tyler-wardhaugh/python/ch2.py b/challenge-101/tyler-wardhaugh/python/ch2.py
new file mode 120000
index 0000000000..13a132b99f
--- /dev/null
+++ b/challenge-101/tyler-wardhaugh/python/ch2.py
@@ -0,0 +1 @@
+ch-2.py
\ No newline at end of file
diff --git a/challenge-101/tyler-wardhaugh/python/requirements.txt b/challenge-101/tyler-wardhaugh/python/requirements.txt
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/challenge-101/tyler-wardhaugh/python/requirements.txt
diff --git a/challenge-101/tyler-wardhaugh/python/test_ch1.py b/challenge-101/tyler-wardhaugh/python/test_ch1.py
new file mode 100755
index 0000000000..9355f68556
--- /dev/null
+++ b/challenge-101/tyler-wardhaugh/python/test_ch1.py
@@ -0,0 +1,22 @@
+#!/usr/bin/env python3
+"""Test Task 1"""
+
+import unittest
+from ch1 import pack_spiral
+
+
+class TestTask1(unittest.TestCase):
+    """Test Task 1"""
+
+    def test_example_cases(self):
+        """Test Task 1"""
+        self.assertEqual([[4, 3], [1, 2]],
+                         pack_spiral(list(range(1, 5))))
+        self.assertEqual([[6, 5, 4], [1, 2, 3]],
+                         pack_spiral(list(range(1, 7))))
+        self.assertEqual([[9, 8, 7, 6], [10, 11, 12, 5], [1, 2, 3, 4]],
+                         pack_spiral(list(range(1, 13))))
+
+
+if __name__ == '__main__':
+    unittest.main()
diff --git a/challenge-101/tyler-wardhaugh/python/test_ch2.py b/challenge-101/tyler-wardhaugh/python/test_ch2.py
new file mode 100755
index 0000000000..9cbce4b371
--- /dev/null
+++ b/challenge-101/tyler-wardhaugh/python/test_ch2.py
@@ -0,0 +1,19 @@
+#!/usr/bin/env python3
+"""Test Task 2"""
+
+import unittest
+from ch2 import contains_origin
+
+
+class TestTask2(unittest.TestCase):
+    """Test Task 2"""
+
+    def test_example_cases(self):
+        """Test Task 2"""
+        self.assertFalse(contains_origin([[0, 1], [1, 0], [2, 2]]))
+        self.assertTrue(contains_origin([[1, 1], [-1, 1], [0, -3]]))
+        self.assertTrue(contains_origin([[0, 1], [2, 0], [-6, 0]]))
+
+
+if __name__ == '__main__':
+    unittest.main()