-
Notifications
You must be signed in to change notification settings - Fork 7
Expand file tree
/
Copy pathdiff_Solution.py.m4
More file actions
62 lines (56 loc) · 1.71 KB
/
Copy pathdiff_Solution.py.m4
File metadata and controls
62 lines (56 loc) · 1.71 KB
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
diff --git a/CodeJam/Solution.py.m4 b/examples/2020/Round3/A/Solution.py.m4
index ecd70df..c37eef3 100644
--- a/CodeJam/Solution.py.m4
+++ b/examples/2020/Round3/A/Solution.py.m4
@@ -460,12 +460,56 @@ def init():
def readInput():
- global result
+ global result, C, J
+ C = cin()
+ J = cin()
# write to result
def calcFunction():
global result
+ result = C
+ lsm = np.zeros((len(C) + 1, len(J) + 1), dtype=np.int32)
+ lsm[0, :] = np.arange(len(J) + 1)
+ lsm[:, 0] = np.arange(len(C) + 1)
+ for i in range(1, len(C) + 1):
+ for j in range(1, len(J) + 1):
+ if C[i - 1] == J[j - 1]:
+ sub_cost = 0
+ else:
+ sub_cost = 1
+
+ lsm[i, j] = min(
+ lsm[i - 1, j] + 1, lsm[i, j - 1] + 1, lsm[i - 1, j - 1] + sub_cost
+ )
+
+ result = ""
+ p = (len(C), len(J))
+ c = 0
+ llog(lsm)
+ while c < lsm[len(C), len(J)] // 2:
+ if lsm[p] == lsm[p[0] - 1, p[1]] + 1:
+ # result=C[]
+ result = C[p[0] - 1] + result
+ p = (p[0] - 1, p[1])
+ c += 1
+ llog("deleting from C position", p[0])
+ elif lsm[p] == lsm[p[0], p[1] - 1] + 1:
+ p = (p[0], p[1] - 1)
+ c += 1
+ llog("deleting from J position", p[1])
+ else:
+ result = C[p[0] - 1] + result
+ p = (p[0] - 1, p[1] - 1)
+ if C[p[0]] == J[p[1]]:
+ pass
+ else:
+ llog("changing from J position", p[1])
+ c += 1
+ llog("result is now:", result)
+ llog("next pos", p)
+ llog("final pos", p)
+ result = J[: p[1]] + result
if __name__ == "__main__":