diff options
Diffstat (limited to 'challenge-096/abigail/lua/ch-2.lua')
| -rwxr-xr-x[-rw-r--r--] | challenge-096/abigail/lua/ch-2.lua | 35 |
1 files changed, 20 insertions, 15 deletions
diff --git a/challenge-096/abigail/lua/ch-2.lua b/challenge-096/abigail/lua/ch-2.lua index 162f06eef0..99058213ca 100644..100755 --- a/challenge-096/abigail/lua/ch-2.lua +++ b/challenge-096/abigail/lua/ch-2.lua @@ -1,3 +1,13 @@ +#!/opt/local/bin/lua + +-- +-- See ../README.md +-- + +-- +-- Run as: lua ch-2.lua < input-file +-- + -- -- This is an implementation of the Wagner Fischer algorithm, which -- calculates the Levenshtein distance. @@ -7,18 +17,13 @@ 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 = {} + distance = {} for i = 0, n do - distances [i] = {} + distance [i] = {} for j = 0, m do if i == 0 or j == 0 then - distances [i] [j] = i + j + distance [i] [j] = i + j else local cost = 1 if string . sub (first, i, i) == @@ -26,10 +31,10 @@ function LevenshteinDistance (first, second) 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 + distance [i] [j] = math . min ( + distance [i - 1] [j] + 1, + distance [i] [j - 1] + 1, + distance [i - 1] [j - 1] + cost ) end end @@ -37,14 +42,14 @@ function LevenshteinDistance (first, second) -- -- 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)) + -- usage from Theta (n * m) to O (n + m) -- if i > 0 then - distances [i - 1] = nil + distance [i - 1] = nil end end - return distances [n] [m] + return distance [n] [m] end |