Merge pull request #3323 from Abigail/abigail/week-096

Abigail/week 096

2 files changed, 80 insertions, 0 deletions

diff --git a/challenge-096/abigail/lua/ch-1.lua b/challenge-096/abigail/lua/ch-1.lua
new file mode 100644
index 0000000000..9c4b1de913
--- /dev/null
+++ b/challenge-096/abigail/lua/ch-1.lua
@@ -0,0 +1,14 @@
+for line in io . lines () do
+    --
+    -- Extract words and put them into an array, in reverse.
+    --
+    local words = {}
+    for str in string . gmatch (line, "[^ ]+") do
+        table . insert (words, 1, str)
+    end
+
+    --
+    -- Print the words
+    --
+    io . write (table . concat (words, " "), "\n")
+end
diff --git a/challenge-096/abigail/lua/ch-2.lua b/challenge-096/abigail/lua/ch-2.lua
new file mode 100644
index 0000000000..162f06eef0
--- /dev/null
+++ b/challenge-096/abigail/lua/ch-2.lua
@@ -0,0 +1,66 @@
+--
+-- This is an implementation of the Wagner Fischer algorithm, which
+-- calculates the Levenshtein distance.
+--
+-- See https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm
+--
+function LevenshteinDistance (first, second)
+    local n = first  : len ()
+    local m = second : len ()
+    if n < m
+    then
+        first, second = second, first
+        n,     m      = m,      n
+    end
+    distances = {}
+    for i = 0, n do
+        distances [i] = {}
+        for j = 0, m do
+            if i == 0 or j == 0
+            then
+                distances [i] [j] = i + j
+            else
+                local cost = 1
+                if string . sub (first,  i, i) ==
+                   string . sub (second, j, j)
+                then
+                    cost = 0
+                end
+                distances [i] [j] = math . min (
+                    distances [i - 1] [j]     + 1,
+                    distances [i]     [j - 1] + 1,
+                    distances [i - 1] [j - 1] + cost
+                )
+            end
+        end
+
+        --
+        -- We only need the previous row, so we can return the
+        -- memory of rows before that. This reduces the memory
+        -- usage from O (n * m) to O (min (n, m))
+        --
+        if i > 0
+        then
+            distances [i - 1] = nil
+        end
+    end
+    return distances [n] [m]
+end
+
+
+for line in io . lines () do
+    --
+    -- Extract words and put them into an array.
+    --
+    local words = {}
+    index = 0
+    for str in string . gmatch (line, "[^ ]+") do
+        index = index + 1
+        words [index] = str
+    end
+
+    --
+    -- Calculate the edit distance, and print the result.
+    --
+    io . write (LevenshteinDistance (words [1], words [2]), "\n")
+end