function levenshtein_distance(str1, str2)
    local len1, len2 = #str1, #str2
    local char1, char2, distance = {}, {}, {}
    str1:gsub('.', function (c) table.insert(char1, c) end)
    str2:gsub('.', function (c) table.insert(char2, c) end)
    for i = 0, len1 do distance[i] = {} end
    for i = 0, len1 do distance[i][0] = i end
    for i = 0, len2 do distance[0][i] = i end
    for i = 1, len1 do
        for j = 1, len2 do
            distance[i][j] = math.min(
                distance[i-1][j  ] + 1,
                distance[i  ][j-1] + 1,
                distance[i-1][j-1] + (char1[i] == char2[j] and 0 or 1)
                )
        end
    end
    return distance[len1][len2]
end

function distance(string1, string2)
    local str1, str2, distance = {}, {}, {};
    str1.len, str2.len = string.len(string1), string.len(string2);
    string.gsub(string1, "(.)", function(s) table.insert(str1, s); end);
    string.gsub(string2, "(.)", function(s) table.insert(str2, s); end);

    for i = 0, str1.len do
      distance[i] = {}
      distance[i][0] = i
    end

    for i = 0, str2.len do
      distance[0][i] = i
    end

    for i = 1, str1.len do
            for j = 1, str2.len do
                    local tmpdist = 1;
                    if(str1[i-1] == str2[j-1]) then tmpdist = 0; end
                    distance[i][j] = math.min(
                            distance[i-1][j] + 1, distance[i][j-1]+1, distance[i-1][j-1] + tmpdist);
            end
    end
    return distance[str1.len][str2.len];
end

local prev = 'test'
local input = io.read()
print(input)

while not (input == '') do   
    print(input, prev)
    local dist = levenshtein_distance(input, prev)
    print('Distance', dist)
        
    prev = input      
    input = io.read()
end

print('quiting')