Holes in a Roof, Problem 2 (Binary Search)

In [1]:

### Problem 2: 
### You are given N binary values in a list. This list represents holes in a roof (1 is a hole). 
### You are also given K equal-length boards which you can use to cover these holes.
### The goal is to determine the optimum (minimum) length these boards must be to cover the holes.

# This problem is solved by using Binary Search to try various lengths.
# The "boardsNeeded" function from Problem 1 can be used to see how many boards 
# of that length are required.  If the number of boards required is <= K, then the 
# trial length is valid, and can try a shorter length.  If the number of
# boards required > K, then you need to increase the length.
 
# You may want to try coding your own solution without looking at the answer,
# otherwise implement and understand the following code


# this function is copied over from Problem 1
def boardsNeeded(binarr, M):
    
    N = len(binarr)
    boards = 0
    last = -1
    for i in range(N):
        if binarr[i] == 1 and last < i:
            boards += 1
            last = i + M - 1
            
    return boards

# here is the new code for problem 2
def lengthNeeded(binarr, K):
    
    N = len(binarr)
    p1 = 1
    p2 = N
    result = -1
    while(p1 <= p2):
        mid = (p1 + p2) // 2
        if( boardsNeeded(binarr, mid) <= K ):
            # board length = mid worked!  
            # we covered all the holes with K boards or less
            # save solution and try a shorter length
            result = mid
            p2 = mid - 1
        else: 
            # board length = mid did not work!
            # try a longer length
            p1 = mid + 1
            
    return result
        
testlist = [0,0,0,1,1,1,1,0,0,1,1,0,0,0,0,0,0,0,1,1,0,0,0,1,0,1,0,1,0,0,0]
testK = 4

answer = lengthNeeded(testlist,testK)
print("The minimum length required is",answer,"to cover all holes with",testK, "equal-length boards")

The minimum length required is 5 to cover all holes with 4 equal-length boards