Ch99 (Lua): Tasks 1 & 2

4 files changed, 136 insertions, 0 deletions

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)