Ch99 (Lua): Tasks 1 & 2

1 files changed, 56 insertions, 0 deletions

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