100 Prisoners Solution Python 3.10 ( Single File )

hundred_prisoners.py

from random import randint
from time import time_ns
import sys
import argparse

try:
    import loguru  # loguru==0.7.0

    logger = loguru.logger
    logger.remove()
    logger.add(sys.stderr, level="INFO")
except Exception as e:
    import logging

    logging.basicConfig(format='%(asctime)s - %(levelname)s - %(message)s', level=logging.INFO)
    logger = logging.getLogger("100Prisoners")
    logger.setLevel(logging.INFO)


def timer_func(func):
    # This function shows the execution time of
    # the function object passed
    def wrap_func(*args, **kwargs):
        t1 = time_ns()
        result = func(*args, **kwargs)
        t2 = time_ns()
        exec_time = t2 - t1
        logger.debug(f'Function {func.__name__!r} executed in {(exec_time):.4f}s')
        return exec_time, result

    return wrap_func


# A function to generate a random permutation of arr[]
def shuffle_via_fisher_yates(card_deck):
    end = len(card_deck) - 1
    # Start from the last element and swap one by one. We don't
    # need to run for the first element that's why i > 0
    for i in range(end - 1, 0, -1):
        # Pick a random index from 0 to i
        j = randint(0, i + 1)
        # Swap arr[i] with the element at random index
        card_deck[i], card_deck[j] = card_deck[j], card_deck[i]
    return card_deck


def build_card_deck(deck_size):
    """
    Build a deck of cards that has deck_size number of cards
    :param deck_size: How many cards will be in the deck.
    :return: A non shuffled deck of cards.
    """
    card_stack = []
    for x in range(deck_size):
        card_stack.append(x)
    return card_stack


def build_card_box_holder(box_size):
    """
    Builds a card box holder where there is one box per card
    :param box_size: number of boxes that will be created with one random card per box
    :return:
    """
    box_holder = []
    deck = build_card_deck(box_size)
    deck = shuffle_via_fisher_yates(deck)
    for x in range(box_size):
        box_holder.append(deck.pop())
    return box_holder


def single_execution_run_with_holder(box_holder, prisoner_number, num_tries_per_prisoner):
    """
    Runs a single iteration of the game
    :param box_holder: a holder which is an array with one randomized card number per element
    :param prisoner_number: number of prisoners
    :param num_tries_per_prisoner number of attempts each prisoner gets
    :return: true| false if successful
    """
    successful = True
    x = 0
    while x < prisoner_number and successful is True:
        next_card = box_holder[x]
        # num_of_prisoner_tries = int(round(prisoner_number / 2))
        y = 0
        while y < num_tries_per_prisoner:
            if next_card != x:
                next_card = box_holder[next_card]
            else:
                # prisoner found their card.
                break
            y += 1
        if next_card != x:
            successful = False
        x += 1
    return successful


def single_execution_run(prisoner_number, num_tries_per_prisoner):
    """
    A single execution of the game which will generate its own box holder
    :param prisoner_number: Number of prisoners
    :param num_tries_per_prisoner number of attempts each prisoner gets
    :return:
    """
    return single_execution_run_with_holder(build_card_box_holder(prisoner_number), prisoner_number,
                                            num_tries_per_prisoner)


def execute(args):
    speed_average = 0
    successes = 0
    if args.include_rand_gen_in_time:
        game_func = timer_func(single_execution_run)
        for x in range(args.num_iterations):
            exec_time, successful = game_func(args.num_prisoners, int(round(args.num_prisoners / 2)))
            if successful:
                successes += 1
            speed_average += exec_time
    else:
        game_func = timer_func(single_execution_run_with_holder)
        for x in range(args.num_iterations):
            holder = build_card_box_holder(args.num_prisoners)
            exec_time, successful = game_func(holder, args.num_prisoners, int(round(args.num_prisoners / 2)))
            if successful:
                successes += 1
            speed_average += exec_time
    success_percentage = float(successes / args.num_iterations) * 100
    speed_average = float(speed_average / args.num_iterations)
    execution_print = [args.num_prisoners,
                       str(args.num_iterations),
                       str(speed_average) + 'ns',
                       success_percentage]
    logger.info(
        "Execution complete. P={: <10} I={:<10} Time(avg)={: <20} SuccessPercent={: <10}".format(*execution_print))


def str2bool(v):
    if isinstance(v, bool):
        return v
    if v.lower() in ('yes', 'true', 't', 'y', '1'):
        return True
    elif v.lower() in ('no', 'false', 'f', 'n', '0'):
        return False
    else:
        raise argparse.ArgumentTypeError('Boolean value expected.')


