codility

codility.python.py

#[codility]MinAvgTwoSlice


def solution(A):
    # write your code in Python 2.6
    # if one slice is the MA, then the average of its subslices
    # can not be smaller and also it can not be bigger, or the average of the 
    # whole slice will change
    # every slice can be divide into two kinds of subslices, e.g., two-element and three element
    
    globalMinAve = sys.float_info.max
    minIndex = 0
    # try two elements
    for i in xrange(0, len(A)-1):
        localAve = (A[i]+A[i+1])/2.0
        if globalMinAve > localAve:
            globalMinAve = localAve
            minIndex = i
    # try three elements
    for i in xrange(0, len(A)-2):
        localAve = (A[i]+A[i+1]+A[i+2])/3.0
        if globalMinAve > localAve:
            globalMinAve = localAve
            minIndex = i
    return minIndex
    pass



# [codility]GenomicRangeQuery



def solution(S, P, Q):
    # write your code in Python 2.6
    dict = {'A':0, 'C':1, 'G':2, 'T':3}
    nuclSumTable = [[0 for col in range(len(S)+1)] for row in range(4)]
    #print nuclSumTable
    for value in enumerate(S):
        for i in xrange(0, 4):
            nuclSumTable[i][value[0]+1] = nuclSumTable[i][value[0]]
        nuclSumTable[dict[value[1]]][value[0]+1] = nuclSumTable[dict[value[1]]][value[0]]+1
    
    # query based on sum tables
    #print nuclSumTable
    results = [0]*len(P)
    for i in xrange(0, len(P)):
        for nuclIndex in xrange(0, 4):
            if nuclSumTable[nuclIndex][Q[i]+1] > nuclSumTable[nuclIndex][P[i]]:
                results[i] = nuclIndex+1
                break
            
    return results
    pass




#[codility]PassingCars


def solution(A):
    # write your code in Python 2.6
    curZeroCnt = 0
    totalPairs = 0
    for value in A:
        if value == 0:
            curZeroCnt += 1
        else:
            totalPairs += curZeroCnt
    
    if totalPairs > 1000000000:
        return -1
    else:
        return totalPairs
    pass


#[codility]MaxCounters


def solution(N, A):
    # write your code in Python 2.6
    maxCount = 0
    lastMaxSetter = 0
    counters = [0]*N
    for op in A:
        if op == N+1:
            lastMaxSetter = maxCount
        else:
            if counters[op-1] < lastMaxSetter:
                counters[op-1] = lastMaxSetter
            counters[op-1] += 1
            maxCount = max(maxCount, counters[op-1])
    #let last max setter applied to every counter
    for i in xrange(0, N):
        counters[i] = max(counters[i], lastMaxSetter)
    
    return counters
    pass
    


# [codility]FrogRiverOne



def solution(X, A):
    # write your code in Python 2.6
    checkCrucialTable = [False]*X
    crucialCnt = 0
    for i in xrange(0, len(A)):
        if not checkCrucialTable[A[i]-1]:
            checkCrucialTable[A[i]-1] = True
            crucialCnt += 1
            if crucialCnt == X:
                return i
    return -1
    pass
    


#[codility]PermCheck


def solution(A):
    # write your code in Python 2.6
    checkTable = [False]*len(A)
    for value in A:
        if value < 1 or value > len(A):
            return 0
        checkTable[value-1] = True
    
    for flag in checkTable:
        if not flag:
            return 0
    
    return 1
    pass


# [codility]PermMissingElem


def solution(A):
    # write your code in Python 2.6
    curSum = 0
    originalSum = 0
    if len(A)%2 == 0:
        originalSum = (len(A)+1)*((len(A)+2)/2)
    else:
        originalSum = ((len(A)+1)/2)*(len(A)+2)
    for i in xrange(0,len(A)):
        curSum += A[i]
    return originalSum-curSum
    pass



# [codility]FrogJmp


def solution(X, Y, D):
    # write your code in Python 2.6
    dis = Y-X
    if dis%D == 0:
        return dis/D
    else:
        return dis/D+1
    pass


#[codility]TapeEquilibrium



def solution(A):
    # write your code in Python 2.6
    arraySum = sum(A)
    globalMinDiff = sys.maxint
    curSum = 0
    for i in xrange(0, len(A)-1):
        curSum += A[i]
        globalMinDiff = min(globalMinDiff, abs(arraySum-2*curSum))
    return globalMinDiff

# [codility]NailingPlanks



def solution(A, B, C):
    # write your code in Python 2.6
    # for each plank find the nearest nail, to do this
    # we can first binary search the nearest coordinate of nail, 
    # and then traverse the following sorted nail (according to coordinate) to find the nearest            # original nail index until not qualified anymore
    
    # sort nails and keep record of original nail index
    nails = sorted(enumerate(C), key = lambda x: x[1])
    # for each plankIndex find the nail with minimum index
    globalMinimumIndex = 0
    for plankIndex in xrange(0, len(A)):
        localMinimumIndex = getMinimumIndexOfNail(A[plankIndex], B[plankIndex], nails, globalMinimumIndex)
        globalMinimumIndex = max(globalMinimumIndex, localMinimumIndex)
        if globalMinimumIndex == len(C):
            return -1
            
    return globalMinimumIndex+1

def getMinimumIndexOfNail(startPos, endPos, nails, prevResultIndex):
    # using binary search to find the nail with nearest position
    left = 0
    right = len(nails)-1
    while left <= right:
        mid = (right-left)/2+left
        if nails[mid][1] >= startPos:
            right = mid-1
        else:
            left = mid+1
    if left == len(nails) or nails[left][1] > endPos:# can not find a qualified nail
        return len(nails)
    # linear traverse to find the qualified nail with smaller index
    resultIndex = nails[left][0]
    
    for nextPossiblePos in xrange(left+1, len(nails)):
        if nails[nextPossiblePos][1] > endPos:
            break
        resultIndex = min(resultIndex, nails[nextPossiblePos][0])
        if prevResultIndex >= resultIndex:# importan cut off, prevResultIndex is ascending
			return prevResultIndex
    return resultIndex
    


#[codility]MinMaxDivision


def solution(K, A):
    # write your code in Python 2.6
    # each time given an expected minimum sum 'ems',
    # then get the minimum group number 'mgn' we should divide into to meet the 'ems'
    # if 'mgn' <= 'K', then try to decrease 'ems'; else versa;
    left = max(A)
    right = sum(A)
    while left <= right:
        ems = (right-left)/2+left
        rmgn = getMinimumGroupNumber(A, ems)
        if rmgn <= K:# we can decrease 'ems'
            right = ems-1
        else:# we should increase 'ems' to decrease 'rmgn' 
            left = ems+1
    return left

def getMinimumGroupNumber(A, ems):
    rmgn = 0
    curSum = 0
    for x in A:
        curSum += x
        if curSum > ems:
            curSum = x
            rmgn += 1
    if curSum > 0:
        rmgn += 1
    return rmgn