foobar_4-1_free_the_bunny_prisoners.py 文件源码

def answer(num_buns, num_required):
    """
    To start this problem, we calculate the number of ways we can arrange bunnies. This is:
        num_buns choose num_required

    This number determines how many distinct keys we have. So we then need to lexicographically hand off keys to each
    bunny and deputize them with the powers to open locks.

    At that point, this problem comes down to deciding how many keys to hand to each bunny. I had to think about that
    by hand.

    :param num_buns: The number of bunnies to distribute keys to.
    :param num_required: The "choose" part of our combinatorial.
    :return: bunny_keyrings, the enumerated keys belonging to each bunny in num_buns.
    """
    # One keyring per bunny.
    bunny_keyrings = [[] for num in range(num_buns)]
    # The number of keys each bunny requires is described by this formula, which I noticed by doing some napkin math.
    # If N == 4 and M == 4, bunnies_per_key == 1.
    # If N == 2 and M == 1, bunnies_per_key == 2.
    # If N == 5 and M == 3, bunnies_per_key == 3.
    # This generally fit the formula bunnies_per_key = N - M + 1.
    bunnies_per_key = num_buns - num_required + 1

    # itertools' enumerate function:
    # def enumerate(sequence, start=0):
    #     n = start
    #     for elem in sequence:
    #         yield n, elem
    #         n += 1
    # This yields a generator! So by generating combinations one at a time, we will get num_buns choose num_required
    # different permutations of num_buns, and we can assign each one as a bunny's keyring. Since this covers all
    # combinations, it should also assure that in all situations, if we pick num_required bunnies, they will all have
    # enough keys to open a cell.
    for keynum, keyholders in enumerate(combinations(range(num_buns), bunnies_per_key)):
        # print(keynum, keyholders)
        for index in keyholders:
            bunny_keyrings[index].append(keynum)

    return bunny_keyrings