summaryrefslogtreecommitdiff log msg author committer range
diff options
 context: 12345678910152025303540 space: includeignore mode: unifiedssdiffstat only
author committer Haidong Ji 2018-12-25 16:42:27 -0600 Haidong Ji 2018-12-25 16:42:27 -0600 61ffe2a9e5fd066dae82a32185bbfe821696bd8a (patch) 142ea3876ce900c72d023dd3ea3cff32efbef473 b12193500c0da24a9e7fc5a8523ed2252da88bad (diff)
Longest subsequence done! (3 seqs)
The only tricky part was to create and populate the 3-d list. The instructions here was helpful: https://www.ict.social/python/basics/multidimensional-lists-in-python
-rw-r--r--AlgoDesignAndTechniqueEdxPython/sources/lcs3.py44
-rw-r--r--AlgoDesignAndTechniqueEdxPython/tests/lcs3Test.py28
2 files changed, 72 insertions, 0 deletions
 diff --git a/AlgoDesignAndTechniqueEdxPython/sources/lcs3.py b/AlgoDesignAndTechniqueEdxPython/sources/lcs3.pynew file mode 100644index 0000000..4de6a44--- /dev/null+++ b/AlgoDesignAndTechniqueEdxPython/sources/lcs3.py@@ -0,0 +1,44 @@+#Uses python3++import sys+def getLCS3(a, b, c):+ l = len(c)+ m = len(b)+ n = len(a)+# https://www.ict.social/python/basics/multidimensional-lists-in-python+# The link above provides good tutorial for creating the 3-d list.+ D = []+ for _ in range(n + 1):+ x = []+ for _ in range(m + 1):+ y = []+ for _ in range(l + 1):+ y.append(0)+ x.append(y)+ D.append(x)+ + for k in range(1, l + 1):+ for j in range(1, m + 1):+ for i in range(1, n + 1):+ if a[i - 1] == b[j - 1] == c[k - 1]:+ D[i][j][k] = D[i - 1][j - 1][k - 1] + 1+ else:+ D[i][j][k] = max(D[i - 1][j][k], D[i][j - 1][k], D[i][j][k - 1])++ return D[n][m][l]++if __name__ == '__main__':+ input = sys.stdin.read()+ data = list(map(int, input.split()))+ an = data+ data = data[1:]+ a = data[:an]+ data = data[an:]+ bn = data+ data = data[1:]+ b = data[:bn]+ data = data[bn:]+ cn = data+ data = data[1:]+ c = data[:cn]+ print(getLCS3(a, b, c)) \ No newline at end of filediff --git a/AlgoDesignAndTechniqueEdxPython/tests/lcs3Test.py b/AlgoDesignAndTechniqueEdxPython/tests/lcs3Test.pynew file mode 100644index 0000000..c5cf51e--- /dev/null+++ b/AlgoDesignAndTechniqueEdxPython/tests/lcs3Test.py@@ -0,0 +1,28 @@+'''+Created on Dec 25, 2018++@author: haidong+'''+import unittest++from sources.lcs3 import getLCS3+++class Test(unittest.TestCase):++ def testName(self):+ a = [1, 2, 3]+ b = [2, 1, 3]+ c = [1, 3, 5]+ self.assertEqual(2, getLCS3(a, b, c))++ def testName1(self):+ a = [8, 3, 2, 1, 7]+ b = [8, 2, 1, 3, 8, 10, 7]+ c = [6, 8, 3, 1, 4, 7]+ self.assertEqual(3, getLCS3(a, b, c))+++if __name__ == "__main__":+ # import sys;sys.argv = ['', 'Test.testName']+ unittest.main()