# Source: content/notes/math/discrete-math.md
# Independent CPU example; use the curriculum environment.
# See /notes/ml/#example-environment or /notes/deep-learning/#example-environment.

def edit_distance(a, b):
    if len(a) < len(b):
        a, b = b, a
    previous = list(range(len(b)+1))
    for i, left in enumerate(a, 1):
        current = [i]
        for j, right in enumerate(b, 1):
            current.append(min(previous[j]+1, current[-1]+1,
                               previous[j-1]+(left != right)))
        previous = current
    return previous[-1]

assert edit_distance("cat", "cut") == 1
assert edit_distance("", "") == 0
assert edit_distance("", "abc") == 3
assert edit_distance("kitten", "sitting") == 3
reference = "one two".split()
hypothesis = "one two three four five".split()
wer = edit_distance(reference, hypothesis)/len(reference)
assert wer == 1.5
print("WER with three insertions:", wer)