def parse_args(args):
    parser = argparse.ArgumentParser('100Prisoners')
    parser.add_argument("--num_prisoners",
                        required=False,
                        default=100,
                        type=int,
                        help="Number of prisoners to run the game for.")
    parser.add_argument("--num_iterations",
                        required=False,
                        default=100,
                        type=int,
                        help="Number of iterations to run the game for.")
    parser.add_argument("--include_rand_gen_in_time",
                        required=False,
                        default=False,
                        type=str2bool,
                        help="Should random generation be included in time results.")
    return parser.parse_args(args)


def build_args_array(p, i):
    return ["--num_prisoners={}".format(p), "--num_iterations={}".format(i)]


def main():
    logger.info("Beginning 100 Prisoners Problem")
    logger.info("""
    The director of a prison offers 100 death row prisoners, who are numbered from 1 to 100, a last chance.
    A room contains a cupboard with 100 drawers. The director randomly puts one prisoner's number in each closed drawer.
    The prisoners enter the room, one after another. Each prisoner may open and look into 50 drawers in any order.
    The drawers are closed again afterwards. If, during this search, every prisoner finds their number in one of the
    drawers, all prisoners are pardoned. If even one prisoner does not find their number, all prisoners die. Before the
    first prisoner enters the room, the prisoners may discuss strategy — but may not communicate once the first prisoner
    enters to look in the drawers. What is the prisoners' best strategy?
    """)

    logger.info("""
    This solution uses the following strategy, not only the prisoners, but also the drawers, are numbered from 1 to 100;
    for example, row by row starting with the top left drawer. 
    The strategy is now as follows:
    \t 1.Each prisoner first opens the drawer labeled with their own number.
    \t 2.If this drawer contains their number, they are done and were successful.
    \t 3.Otherwise, the drawer contains the number of another prisoner, and they next open the drawer labeled with this number.
    \t 4.The prisoner repeats steps 2 and 3 until they find their own number, or fail because the number is not found in the first fifty opened drawers.
    By starting with their own number, the prisoner guarantees they are on the unique permutation cycle of drawers
    containing their number. The only question is whether this cycle is longer than fifty drawers.
    """)

    args = sys.argv[1:]
    if len(args) > 0:
        args = parse_args(sys.argv[1:])
        execute(args)
    else:
        args = parse_args(build_args_array(100, 1))
        execute(args)
        args = parse_args(build_args_array(100, 10))
        execute(args)
        args = parse_args(build_args_array(100, 100))
        execute(args)
        args = parse_args(build_args_array(100, 1_000))
        execute(args)
        args = parse_args(build_args_array(100, 10_000))
        execute(args)
        args = parse_args(build_args_array(100, 100_000))
        execute(args)
    logger.info("100 Prisoners Problem Complete")


# Press the green button in the gutter to run the script.
if __name__ == '__main__':
    main()

Problem

The director of a prison offers 100 death row prisoners, who are numbered from 1 to 100, a last chance.
A room contains a cupboard with 100 drawers. The director randomly puts one prisoner's number in each closed drawer.
The prisoners enter the room, one after another. Each prisoner may open and look into 50 drawers in any order.
The drawers are closed again afterwards. If, during this search, every prisoner finds their number in one of the
drawers, all prisoners are pardoned. If even one prisoner does not find their number, all prisoners die. Before the
first prisoner enters the room, the prisoners may discuss strategy — but may not communicate once the first prisoner
enters to look in the drawers. What is the prisoners' best strategy?

Solution Used

    This solution uses the following strategy, not only the prisoners, but also the drawers, are numbered from 1 to 100;
    for example, row by row starting with the top left drawer. 
    The strategy is now as follows:
    	 1.Each prisoner first opens the drawer labeled with their own number.
    	 2.If this drawer contains their number, they are done and were successful.
    	 3.Otherwise, the drawer contains the number of another prisoner, and they next open the drawer labeled with this number.
    	 4.The prisoner repeats steps 2 and 3 until they find their own number, or fail because the number is not found in the first fifty opened drawers.
    By starting with their own number, the prisoner guarantees they are on the unique permutation cycle of drawers
    containing their number. The only question is whether this cycle is longer than fifty drawers.
    ```

Results:

P = Number of Prisoners
I = Number of Iterations
Time(avg) = Average speed of one iteration over N iterations

Execution complete. P=100        I=1          Time(avg)=10467.0ns            SuccessPercent=0.0       
Execution complete. P=100        I=10         Time(avg)=37836.9ns            SuccessPercent=10.0      
Execution complete. P=100        I=100        Time(avg)=146416.87ns          SuccessPercent=40.0      
Execution complete. P=100        I=1000       Time(avg)=118677.438ns         SuccessPercent=31.5      
Execution complete. P=100        I=10000      Time(avg)=127125.3206ns        SuccessPercent=33.35     
Execution complete. P=100        I=100000     Time(avg)=128619.12711ns       SuccessPercent=33.277