Google Code Jam Helper file v1.1

import multiprocessing
import cPickle
import time
import bisect
import math
from files import *

"""
Things yet to do:

"""

BABY = 0
SMALL = 1
LARGE = 2
PSMALL = 3
PLARGE = 4

def doit(preprocess, readinput, solve, MultiCore = True, Verify = False, Input  = None, Filename = None, Problem = "A", Attempt = 0, SingleCase = False):
    start_time = time.time()

    if Input == None:
        if Filename == None:
            print "Input Filename Not specified."
            return
        INPUTNAME = Filename
    else:
        INPUTNAME = Problem + "_baby.in"
        if Input == SMALL: INPUTNAME = Problem + "-small-attempt" + str(Attempt) + ".in"
        if Input == LARGE: INPUTNAME = Problem + "-large.in"
        if Input == PSMALL: INPUTNAME = Problem + "-small-practice.in"
        if Input == PLARGE: INPUTNAME = Problem + "-large-practice.in"



    OUTPUTNAME = INPUTNAME[:INPUTNAME.find(".")] + ".out"

    Input = File(INPUTNAME, "r")
    Correct = None

    if Verify == True:
        try:
            Output = File(OUTPUTNAME, "r")
            Correct = Output.readall()
        except IOError:
            print "Verification not possible - output file does not exist. Fall back to normal mode."
            Verify = False
            Output = File(OUTPUTNAME, "w")
    else:
        Output = File(OUTPUTNAME, "wb")

    PREPNAME = Problem + ".prep"
    try:
        pfile = open(PREPNAME, "rb")
        Prep = cPickle.load(pfile)
        pfile.close()
        print "Loaded preprocessed information from file"
    except IOError:
        Prep = preprocess()
        if Prep <> None:
            pfile = open(PREPNAME, "wb")
            cPickle.dump(Prep, pfile, 2)
            pfile.close()
            print "Saved preprocessed information to file"

    if SingleCase == True:
        n_cases = 1
    else:
        n_cases = Input.readint()

    Problems = []

    # Just reading input
    for _ in range(n_cases):
        Problems.append(readinput(Input))

    AllCorrect = True

    if MultiCore:
        pool = multiprocessing.Pool(processes = 4)
        Result = [pool.apply_async(solve, [p, Prep]) for p in Problems]

    for n in range(n_cases):
        if MultiCore:
            Solution = Result[n].get()
        else:
            Solution = solve(Problems[n], Prep)

        sline = "Case #" + str(n+1) + ": " + str(Solution)

        print sline

        if not Verify:
            Output.write(sline + "\n")
        else:
            for line in split(sline, "\n"):
                if len(Correct) == 0 or line.rstrip("\n") <> Correct[0].rstrip("\n"):
                    print "MISMATCH: ", line,
                    AllCorrect = False
                    if len(Correct) > 0: print Correct[0]
                    else: print ""
                if len(Correct) > 0: Correct.pop(0)

        TOT = (time.time() - start_time) / (n + 1) * n_cases
        if TOT > 120:
            print "Running over two minutes by:", int (TOT - 120), "seconds"

    print time.time() - start_time, "seconds"
    if Verify and AllCorrect == False:
        print "VERIFICATION FAILED - ERRORS WERE FOUND IN SOLUTION"

    return

Primes = None
largestPrime = None

def frange(x, y, jump):
    while x < y:
        yield x
        x += jump

def loadPrimes(N):
    global Primes
    global largestPrime
    try:
        pfile = open("Primes" + str(N) + ".prep", "rb")
        Primes = cPickle.load(pfile)
        largestPrime = N
        pfile.close()
    except IOError:
        s = set(range(3, N + 1, 2))
        Primes = [2]
        for i in range(3, N + 1, 2):
            if i not in s:
                continue

            Primes.append(i)

            k = 2
            while k*i <= N:
                if k*i in s:
                    s.remove(k*i)
                k += 1
        pfile = open("Primes" + str(N) + ".prep", "wb")
        cPickle.dump(Primes, pfile, 2)
        largestPrime = N
    return


