Problème des 100 prisonniers, version naïve et optimale

c05_prisoners.py

''' Fichier de simulation du problème des 100 prisonniers '''
from typing import List
from random import randint, shuffle


def run_simulations(n: int, strategy="naive") -> None:
    """
    Fonction qui effectue un nombre `n` de simulations du problème.
    On peut améliorer cette fonction pour y ajouter un paramètre pour la stratégie à adopter.
    :param n: Un entier qui définit le nombre de simulations à réaliser
    :param strategy: "naive" pour la stratégie naïve (valeur par défaut), "optimal" pour la stratégie optimale.
    """
    successful_simulation_count: int = 0
    for i in range(n):
        print(f"Simulation number: {i}")
        if run_simulation(strategy):
            successful_simulation_count += 1
    print(f"Nombre de simulations réussies: {successful_simulation_count}")
    print(f"Chances de succès: {successful_simulation_count/n}")


def run_simulation(strategy="naive") -> bool:
    """
    Fonction qui effectue une simulation du problème.
    On peut améliorer cette fonction pour y ajouter un paramètre pour la stratégie à adopter.
    :param strategy: "naive" pour la stratégie naïve (valeur par défaut), "optimal" pour la stratégie optimale.
    :return: Vrai si tous les prisonniers ont trouvé leur clé, Faux sinon
    """
    nb_prisoners: int = 100
    boxes: List[int] = list(range(nb_prisoners))
    shuffle(boxes)
    count_successful_prisoners: int = 0
    for p in range(nb_prisoners):
        if strategy == "naive":
            if simulate_naive_prisoner(boxes, p):
                count_successful_prisoners += 1
        elif strategy == "optimal":
            if simulate_optimal_prisoner(boxes, p):
                count_successful_prisoners += 1
    return count_successful_prisoners == nb_prisoners


def simulate_naive_prisoner(boxes: list[int], p: int) -> bool:
    """
    Fonction qui simule le comportement d'un prisonnier adoptant une stratégie naïve.
    cette fonction a été modifiée par rapport à ce qui a été produit en cours, afin de 
    mieux modéliser le choix aléatoire de la prochaine boîte à chaque essai.
    :param boxes: Liste d'entiers symbolisant les boîtes.
    :param p: Un entier représentant le prisonnier simulé.
    :return: Vrai si le prisonnier trouve sa clé en moins de 50 tentatives, Faux sinon.
    """
    attempt_number: int = 0
    # Cette variable va prendre toutes les boîtes ouvertes par un prisonnier
    # Cela nous permet de nous assurer que le tirage aléatoire ne donne pas deux fois la même boîte
    opened_boxes: List[int] = []
    while attempt_number < 50:
        box_number: int = randint(0, 99)
        # Tant que box_number pointe vers une boîte déjà ouverte par le prisonnier,
        # on génère un autre nombre aléatoire
        while box_number in opened_boxes:
            box_number = randint(0, 99)
        key = boxes[box_number]
        if key == p:
            return True
        attempt_number += 1
    return False


""" Version construite durant le cours
def simulate_naive_prisoner(boxes: list[int], p: int) -> bool:
    boxes_to_open: list[int] = list(range(100))
    shuffle(boxes_to_open)
    attempt_number: int = 0
    while attempt_number < 50:
        key = boxes[boxes_to_open[attempt_number]]
        if key == p:
            return True
        attempt_number += 1
    return False
"""


def simulate_optimal_prisoner(boxes: List[int], p: int) -> bool:
    """
    Fonction qui simule le comportement d'un prisonnier adoptant la stratégie optimale.
    :param boxes: Liste d'entiers symbolisant les boîtes.
    :param p: Un entier représentant le prisonnier simulé
    :return: Vrai si le prisonnier trouve sa clé en moins de 50 tentatives, Faux sinon.
    """
    attempt_number: int = 0
    key = p
    while attempt_number < 50:
        key = boxes[key]
        if key == p:
            return True
        attempt_number += 1
    return False



run_simulations(1000, strategy="optimal")