"""b.py Load Balancing June Kim <juneaftn@hanmail.net>""" from __future__ import generators import unittest, shlex from cStringIO import StringIO def doAll(aString): lines=parseLines(aString) for eachLine in lines: yield getRounds(eachLine) def parseLines(aString): stream=StringIO(aString) lexer=shlex.shlex(stream) numOfElements=int(lexer.get_token()) total=[] while 1: thisLine=[] for i in range(numOfElements): thisLine.append(int(lexer.get_token())) yield thisLine numOfElements=lexer.get_token() if numOfElements=='-': break else: numOfElements=int(numOfElements) def getSum(aList): return reduce(lambda x,y:x+y,aList,0) class BalancingImpossibleException(Exception): pass def getAvg(aList): sum=getSum(aList) if sum % len(aList): raise BalancingImpossibleException return sum/len(aList) def getRounds(aList,aDebug=0): try: avg=getAvg(aList) except BalancingImpossibleException: return -1 listLen=len(aList) totalSum=getSum(aList) last=0;leftSum=0;rightSum=totalSum for i in range(listLen): rightSum-=aList[i] last=min(leftSum-avg*i,rightSum-avg*(listLen-i-1),last) leftSum+=aList[i] return -last class TestLoadBalancing(unittest.TestCase): def setUp(self): self.l=[[[6,0,9],4], [[0,9,6],5], [[0,6,9],5], [[2,3,5,6],3], [[0,1,4,3],3], [[16,17,15, 0,20, 1, 1, 2],23], [[16,17,15, 1,19, 1, 1, 2],23], [[16,17,15,10,10, 1, 1, 2],23], [[16,17,15,11, 9, 1, 1, 2],23], [[16,17,15,12, 8, 1, 1, 2],24], [[16,17,15,13, 7, 1, 1, 2],25], [[16,17,15,20, 0, 1, 1, 2],32], [[16, 1,15,20, 0, 1,17, 2],16], [[16, 1,15, 0,20, 1,17, 2], 7], [[17,18,16,21, 1, 2, 2, 3],32], [[0,0,100,0,0,0,0,0,0,0],70], [[0,0, 99,1,0,0,0,0,0,0],69], [[0,1,3,5,333,5,3,1,0],147 ], [[5,1,4,2,3,3,2,4,1,5,0,6],3], [[9,0,8,1,7,2,6,3,5,4,4,5,3,6,2,7,1,8,0,9],-1], [[17,9,4],7], [[6,94,3303,6921,94,105,8,7,77,4084,8,7,98,6,4,\ 974,3,10,6,0,90,23],7459], ] def testGetRounds(self): for data,answer in self.l: actual=getRounds(data) self.assertEquals(answer,actual) def testParseLine(self): data="""\ 3 0 1 3 2 5 1 -1""" expected=[[0,1,3],[5,1]] self.assertEquals(expected,list(parseLines(data))) if __name__=='__main__': unittest.main(argv=('','-v')) ################################################## """runb.py Runner for b.py June Kim <juneaftn@hanmail.net> python runb.py <inputfile> <outputfile> """ import b,sys if __name__=='__main__': f=open(sys.argv[1]) fout=open(sys.argv[2],'wt') bgen=b.doAll(f.read()) for each in bgen: print each fout.write("%s\n"%each) f.close() fout.close() ################################################## ## B1 ## ## 147 ## 3 ## -1 ## 7459 ## 7 ## 8564 ################################################# ## B2 ## ## 107829 ## 24286 ## 167437 ##################################################