def getPrimes(A, B):
    global Primes
    global largestPrime
    """get primes between A and B inclusive"""
    if Primes == None:
        print "Prime numbers are not initialized"
        quit()

    if B > largestPrime:
        print "Sorry, no data on primes so large"
        quit()

    S = bisect.bisect_left(Primes, A)
    E = bisect.bisect_left(Primes, B + 1)
    return Primes[S:E]


def ncr(n, r):
    r = min(r, n-r)
    if r == 0: return 1
    if r < 0: return 0
    num = reduce(mul, xrange(n, n-r, -1))
    denom = reduce(mul, xrange(1, r+1))
    return num/denom

def memoize(f):
    cache= {}
    def memf(*x):
        if x not in cache:
            cache[x] = f(*x)
        return cache[x]
    return memf

def Transpose(M):
    X = len(M)
    Y = len(M[0])
    A = []
    for y in range(Y):
        B = [0] * X
        for x in range(X):
            B[x] = M[x][y]
        A.append(B)
    return A

def bin_search_max(function, search_from, search_to, *args):
    """
    function - function to test - must return True when result is OK.
    search_from - search from where (integer!)
    search_to - search to where (integer!)
    """

    while search_from <> search_to:
        guess = (search_from + search_to) / 2 + 1
        if function(guess, *args):
            search_from = guess
        else:
            search_to = guess - 1

    return search_from

def bin_search_max_float(function, search_from, search_to, precision, *args):
    """
    function - function to test - must return True when result is OK.
    search_from - search from where (integer!)
    search_to - search to where (integer!)
    """

    while abs(search_from - search_to) > precision:
        guess = (search_from + search_to) / 2.0
        if function(guess, *args):
            search_from = guess
        else:
            search_to = guess

    return search_from

def bin_search_min_float(function, search_from, search_to, precision, *args):
    """
    function - function to test - must return True when result is OK.
    search_from - search from where (integer!)
    search_to - search to where (integer!)
    """

    while abs(search_from - search_to) > precision:
        guess = (search_from + search_to) / 2.0
        if function(guess, *args):
            search_to = guess
        else:
            search_from = guess

    return search_from

def bin_search_min(function, search_from, search_to, *args):
    """
    function - function to test - must return True when result is OK.
    search_from - search from where (integer!)
    search_to - search to where (integer!)
    """

    while search_from <> search_to:
        guess = (search_from + search_to) / 2
        if function(guess, *args):
            search_to = guess
        else:
            search_from = guess + 1

    return search_from


def bin_search(function, search_result, search_from, search_to, precision, *args):
    """
    function - function to test
    search_result - what to look for (which number)
    search_from - search from where
    search_to - search to where
    precision - precision for comparison to test result
    """
    W = search_to - search_from
    step =  W / 4.0
    initial = W / 2.0 + search_from
    s = function(initial, *args)

    while abs(step) > precision:
        if s > search_result and step > 0:
            step = - step / 2
        if s < search_result and step < 0:
            step = - step / 2
        initial = initial + step
        s = function(initial, *args)
    return initial

def square_matrix_multiply(a, b):
    s = len(a)
    r = []

    for x in range(s):
        r.append([0] * s)
        for y in range(s):
            for t in range(s):
                r[x][y] += (a[x][t] * b[t][y])
                r[x][y] = r[x][y]

    return r

def fastpower(m, x, p):
    """return a**b % q"""
    val = x
    mult = x
    p -= 1

    while p > 0:
        odd = p & 1 # bitwise and
        if odd == 1:
            val = m(val, mult)
            p -= 1
        if p == 0:
            break
        mult = m(mult, mult)
        p = p >> 1 # bitwise divide by 2
    return val

def feq(a, b):
    return fabs(a-b) < 1e-8

