"""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
##################################################
