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

Challenge 096

1 files changed, 50 insertions, 0 deletions

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