Ipsc Load Balancing

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