Barn Repair

With one board, we have to cover all the unoccupied stalls.

With two boards, we skip the largest segment of consecutive empty stalls.

With three boards, we skip the largest and second-largest segments of consecutive empty stalls.

Therefore, our algorithm is:

1) Create a list of all the segments of consecutive empty stalls.

2) Sort the list by length from largest to smallest.

3) Since with N boards we can skip N-1 segments of stalls, we remove the first N-1 entries from the list.

4) Output the sum of the number of occupied stalls and the sum of the rest of the list.

def generateString(c,occupied):
    res = [' ']*c
    for i in occupied:
        res[i-1] = '#'
    print(''.join(i for i in res))
    return res

def consecutiveEmpty(s):
    new = []
    lastSwitch = -1
    firstStallIndex=s.index('#')
    for i in range(firstStallIndex,len(s)-1):
        if s[i] != s[i+1]:
            if s[i] == ' ':
                new.append(i-lastSwitch)
            lastSwitch = i
    return sorted(new)

def parseInput(filename):
    with open(filename,'r') as fIn:
        i = fIn.read().split('\n')
    maxBoards,numStalls,numOccupied = list(map(int,i[0].split()))
    occupied = []
    for line in i[1:-1]:
        occupied.append(int(line))
    return maxBoards,numStalls,occupied,numOccupied

def main():
    maxBoards,numStalls,occupied,numOccupied = parseInput('barn1.in')
    s = generateString(numStalls,occupied)
    emptyStalls = consecutiveEmpty(s)
    print(emptyStalls)
    res = 0
    print(emptyStalls[0:maxBoards])
    for i in emptyStalls[0:len(emptyStalls)-maxBoards+1]:
        res += i
    print(res+numOccupied)
    with open('barn1.out','w') as fOut:
        fOut.write(str(res+numOccupied)+'\n')

if __name__ == '__main__':
    main()