summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorHaidong Ji2018-12-25 14:27:29 -0600
committerHaidong Ji2018-12-25 14:27:29 -0600
commitb12193500c0da24a9e7fc5a8523ed2252da88bad (patch)
tree492708d14c0bba5575452f50d27397361a047536
parent33b21ee9aad03b052d14227e023b9697c6ce4a55 (diff)
Longest subsequence of 2 seqs done!
Not too bad, since I worked it out in Java already.
-rw-r--r--AlgoDesignAndTechniqueEdxPython/sources/lcs2.py35
-rw-r--r--AlgoDesignAndTechniqueEdxPython/tests/lcs2Test.py48
2 files changed, 83 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxPython/sources/lcs2.py b/AlgoDesignAndTechniqueEdxPython/sources/lcs2.py
new file mode 100644
index 0000000..76f73fd
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/sources/lcs2.py
@@ -0,0 +1,35 @@
+# Uses python3
+
+import sys
+
+
+def getLCS2Length(a, b):
+ m = len(b)
+ n = len(a)
+
+ D = [[0 for _ in range(m + 1)] for _ in range(n + 1)]
+
+ for j in range(1, m + 1):
+ for i in range(1, n + 1):
+ if a[i - 1] == b[j - 1]:
+ D[i][j] = D[i - 1][j - 1] + 1
+ else:
+ D[i][j] = max(D[i - 1][j], D[i][j - 1])
+
+ return D[n][m]
+
+
+if __name__ == '__main__':
+ input = sys.stdin.read()
+ data = list(map(int, input.split()))
+
+ n = data[0]
+ data = data[1:]
+ a = data[:n]
+
+ data = data[n:]
+ m = data[0]
+ data = data[1:]
+ b = data[:m]
+
+ print(getLCS2Length(a, b))
diff --git a/AlgoDesignAndTechniqueEdxPython/tests/lcs2Test.py b/AlgoDesignAndTechniqueEdxPython/tests/lcs2Test.py
new file mode 100644
index 0000000..6c9d350
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/tests/lcs2Test.py
@@ -0,0 +1,48 @@
+'''
+Created on Dec 25, 2018
+
+@author: haidong
+'''
+import unittest
+
+from sources.lcs2 import getLCS2Length
+
+
+class Test(unittest.TestCase):
+
+ def testName(self):
+ a = [2, 7, 5]
+ b = [2, 5]
+ self.assertEqual(2, getLCS2Length(a, b))
+
+ def testName1(self):
+ a = [7]
+ b = [1, 2, 3, 4]
+ self.assertEqual(0, getLCS2Length(a, b))
+
+ def testName2(self):
+ a = [2, 7, 8, 3]
+ b = [5, 2, 8, 7]
+ self.assertEqual(2, getLCS2Length(a, b))
+
+ def testName3(self):
+ a = [1, 2, 3, 4, 5, 6, 7]
+ b = [1, 2, 8, 4, 5, 6]
+ self.assertEqual(5, getLCS2Length(a, b))
+
+ def testName4(self):
+ a = [1, 9, 2, 5, 5, 5, 8, 3, 5, 11, 0, 2, 4, 1, 7, 4, 5, 9, 2, 4, 0, 3, 1, 5, 8, 3, 5, 9, 7, 8, 4, 5, 6,
+ 7 ]
+ b = [6, 3, 8, 3, 1, 8, 3, 5, 0, 9, 6, 8, 3, 5, 7, 9, 1, 4, 7, 9, 3, 5, 9, 0, 1, 4, 2, 7, 5, 8, 9, 3, 5,
+ 6, 1, 6, 3, 1, 6, 7, 3]
+ self.assertEqual(17, getLCS2Length(a, b))
+
+ def testName5(self):
+ a = [2, 4, 3, 3]
+ b = [1, 4, 3]
+ self.assertEqual(2, getLCS2Length(a, b))
+
+
+if __name__ == "__main__":
+ # import sys;sys.argv = ['', 'Test.testName']
+ unittest.main()