summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--AlgoDesignAndTechniqueEdxPython/sources/covering_segment.py33
-rw-r--r--AlgoDesignAndTechniqueEdxPython/tests/covering_segmentsTest.py56
2 files changed, 89 insertions, 0 deletions
diff --git a/AlgoDesignAndTechniqueEdxPython/sources/covering_segment.py b/AlgoDesignAndTechniqueEdxPython/sources/covering_segment.py
new file mode 100644
index 0000000..1093565
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/sources/covering_segment.py
@@ -0,0 +1,33 @@
+# Uses python3
+import sys
+from collections import namedtuple
+
+Segment = namedtuple('Segment', 'start end')
+
+
+def getSortedListOfSegs(segList):
+ segList.sort()
+ return segList
+
+
+def getOptimalPoints(segList):
+ if len(segList) == 1:
+ return [segList[0].start]
+ if segList[0].end <= segList[1].start:
+ result = [segList[0].end]
+ if segList[1].start == segList[1].end:
+ if len(segList) == 2:
+ return result
+ else:
+ result.extend(getOptimalPoints(segList[2:]))
+ return result
+ else:
+ if segList[0].end >= segList[1].end:
+ result = [segList[1].end]
+ del(segList[1])
+ result.extend(getOptimalPoints(segList[1:]))
+ return result
+ else:
+ result = [segList[0].end]
+ result.extend(getOptimalPoints(segList[1:]))
+ return result \ No newline at end of file
diff --git a/AlgoDesignAndTechniqueEdxPython/tests/covering_segmentsTest.py b/AlgoDesignAndTechniqueEdxPython/tests/covering_segmentsTest.py
new file mode 100644
index 0000000..2d61601
--- /dev/null
+++ b/AlgoDesignAndTechniqueEdxPython/tests/covering_segmentsTest.py
@@ -0,0 +1,56 @@
+'''
+Created on Sep 9, 2018
+
+@author: haidong
+'''
+import unittest
+
+from collections import namedtuple
+
+from sources.covering_segment import getSortedListOfSegs, getOptimalPoints
+
+Segment = namedtuple('Segment', 'start end')
+
+class Test(unittest.TestCase):
+
+
+ def testNameSegment(self):
+ s1 = Segment(1,2)
+ self.assertEqual(s1.start, 1)
+ self.assertEqual(s1.end, 2)
+
+ def testGetSortedListOfSegs1(self):
+ s1 = Segment(3,4)
+ s2 = Segment(1,2)
+ segList = [s1, s2]
+ self.assertEqual(getSortedListOfSegs(segList), [s2, s1])
+
+ def testGetSortedListOfSegs2(self):
+ s1 = Segment(3,8)
+ s2 = Segment(3,5)
+ segList = [s1, s2]
+ self.assertEqual(getSortedListOfSegs(segList), [s2, s1])
+
+ def testGetOptimalPoints(self):
+ s1 = Segment(1,3)
+ s2 = Segment(2,5)
+ s3 = Segment(3,6)
+ segList = [s1, s2, s3]
+ segList.sort()
+ result = getOptimalPoints(segList)
+ self.assertEqual(len(result), 1)
+
+ def testGetOptimalPoints1(self):
+ s1 = Segment(4,7)
+ s2 = Segment(1,3)
+ s3 = Segment(2,5)
+ s4 = Segment(5,6)
+ segList = [s1, s2, s3, s4]
+ segList.sort()
+ result = getOptimalPoints(segList)
+ self.assertEqual(len(result), 2)
+
+
+if __name__ == "__main__":
+ #import sys;sys.argv = ['', 'Test.testName']
+ unittest.main() \ No newline at end of file