Poison Bottles

poison_bottles.py

def find_poisoned_bottle(bottles):
    """
    Find position of the poisonous wine bottle in 1000 bottles, using 10 strips, given that there
    is only 1 poisonous bottle of the 1000 bottles.
    
    The logic is to line up all 10 strips and represent them as binary numbers, with each strip in a position for the 
    binary numbers. Then, each wine bottle is labeled from 1-1000. Since 2^10 is the first power of 2 that is greater than 1000,
    10 strips are sufficient and we only need to test once with all 10 strips, and then wait 1 week for the test results to come back.
    Then, aligning the strips in the same order as before, there will be a sequence of positive and negative strips. Converting that
    sequence from binary (with positive as 1's and negative as 0's) back into decimal form, we will have the index of the poisoned 
    wine bottle. Thus, it only takes 1 test to find the poisoned bottle using all 10 strips, which is 1 week in total.
    
    For example, if the poisoned bottle is the last bottle at position 1000, then the binary representation of 1000 is 1111101000, and so
    the strips in positions with 1's will turn positive a week later after we drop the poison. Once we get this result back, we can deduce
    that the poisoned wine position is 1000, since we just convert 1111101000 back to decimal form.
    
    :param bottles (list): list of 1000 bottles with 1's as poisonous and 0's as non-poisonous
    :return (int): index of the poisonous bottle
    """
    assert len(bottles)==1000, "Input bottles must be length 1000."
    assert set(bottles)==set(0, 1), "Input bottles must only contain binary values."
    num_strips = 10  # total number of strips
    strips = [0 for _ in range(num_strips)]  # strips at 10 positions to represent binary numbers
    for i, bottle in enumerate(bottles):
        binary_position = "{0:b}".format(i+1)  # binary value of bottle position
        # we drop the wine onto each strip with 1 as the position for the binary value
        if bottle==0:
            # if the bottle is non-poisonous, then nothing will happen to the strips
            continue
        elif bottle==1:
            # if the bottle is poisonous, then the strips with 1 as the position will be poisoned and turn positive
            # the sequence of strips will represent the position of the poisoned wine bottle
            strips = [positive for positive in binary_position]
            
    # after 1 week, the strip results come back, and we have a binary representation of the 10 strips, with poisoned strips
    # being 1's and unpoisoned strips being 0's; we convert this back to decimal representation
    
    # return position of the poisonous wine bottle
    return int(''.join(strips), 2)