From 38b3f4b27cb5141f27e81d1f66082af7a2e9cfbb Mon Sep 17 00:00:00 2001 From: Haidong Ji Date: Wed, 19 Sep 2018 21:45:59 -0500 Subject: Covering segment complete. This is quite tricky. I read the forum and it helped https://courses.edx.org/courses/course-v1:UCSanDiegoX+ALGS200x+2T2017/discussion/forum/course/threads/5a427c497acf2d0810000713 In particular try_my_best's algorithm worked. But I need to de-dup and sort the list before feeding it to that algorithm, otherwise it won't pass all the tests!--- .../tests/covering_segmentsTest.py | 155 ++++++++++++++++++--- 1 file changed, 138 insertions(+), 17 deletions(-) (limited to 'AlgoDesignAndTechniqueEdxPython/tests') diff --git a/AlgoDesignAndTechniqueEdxPython/tests/covering_segmentsTest.py b/AlgoDesignAndTechniqueEdxPython/tests/covering_segmentsTest.py index 2d61601..aeb4f36 100644 --- a/AlgoDesignAndTechniqueEdxPython/tests/covering_segmentsTest.py +++ b/AlgoDesignAndTechniqueEdxPython/tests/covering_segmentsTest.py @@ -7,29 +7,31 @@ import unittest from collections import namedtuple -from sources.covering_segment import getSortedListOfSegs, getOptimalPoints +# from sources.covering_segment import getOptimalPoints, getOptimalPoints1, getOptimalPoints2 +from sources.covering_segment import getOptimalPoints2 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 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 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 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) @@ -37,7 +39,7 @@ class Test(unittest.TestCase): s3 = Segment(3,6) segList = [s1, s2, s3] segList.sort() - result = getOptimalPoints(segList) + result = getOptimalPoints2(segList) self.assertEqual(len(result), 1) def testGetOptimalPoints1(self): @@ -47,9 +49,128 @@ class Test(unittest.TestCase): s4 = Segment(5,6) segList = [s1, s2, s3, s4] segList.sort() - result = getOptimalPoints(segList) + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 2) + + def testGetOptimalPoints2(self): + s1 = Segment(1,1) + s2 = Segment(1,1) + s3 = Segment(1,1) + segList = [s1, s2, s3] + segList.sort() + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 1) + + def testGetOptimalPoints3(self): + s1 = Segment(1,1) + s2 = Segment(1,2) + s3 = Segment(1,1) + segList = [s1, s2, s3] + segList.sort() + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 1) + + def testGetOptimalPoints4(self): + s1 = Segment(5,6) + s2 = Segment(3,4) + s3 = Segment(1,2) + segList = [s1, s2, s3] + segList.sort() + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 3) + + def testGetOptimalPoints5(self): + s1 = Segment(1,1) + s2 = Segment(2,2) + s3 = Segment(1,1) + segList = [s1, s2, s3] + segList.sort() + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 2) + + def testGetOptimalPoints6(self): + s1 = Segment(1,5) + s2 = Segment(2,2) + s3 = Segment(1,1) + segList = [s1, s2, s3] + segList.sort() + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 2) + + def testGetOptimalPoints7(self): + s1 = Segment(1,5) + s2 = Segment(2,4) + s3 = Segment(1,3) + segList = [s1, s2, s3] + segList.sort() + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 1) + + def testGetOptimalPoints8(self): + s1 = Segment(1,4) + s2 = Segment(2,4) + s3 = Segment(1,3) + segList = [s1, s2, s3] + segList.sort() + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 1) + + def testGetOptimalPoints9(self): + s1 = Segment(1,7) + s2 = Segment(1,6) + s3 = Segment(1,3) + segList = [s1, s2, s3] + segList.sort() + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 1) + + def testGetOptimalPoints10(self): + s1 = Segment(1,7) + s2 = Segment(1,6) + s3 = Segment(1,3) + s4 = Segment(7,7) + segList = [s1, s2, s3, s4] + segList.sort() + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 2) + + def testGetOptimalPoints11(self): + s1 = Segment(1,2) + s2 = Segment(3,4) + s3 = Segment(6,12) + s4 = Segment(7,8) + segList = [s1, s2, s3, s4] + segList.sort() + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 3) + + def testGetOptimalPoints12(self): + s1 = Segment(1,15) + s2 = Segment(2,14) + s3 = Segment(6,12) + s4 = Segment(7,8) + segList = [s1, s2, s3, s4] + segList.sort() + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 1) + + def testGetOptimalPoints13(self): + s1 = Segment(1,15) + s2 = Segment(2,3) + s4 = Segment(4,8) + segList = [s1, s2, s4] + segList.sort() + result = getOptimalPoints2(segList) self.assertEqual(len(result), 2) + def testGetOptimalPoints14(self): + s1 = Segment(1,3) + s2 = Segment(1,4) + s4 = Segment(2,3) + segList = [s1, s2, s4] + segList.sort() + result = getOptimalPoints2(segList) + self.assertEqual(len(result), 1) if __name__ == "__main__": #import sys;sys.argv = ['', 'Test.testName'] -- cgit v1.2.3