1 import unittest
   2 """
   3 Seminar:FourBoxes problem in [yong27/2003-01-10]
   4 
   5 Wrong approach --> [yong27/2003-01-12] correct. performance improvement
   6 """
   7 import unittest
   8 
   9 def intersect(*args):
  10     result=[]
  11     for x in args[0]:
  12         for other in args[1:]:
  13             if x not in other: break
  14         else:
  15             result.append(x)
  16     return result
  17 
  18 def combo(aList, size=2): 
  19     if size==0 or not aList: 
  20         return [aList[:0]] 
  21     else: 
  22         result = [] 
  23         for i in range(0, (len(aList)-size)+1): 
  24             pick = aList[i:i+1] 
  25             rest = aList[i+1:] 
  26             for x in combo(rest, size-1): 
  27                 result.append(pick+x) 
  28         return result 
  29 
  30 class Rect:
  31     def __init__(self, x1,y1, x2, y2):
  32         self.x1=x1; self.y1=y1
  33         self.x2=x2; self.y2=y2
  34         self.xr=range(x1,x2)
  35         self.yr=range(y1,y2)
  36     def area(self):
  37         return (self.x2-self.x1) * (self.y2-self.y1)
  38     def getPileArea(self, *aRect):
  39         xrList=[self.xr]; yrList=[self.yr]
  40         for rect in aRect:
  41             xrList.append(rect.xr)
  42             yrList.append(rect.yr)
  43         xIts = intersect(*xrList)
  44         yIts = intersect(*yrList)
  45         if xIts and yIts:
  46             return len(xIts) * len(yIts)
  47         else:
  48             return 0
  49 
  50 def main(a,b,c,d):
  51     totalArea = a.area()+b.area()+c.area()+d.area()
  52     for pair in combo([a,b,c,d]):
  53         totalArea -= pair[0].getPileArea(pair[1])
  54     for three in combo([a,b,c,d],3):
  55         totalArea += three[0].getPileArea(three[1],three[2])
  56     totalArea -= a.getPileArea(b,c,d)
  57     return totalArea
  58 
  59 def myProblem():
  60     a=Rect(1,2,4,4)
  61     b=Rect(2,3,5,7)
  62     c=Rect(3,1,6,5)
  63     d=Rect(7,3,8,6)
  64     return main(a,b,c,d)
  65 
  66 class RectTest(unittest.TestCase):
  67     def testIntersect(self):
  68         a = [1,2,3,4]
  69         b = [3,4,5,6]
  70         self.assertEquals([3,4], intersect(a,b))
  71     def testIntersectMultiArgu(self):
  72         a = [[1,2],[0]]
  73         self.assertEquals([], intersect(*a))
  74     def testIntersectThree(self):
  75         a = [1,2,3,4]
  76         b = [3,4,5,6]
  77         c = [4,5,6,7]
  78         self.assertEquals([4], intersect(a,b,c))
  79     def testCombination(self):
  80         self.assertEquals([[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]],
  81                           combo([1,2,3,4]))
  82         self.assertEquals([[1,2],[1,3],[2,3]],combo([1,2,3]))
  83 
  84     def testOneArea(self):
  85         a = Rect(1,2,4,4)
  86         self.assertEquals(6, a.area())
  87     def testIsPile1(self):
  88         a = Rect(0,0,1,1)
  89         b = Rect(1,0,2,1)
  90         self.assertEquals(0, a.getPileArea(b))
  91     def testIsPile2(self):
  92         a = Rect(0,0,2,2)
  93         b = Rect(1,1,3,3)
  94         self.assertEquals(1, a.getPileArea(b))
  95     def testIsPileThree(self):
  96         a = Rect(0,0,2,1)
  97         b = Rect(1,0,3,2)
  98         c = Rect(1,0,2,3)
  99         self.assertEquals(1, a.getPileArea(b,c))
 100     def testMain(self):
 101         self.assertEquals(26, myProblem())
 102 
 103 def specialProblem():
 104     a=Rect(1,2,800,600)
 105     b=Rect(2,3,700,900)
 106     c=Rect(3,1,666,666)
 107     d=Rect(7,3,1000,888)
 108     return main(a,b,c,d)
 109 
 110 if __name__=='__main__':
 111     #unittest.main(argv=('','-v'))
 112     print specialProblem()