-
Notifications
You must be signed in to change notification settings - Fork 0
/
min_edit_distance.py
68 lines (53 loc) · 1.59 KB
/
min_edit_distance.py
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
# Finding the minimum number of edits on X to get to Y.
# Inserting a new character or deleting an existing character costs 1 edit.
# Substituting costs 2( or 1) edits.
# def update_memo(a, b, memo):
# memo.update([(a, b)])
# return
# import functools as ft
# @ft.lru_cache(maxsize=None)
def call_counter(func):
def helper(*args, **kwargs):
helper.calls += 1
return func(*args, **kwargs)
helper.calls = 0
helper.__name__= func.__name__
return helper
def memoize(func):
mem = {}
def memoizer(*args, **kwargs):
key = str(args) + str(kwargs)
if key not in mem:
mem[key] = func(*args, **kwargs)
return mem[key]
return memoizer
@call_counter
@memoize
def d(x, y):
if(len(x) == 0):
return(len(y))
elif(len(y) == 0):
return(len(x))
else:
return(min(
d(x[1:], y) + 1,
d(x, y[1:]) + 1,
d(x[1:], y[1:]) + (lambda a, b: 0 if a[0] == b[0] else 10)(x, y)
))
import time
def call(a, b):
start = time.time()
distance = d(a, b)
end = time.time()
t_reqd = end - start
print(f'Minimum distance between {a} and {b} is {distance}. It took {int(t_reqd)} seconds.')
# print(d("Python", "Peithen"))
# print("The function was called " + str(d.calls) + " times!")
# call('abc', 'c')
# call('intention', 'execution')
# call('sunday', 'saturday')
# call('accomodate', 'accommodate')
# call('pharoah', 'pharaoh')
# call('ATGCGTGGCATGGCA', 'ATCCGCGGAGCTACCT')
call('ATGCGTGGCATGGCAGGCTAAATT', 'ATCCGCCCGTGGTACGGAGCTACCT')
# call("Python", "Peithen")