Merge pull request #2485 from tylerw/tw/challenge-081

Challenge 081 in Lua (and improvements to Clojure solutions)

7 files changed, 158 insertions, 4 deletions

diff --git a/challenge-081/tyler-wardhaugh/clojure/src/tw/weekly/c81/t1.clj b/challenge-081/tyler-wardhaugh/clojure/src/tw/weekly/c81/t1.clj
index 13a382f7c6..d170171616 100644
--- a/challenge-081/tyler-wardhaugh/clojure/src/tw/weekly/c81/t1.clj
+++ b/challenge-081/tyler-wardhaugh/clojure/src/tw/weekly/c81/t1.clj
@@ -15,6 +15,7 @@
         is-substring (fn [s] (= large (reduce str (-> (quot large-len (count s)) (repeat s)))))]
     (->> (reductions str "" small)
          (drop 1)
+         (filter #(zero? (rem large-len (count %))))
          (filter is-substring))))
 
 (defn -main
diff --git a/challenge-081/tyler-wardhaugh/lua/README.md b/challenge-081/tyler-wardhaugh/lua/README.md
index c469977934..e629f5866f 100644
--- a/challenge-081/tyler-wardhaugh/lua/README.md
+++ b/challenge-081/tyler-wardhaugh/lua/README.md
@@ -1,17 +1,17 @@
 
 # The Weekly Challenge
 
-The Weekly Challenge - #080 - Tyler Wardhaugh
+The Weekly Challenge - #081 - Tyler Wardhaugh
 
 ## Usage
 
 Run Task 1:
 
-    $ ./run.lua ch-1 5 2 -2 0
+    $ ./run.lua ch-1 S1 S2
 
 Run Task 2:
 
-    $ ./run.lua ch-2 1 2 2
+    $ ./run.lua ch-2 INPUT
 
 Run the project's tests (all the samples from the task descriptions plus some others):
 
@@ -20,4 +20,5 @@ 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/)
-*   [busted](https://olivinelabs.com/busted/) (unit testing framework)
+*   [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-081/tyler-wardhaugh/lua/ch-1.lua b/challenge-081/tyler-wardhaugh/lua/ch-1.lua
new file mode 100755
index 0000000000..8203f05c74
--- /dev/null
+++ b/challenge-081/tyler-wardhaugh/lua/ch-1.lua
@@ -0,0 +1,42 @@
+#!/usr/bin/env lua
+
+local t1 = {}
+
+do
+  local lpeg = require'lpeg'
+  local P = lpeg.P
+  function t1.make_pat(s)
+    return P(s)
+  end
+end
+
+function t1.common_base_string(s1, s2)
+  -- ensure s1 is smaller or equal in length to s2
+  if s1:len() > s2:len() then
+    s1, s2 = s2, s1
+  end
+
+  local s2_len = s2:len()
+  local results, substring, part = {}
+  for i = 1,s2_len do
+    -- skip attempt if s2's length not evenly divisible by i
+    if s2_len % i ~= 0 then goto continue end
+
+    substring = s2:sub(1, s2_len // i)
+    part = t1.make_pat(substring)
+    if (part^i):match(s2) and (part^1 * -1):match(s1) then
+      table.insert(results, substring)
+    end
+    ::continue::
+  end
+
+  return results
+end
+
+function t1.run(args)
+  local S1, S2 = table.unpack(args, 1, 2)
+  local bases = t1.common_base_string(S1, S2)
+  print(table.concat(bases, " "))
+end
+
+return t1
diff --git a/challenge-081/tyler-wardhaugh/lua/ch-2.lua b/challenge-081/tyler-wardhaugh/lua/ch-2.lua
new file mode 100755
index 0000000000..49b5732fb1
--- /dev/null
+++ b/challenge-081/tyler-wardhaugh/lua/ch-2.lua
@@ -0,0 +1,73 @@
+#!/usr/bin/env lua
+
+--[[
+   An iterator over a table yielding keys (and their corresponding values) in
+   sorted order.
+
+   source: ideas from "keysToList" (and others) in:
+      http://lua-users.org/wiki/SortedIteration
+]]--
+function ordered_pairs(tbl, cmp)
+  local o = {}
+  for k, _ in pairs(tbl) do table.insert(o, k) end
+  table.sort(o, cmp)
+
+  local i = 0
+  return function()
+    i = i + 1
+    return o[i], tbl[o[i]]
+  end
+end
+
+local t2 = {}
+
+do
+  local lpeg = require'lpeg'
+  lpeg.locale(lpeg)
+  local C, Cs, Ct, P, S = lpeg.C, lpeg.Cs, lpeg.Ct, lpeg.P, lpeg.S
+
+  local strip = (S[[."(),]] + P"'s" + P"--" + P"\n")
+  t2.sanitizer = Cs((strip / " " + 1)^0)
+
+  local space = lpeg.space^1
+  local word = C((1 - space)^1)
+  t2.wordify = Ct(word * (space * word)^0)
+end
+
+function t2.frequency_sort(text)
+  local sanitized = t2.sanitizer:match(text)
+  local words = t2.wordify:match(sanitized)
+
+  local count = {}
+  for _, v in ipairs(words) do count[v] = (count[v] or 0) + 1 end
+
+  local invert = {}
+  for k, v in pairs(count) do
+    if invert[v] then
+      table.insert(invert[v], k)
+    else
+      invert[v] = {k}
+    end
+  end
+
+  for _, v in pairs(invert) do table.sort(v) end
+
+  return invert
+end
+
+function t2.slurp(input)
+  local fh = assert(io.open(input, "r"))
+  local text = fh:read("*all")
+  fh:close()
+  return text
+end
+
+function t2.run(args)
+  local input = args[1]
+  local results = t2.frequency_sort(t2.slurp(input))
+  for k, v in ordered_pairs(results) do
+    print(k, table.concat(v, " "), "\n")
+  end
+end
+
+return t2
diff --git a/challenge-081/tyler-wardhaugh/lua/resources/input b/challenge-081/tyler-wardhaugh/lua/resources/input
new file mode 100644
index 0000000000..37001629ad
--- /dev/null
+++ b/challenge-081/tyler-wardhaugh/lua/resources/input
@@ -0,0 +1,3 @@
+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-081/tyler-wardhaugh/lua/run.lua b/challenge-081/tyler-wardhaugh/lua/run.lua
new file mode 100755
index 0000000000..c6e7473bee
--- /dev/null
+++ b/challenge-081/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-081/tyler-wardhaugh/lua/test.lua b/challenge-081/tyler-wardhaugh/lua/test.lua
new file mode 100755
index 0000000000..0874b984cc
--- /dev/null
+++ b/challenge-081/tyler-wardhaugh/lua/test.lua
@@ -0,0 +1,25 @@
+#!/usr/bin/env lua
+
+require 'busted.runner'()
+
+describe("Task 1, Common Base String", function()
+  local t1 = require'ch-1'
+  it("produces correct results for the examples", function()
+    assert.are.same(t1.common_base_string("abcdabcd", "abcdabcdabcdabcd"), {"abcdabcd", "abcd"})
+    assert.are.same(t1.common_base_string("aaa", "aa"), {"a"})
+  end)
+end)
+
+describe("Task 2, Frequency Sort", function()
+  local t2  = require'ch-2'
+  it("produces correct results for the examples", function()
+    local expected = {
+      [1]={"But", "City", "It", "Jet", "Juliet", "Latino", "New", "Romeo", "Side", "Story", "Their", "Then", "West", "York", "adaptation", "any", "anything", "at", "award-winning", "away", "become", "before", "begin", "best", "classic", "climactic", "coexist", "control", "dance", "do", "doesn't", "end", "ending", "escalates", "families", "feuding", "form", "former", "friend", "gains", "gangs", "goes", "happened", "hatred", "heartbreaking", "highway", "hoping", "in", "know", "love", "lovers", "meet", "meeting", "neither", "no", "one", "plan", "planning", "point", "romantic", "rumble", "run", "secret", "sends", "sister", "streets", "strikes", "terribly", "their", "two", "under", "understanding", "until", "violence", "warring", "what", "when", "where", "white", "whoever", "wins", "with", "wrong", "younger"},
+      [2]={"Bernardo", "Jets", "Riff", "Sharks", "The", "by", "it", "led", "tragedy"},
+      [3]={"Maria", "Tony", "a", "can", "of", "stop"},
+      [4]={"to"},
+      [9]={"and", "the"}
+    }
+    assert.are.same(t2.frequency_sort(t2.slurp("resources/input")), expected)
+  end)
+end)