def next_permutation(L):
    B = len(L) - 1
    while L[B] <= L[B-1]:
        B = B - 1
        if (B == 0):
            return sorted(L)

    b = B
    for x in range(B, len(L)):
        if L[b] > L[x] and L[x] > L[B-1]:
            b = x

    (L[b], L[B - 1]) = (L[B - 1], L[b])
    L = L[:B] + sorted(L[B:])
    return L

def semi_circle_segment(x0, x1, R):
    def integral(x, R):
        h = R - x
        return (R**2*acos((R-h)/R) - (R-h)*sqrt(2*R*h-h**2))/2

    return - integral(x1, R) + integral(x0, R)

def isqrt(x):
    if x < 0:
        raise ValueError('square root not defined for negative numbers')
    n = int(x)
    if n == 0:
        return 0
    a, b = divmod(n.bit_length(), 2)
    x = 2**(a+b)
    while True:
        y = (x + n//x)//2
        if y >= x:
            return x
        x = y

def ilog(x, b):
    if b == 1:
        raise "Log base 1 fail"
    a = -1
    bb = 1
    while bb <= x:
        bb *= b
        a += 1
    return a

class File:
    def __init__(self, filename, mode):
        self.handle = open(filename, mode)
        self.cursor = 0
        self.filename = filename
        self.mode = mode
        if mode == "r":
            self.lines = self.handle.readlines()

    def __del__(self):
        self.handle.close()

    def readint(self):
        a = int(self.lines[self.cursor])
        self.cursor += 1
        return a

    def readall(self):
        return self.lines

    def readbinary(self):
        self.handle.close()
        self.handle = open(self.filename, "rb")
        return self.handle.read()

    def readints(self):
        ints = self.lines[self.cursor]
        ints = strip(ints, "\n")
        ints = strip(ints, " ")
        while "  " in ints:
            ints = ints.replace("  ", " ")
        ints = ints.split(" ")
        for a in range(len(ints)):
            ints[a] = int(ints[a])
        self.cursor += 1
        return ints

    def readfloats(self):
        ints = self.lines[self.cursor]
        ints = strip(ints, "\n")
        ints = ints.split(" ")
        for a in range(len(ints)):
            ints[a] = float(ints[a])
        self.cursor += 1
        return ints

    def readstring(self):
        a = self.lines[self.cursor]
        a = strip(a, "\n")
        self.cursor += 1
        return a

    def readstrings(self):
        a = self.lines[self.cursor]
        a = strip(a, "\n")
        a = a.split(" ")
        self.cursor += 1
        return a

    def write(self, line):
        self.handle.write(line)
        return

    def writeint(self, number):
        self.handle.write(str(number))
        return

    def writefloat(self, fl, after):
        self.handle.write(("%." + str(after) + "f") % fl)
        return

    def nextline(self):
        self.handle.write("\n")
        return


    """Matrix = numpy.array(Matrix, dtype = numpy.int64)"""


class UnionFind:
    def __init__(self):
        '''\
Create an empty union find data structure.'''
        self.num_weights = {}
        self.parent_pointers = {}
        self.num_to_objects = {}
        self.objects_to_num = {}
        self.unique = 0

    def insert_objects(self, objects):
        '''\
Insert a sequence of objects into the structure.  All must be Python hashable.'''
        for object in objects:
            self.find(object);

    def find(self, object):
        '''\
Find the root of the set that an object is in.
If the object was not known, will make it known, and it becomes its own set.
Object must be Python hashable.'''
        if not object in self.objects_to_num:
            obj_num = len(self.objects_to_num)
            self.num_weights[obj_num] = 1
            self.objects_to_num[object] = obj_num
            self.num_to_objects[obj_num] = object
            self.parent_pointers[obj_num] = obj_num
            self.unique += 1
            return object
        stk = [self.objects_to_num[object]]
        par = self.parent_pointers[stk[-1]]
        while par != stk[-1]:
            stk.append(par)
            par = self.parent_pointers[par]
        for i in stk:
            self.parent_pointers[i] = par
        return self.num_to_objects[par]

    def union(self, object1, object2):
        '''\
Combine the sets that contain the two objects given.
Both objects must be Python hashable.
If either or both objects are unknown, will make them known, and combine them.'''
        o1p = self.find(object1)
        o2p = self.find(object2)
        if o1p != o2p:
            on1 = self.objects_to_num[o1p]
            on2 = self.objects_to_num[o2p]
            w1 = self.num_weights[on1]
            w2 = self.num_weights[on2]
            if w1 < w2:
                o1p, o2p, on1, on2, w1, w2 = o2p, o1p, on2, on1, w2, w1
            self.num_weights[on1] = w1+w2
            del self.num_weights[on2]
            self.parent_pointers[on2] = on1
            self.unique -= 1
    def getUnique(self):
        return self.unique


class mod_calc:
    def __init__(self, m):
        self.m = m
        self.fact_table = None

        self.pre_fact(m)

    def pre_fact(self, m):
        f = 1
        res = [1]
        for n in range(1, m):
            f = (f*n)%m
            res.append(f)
        return res

    def factorial(self, n):
        if self.fact_table == None:
            self.fact_table = self.pre_fact(self.m)
        if n==0:
            return 1
        r = n%self.m
        k = n//self.m
        kk = 1
        if k%2==1:
            kk = -1
        return (self.fact_table[r]*self.factorial(k)*kk)%self.m

    def fact_ord(self, n):
        r = n%self.m
        k = n//self.m
        if k==0:
            return 0
        return k+self.fact_ord(k)

    def gcd(self, a, b):
        if b==0:
            return [1,0]
        k = a//b
        r = a-b*k
        g = self.gcd(b, r)
        return [g[1], g[0]-g[1]*k]

    def inv(self, x):
        g = self.gcd(self.m, x)
        return g[1]%self.m

    def ncr(self, n, r):
        if self.fact_ord(n)>self.fact_ord(r)+self.fact_ord(n-r):
            return 0
        return (self.factorial(n)*self.inv((self.factorial(r)*self.factorial(n-r))%self.m))%self.m

def rotate_coordinates_clockwise(xr, yr, alpha):
    """point stays still, coordinate axis rotate clockwise by angle alpha"""
    y = yr * math.cos(alpha) + xr * math.sin(alpha)
    x = xr * math.cos(alpha) - yr * math.sin(alpha)
    return x, y

def point_left_line(a, b, c):
    """a and b are two points of line, showing direction. c is point to be determined"""
    r = (b[0] - a[0])*(c[1] - a[1]) - (b[1] - a[1])*(c[0] - a[0])

    if r > 1e-15:
        return True

    elif r < -1e-15:
        return False

    return None

def convex_hull(points):
    points = sorted(set(points))
    if len(points) <= 1:
        return points
    def cross(o, a, b):
        return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])
    lower = []
    for p in points:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)
    upper = []
    for p in reversed(points):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)
    return lower[:-1] + upper[:-1]

def findSCCs(Graph, n = None):
    """Graph with vertices numbered from 1...n, represented as Dictionary"""

    if n == None:
        n = len(Graph)

    po={}
    ll={}
    sf={}
    sq = []
    sl=[]
    i=0
    for s in xrange(1, n+1):
        if s not in sf:
            queue=[s]
            while queue:
                v=queue[-1]
                if v not in po:
                    i=i+1
                    po[v]=i
                done=1
                v_nbrs=Graph.get(v, [])
                for w in v_nbrs:
                    if w not in po:
                        queue.append(w)
                        done=0
                        break
                if done==1:
                    ll[v]=po[v]
                    for w in v_nbrs:
                        if w not in sf:
                            if po[w]>po[v]:
                                ll[v]=min([ll[v],ll[w]])
                            else:
                                ll[v]=min([ll[v],po[w]])
                    queue.pop()
                    if ll[v]==po[v]:
                        sf[v]=True
                        scc=[v]
                        while sq and po[sq[-1]]>po[v]:
                            k=sq.pop()
                            sf[k]=True
                            scc.append(k)
                        sl.append(scc)
                    else:
                        sq.append(v)
    return sl