100 Prisoners Problem in Python

"""
My attempt at testing the 100 prisoners problem and the solutions proposed.


From Wikipedia:
"The 100 prisoners problem is a mathematical problem in probability theory and combinatorics. In this problem, 100 numbered
prisoners must find their own numbers in one of 100 drawers in order to survive. The rules state that each prisoner may open
only 50 drawers and cannot communicate with other prisoners. At first glance, the situation appears hopeless, but a clever
strategy offers the prisoners a realistic chance of survival. Danish computer scientist Peter Bro Miltersen first proposed
the problem in 2003."

"If every prisoner selects 50 drawers at random, the probability that a single prisoner finds their number is 50%. Therefore,
the probability that all prisoners find their numbers is the product of the single probabilities, which is
(1/2)100 ≈ 0.0000000000000000000000000000008, a vanishingly small number. The situation appears hopeless."

"Surprisingly, there is a strategy that provides a survival probability of more than 30%. The key to success is that the
prisoners do not have to decide beforehand which drawers to open. Each prisoner can use the information gained from the contents
of every drawer they already opened to decide which one to open next. Another important observation is that this way the success
of one prisoner is not independent of the success of the other prisoners, because they all depend on the way the numbers are
distributed.[2]

To describe the 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:[3]

Each prisoner first opens the drawer labeled with their own number.
If this drawer contains their number, they are done and were successful.
Otherwise, the drawer contains the number of another prisoner, and they next open the drawer labeled with this number.
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 sequence of drawers containing their number.
The only question is whether this sequence is longer than fifty drawers."

"The reason this is a promising strategy is illustrated with the following example using 8 prisoners and drawers, whereby each
prisoner may open 4 drawers. The prison director has distributed the prisoners' numbers into the drawers in the following fashion:

number of drawer 1 2 3 4 5 6 7 8
number of prisoner 7 4 6 8 1 3 5 2

The prisoners now act as follows:

Prisoner 1 first opens drawer 1 and finds number 7. Then they open drawer 7 and find number 5. Then they open drawer 5, where
they find their own number and are successful.
Prisoner 2 opens drawers 2, 4, and 8 in this order. In the last drawer they find their own number 2.
Prisoner 3 opens drawers 3 and 6, where they find their own number.
Prisoner 4 opens drawers 4, 8, and 2, where they find their own number. This is the same cycle encountered by prisoner 2, but
they aren't aware of it.
Prisoners 5 to 8 will also each find their numbers in a similar fashion.
In this case, all prisoners find their numbers. This is, however, not always the case. For example, the small change to the
numbers of swapping drawers 5 and 8 would cause prisoner 1 to fail after opening 1, 7, 5, and 2 (and not finding their own number)"


"Therefore, using the cycle-following strategy the prisoners survive in a surprising 31% of cases."

https://en.wikipedia.org/wiki/100_prisoners_problem
"""

import random
import time
import sys


###################################################
#### SET HERE THE AMOUNT OF TRIES YOU WANT     ####
#### SUGGEST NUMBERS: 1_000, 10_000, 1_000_000 ####
###################################################

num_of_tries: int = 10_000


#
##  Creates a list with numbers 1-100, ordered structure
##  Returns an ordered list of integers
#
def create_ordered_number_list() -> list[int]:
    return list(range(1, 101))


#
##  Shuffles the list around with true RNG from systemcall
##  Returns an unordered list of integers
#
def create_shuffle_list(numbers: list[int]) -> list[int]:
    # create true RNG via system call
    rng = random.SystemRandom()

    # copy the ordered list
    new_list = numbers.copy()

    # shuffle it around to create a random list
    rng.shuffle(new_list)

    return new_list


#
## Creates the randomized boxes
## returns a dict of integers
#
def create_boxes(box_numbers: list[int], papers: list[int]) -> dict[int, int]:
    # create the empty dict
    boxes: dict[int, int] = {}

    # helper variable
    counter: int = 0

    while counter < 100:

        # binds the box_number number to the paper number
        boxes[box_numbers[counter]] = papers[counter]
        counter += 1

    return boxes


#
## Opens the box with the current number, returns true if the number is found
#
def check_box(boxes: dict[int, int], cur_num: int, box_num: int) -> bool:
    return boxes[box_num] == cur_num


#
## Opens the box with the current number, returns the number inside
#
def next_box(boxes: dict[int, int], cur_num: int) -> int:
    return boxes[cur_num]


#
## every prisoner can open a maximum of 50 boxes
## returns true if they find the number within 50
## tries
#
def open_boxes(boxes: dict[int, int], prisoner: int) -> bool:
    # a maximum of 50 tries, start with 1 for the DEBUG statements
    tries: int = 1

    # we start with opening the box with the same number
    # as the prisoner
    box_num: int = prisoner

    while tries <= 50:
        # we check if the number inside the box is the number we want
        if check_box(boxes, prisoner, box_num):

            # DEBUG: UNCOMMENT TO FOLLOW THE PRISONERS LOOP
            #
            # print(
            #    f"prisoner #{prisoner} found his number in box #{box_num} on try #{tries}"
            # )
            return True

        else:
            # DEBUG: UNCOMMENT TO FOLLOW THE PRISONERS LOOP
            # print(
            #    f"({tries}): prisoner #{prisoner} found number #{boxes[box_num]} in box #{box_num}"
            # )

            # if not, we go to the next box
            box_num = next_box(boxes, box_num)

            # increase the tries
            tries += 1

    # if we ran through the whole loop we failed and return False
    return False


def hundred_prisoners_problem(ordered_list: list[int]) -> bool:
    # see how long the script took to run
    start: time = time.time()

    # statistics of failed and passed attempts
    failed: int = 0
    passed: int = 0

    # we'll do the loop 10,000 times. The statistics should still work for
    # 100,000, 1,000,000 times etc, with roughly the same percentage

    for i in range(num_of_tries):

        # the program will take a bit of time when the num_of_tries is above 10_000
        # so we print the current attempt to show progress
        sys.stdout.write("\rAttempt #" + str(i + 1) + "\r")
        sys.stdout.flush()

        # for every run we create new randomized prisoners, box numbers and papers
        # and add them into boxes
        prisoners: list[int] = create_shuffle_list(ordered_list)
        box_numbers: list[int] = create_shuffle_list(ordered_list)
        papers: list[int] = create_shuffle_list(ordered_list)
        boxes: dict[int, int] = create_boxes(box_numbers, papers)

        # we add a variable to keep track if a prisoner has failed his loop
        # then we break the loop and add it to the failed statistics
        prisoner_failed: bool = False

        for prisoner in range(100):
            if open_boxes(boxes, prisoners[prisoner]):
                continue
            else:
                prisoner_failed = True
                break

        if prisoner_failed:
            failed += 1
        else:
            passed += 1

    end: time = time.time()
    total_time: float = end - start
    sys.stdout.flush()
    print("\r\n")

    # we print in seconds because i'm lazy
    print(f"\rThe script took {total_time:.2f} seconds to run")
    print(f"Failed attempts: {failed}, passed attempts: {passed}")
    print(f"The full loop worked about {(passed / num_of_tries) * 100}% of the time")


lst: list[int] = create_ordered_number_list()
hundred_prisoners_problem(lst)