Returns the Levenshtein Distance value between two strings.

Levenshtein.neon

-- Rosettacode Coding Exercise: Levenshtein distance
-- Description: In information theory and computer science, the Levenshtein distance is a metric
--              for measuring the amount of difference between two sequences (i.e. an edit 
--              distance).  The Levenshtein distance between two strings is defined as the minimum 
--              number of edits needed to transform one string into the other, with the allowable 
--              edit operations being insertion, deletion, or substitution of a single character.
-- From: http://rosettacode.org/wiki/Levenshtein_distance
-- Language: http://neon-lang.org
-- Author: Larry Frieson
-- Date: 11/11/2015
IMPORT multiarray

FUNCTION Distance(s, n: String, sl, nl: Number): Number
    -- for all i and j, d[i,j] will hold the Levenshtein distance between the first i characters of s and the first j characters of n
    -- note that d has (s.length()) * (n.length()) values
    VAR d: multiarray.ArrayNumber2D := multiarray.makeNumber2D(s.length() - 1, n.length() - 1)

    -- set each element in d to zero
    FOR i := 0 TO s.length()-1 DO
        FOR j := 0 TO n.length()-1 DO
            d[i][j] := 0
        END FOR
    END FOR
 
    -- source prefixes can be transformed into empty string by dropping all characters
    FOR i := 1 TO s.length() - 1 DO
        d[i][0] := i
    END FOR
 
    -- target prefixes can be reached from empty source prefix by inserting every character
    FOR j := 1 TO n.length() - 1 DO
        d[0][j] := j
    END FOR
 
    FOR j := 1 TO n.length() - 1 DO
        FOR i := 1 TO s.length() - 1 DO
            IF s[i] = n[j] THEN
                d[i][j] := d[i - 1][j - 1]              -- no operation required
            ELSE
                d[i][j] := Min([d[i - 1][j] + 1,        -- a deletion
                                d[i][j - 1] + 1,        -- an insertion
                                d[i - 1][j - 1] + 1])   -- a substitution
            END IF
        END FOR
    END FOR
    RETURN d[s.length() - 1][n.length() -1]
END FUNCTION

/* FUNCTION Distance(s, n: String, sPos: Number, nPos: Number): Number
    VAR val: Number := 0

    -- if either string is empty, then the distance is the length of the string.
    IF sPos < 0 THEN
        RETURN nPos
    END IF
    IF nPos < 0 THEN
        RETURN sPos
    END IF

    --print("s[sPos-1]=\(s[sPos-1]), n[nPos-1]=\(n[nPos-1])")
    IF s[sPos] = n[nPos] THEN
        RETURN Distance(s, n, sPos - 1, nPos - 1)
    END IF

    --print("sPos=\(sPos), nPos=\(nPos)")
    RETURN Min([
        Distance(s, n, sPos - 1, nPos - 1)  + 1, 
        Distance(s, n, sPos,     nPos - 1)  + 1, 
        Distance(s, n, sPos - 1, nPos)      + 1
    ])
    --RETURN Distance(s, n, sPos - 1, nPos - 1)
END FUNCTION
 */
FUNCTION Min(val: Array<Number>): Number
    VAR minVal: Number := 0xFFFFFFFF
    
    FOREACH n IN val DO
        IF n < minVal THEN
            minVal := n
        END IF
    END FOREACH
    print("Min of: \(val) is \(minVal).")
    RETURN minVal
END FUNCTION

VAR S1, S2: String := ""
S1 := "kitten"
S2 := "sitting"
TESTCASE Distance(S1, S2, S1.length()-1, S2.length()-1) = 3
S1 := "rosettacode"
S2 := "raisethysword"
print("\(Distance(S1, S2, S1.length() - 1, S2.length() -1 )+1)")
TESTCASE Distance(S1, S2, S1.length()-1, S2.length()-1) = 8