blob: e55363e93843c1c8cf7823137b49e36b37b2fd13 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#!/usr/bin/env python3
"""Challenge 96, Task 2"""
import sys
import numpy as np
DEFAULT_INPUT = ["kitten", "sitting"]
def edit_distance(s1, s2):
"""Determine the edit distance between two strings."""
dp = np.zeros((len(s1), len(s2)), dtype=np.int)
for i, j in np.ndindex(dp.shape):
if i == 0:
dp[i][j] = j
elif j == 0:
dp[i][j] = i
elif s1[i - 1] == s2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = 1 + min(dp[i][j - 1],
dp[i - 1][j],
dp[i - 1][j - 1])
return dp[-1][-1]
def main(args=None):
"""Run the task"""
if args is None:
args = sys.argv[1:]
if args:
s1, s2 = args[0:2]
else:
s1, s2 = DEFAULT_INPUT
print(edit_distance(s1, s2))
if __name__ == '__main__':
sys.exit(main())
|
