From 6a8e97190d55b1e0f94318e4e0316e50de7415c0 Mon Sep 17 00:00:00 2001
From: Abigail <abigail@abigail.be>
Date: Tue, 19 Jan 2021 13:43:39 +0100
Subject: lua solution for week 96, part 1

---
 challenge-096/abigail/lua/ch-1.lua | 14 ++++++++++++++
 1 file changed, 14 insertions(+)
 create mode 100644 challenge-096/abigail/lua/ch-1.lua

(limited to 'challenge-096/abigail/lua')

diff --git a/challenge-096/abigail/lua/ch-1.lua b/challenge-096/abigail/lua/ch-1.lua
new file mode 100644
index 0000000000..68d1c5eb86
--- /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.
+    --
+    words = {}
+    for str in string . gmatch (line, "[^ ]+") do
+        table . insert (words, 1, str)
+    end
+
+    --
+    -- Print the words
+    --
+    io . write (table . concat (words, " "), "\n")
+end
-- 
cgit 


From b15a7dd19167fadcd7ef68d7807fb0915935fc5c Mon Sep 17 00:00:00 2001
From: Abigail <abigail@abigail.be>
Date: Tue, 19 Jan 2021 17:54:23 +0100
Subject: Make lua variables lexical

---
 challenge-096/abigail/lua/ch-1.lua | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'challenge-096/abigail/lua')

diff --git a/challenge-096/abigail/lua/ch-1.lua b/challenge-096/abigail/lua/ch-1.lua
index 68d1c5eb86..9c4b1de913 100644
--- a/challenge-096/abigail/lua/ch-1.lua
+++ b/challenge-096/abigail/lua/ch-1.lua
@@ -2,7 +2,7 @@ for line in io . lines () do
     --
     -- Extract words and put them into an array, in reverse.
     --
-    words = {}
+    local words = {}
     for str in string . gmatch (line, "[^ ]+") do
         table . insert (words, 1, str)
     end
-- 
cgit 


From aafab4118e1ed9b94a7f2c16cf4457d79ab53f77 Mon Sep 17 00:00:00 2001
From: Abigail <abigail@abigail.be>
Date: Tue, 19 Jan 2021 18:53:19 +0100
Subject: lua solution for week 96, part 2

---
 challenge-096/abigail/lua/ch-2.lua | 56 ++++++++++++++++++++++++++++++++++++++
 1 file changed, 56 insertions(+)
 create mode 100644 challenge-096/abigail/lua/ch-2.lua

(limited to 'challenge-096/abigail/lua')

diff --git a/challenge-096/abigail/lua/ch-2.lua b/challenge-096/abigail/lua/ch-2.lua
new file mode 100644
index 0000000000..bb1b042b19
--- /dev/null
+++ b/challenge-096/abigail/lua/ch-2.lua
@@ -0,0 +1,56 @@
+--
+-- 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
+    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
-- 
cgit 


From 053b0ef31a9cddae0cbd792ad539b2d68876538c Mon Sep 17 00:00:00 2001
From: Abigail <abigail@abigail.be>
Date: Tue, 19 Jan 2021 22:01:14 +0100
Subject: lua/ch-2.lua: Save some memory.

---
 challenge-096/abigail/lua/ch-2.lua | 10 ++++++++++
 1 file changed, 10 insertions(+)

(limited to 'challenge-096/abigail/lua')

diff --git a/challenge-096/abigail/lua/ch-2.lua b/challenge-096/abigail/lua/ch-2.lua
index bb1b042b19..162f06eef0 100644
--- a/challenge-096/abigail/lua/ch-2.lua
+++ b/challenge-096/abigail/lua/ch-2.lua
@@ -33,6 +33,16 @@ function LevenshteinDistance (first, second)
                 )
             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
-- 
cgit