import random

### Une histoire de probabilités…

def mains(n):
    liste = [False] * (2*n-3) + [True] * 3
    random.shuffle(liste)
    return liste[:n], liste[n:]

# Exercice 1

def repetitions(n=10, nb=10000):
    reussites = 0
    for _ in range(nb):
        gauche, droite = mains(n)
        nb_gauche = 0
        for i in range(n):
            if gauche[i]:
                nb_gauche += 1
        if nb_gauche == 0 or nb_gauche == 3:
            reussites += 1
    return reussites

def estimation_probabilite(n=10, nb=10000):
    return repetitions(n, nb) / nb

print("Test pour l'exercice 1 (avec n = 10) :", estimation_probabilite())

# Exercice 2

def coeff_bin(n, k):
    if k < 0 or n < k:
        return 0
    numer = 1
    denom = 1
    for i in range(k):
        numer *= n-i
        denom *= k-i
    return numer // denom

# Exercice 3

def calcul_probabilite(n=10):
    return 2 * coeff_bin(2*n-3, n-3) / coeff_bin(2*n, n)

def calcul_probabilite_simplifie(n=10): # En manipulant les calculs…
    return (n-2) / (4*n - 2)

print("Test pour l'exercice 3 (avec n = 10) :", calcul_probabilite())

# Exercice 4

# Grâce aux formules générales déjà implémentées dans les exercices 1 et 3, c'est immédiat !

print("Tests pour l'exercice 4 (avec n = 13) : estimation", estimation_probabilite(13), "et valeur", calcul_probabilite(13))

# Exercice 5

# Idem

print("Tests pour l'exercice 5 (avec n = 3) : estimation", estimation_probabilite(3), "et valeur", calcul_probabilite(3))

print("Par principe, avec n = 2 : estimation", estimation_probabilite(2), "et valeur", calcul_probabilite(2))

# Exercice 6

# Idem

print("Test pour l'exercice 6 avec n = 100 : estimation", estimation_probabilite(100), "et valeur", calcul_probabilite(100))
print("Test pour l'exercice 6 avec n = 1000 : estimation", estimation_probabilite(1000, 1000), "et valeur", calcul_probabilite(1000))
print("Test pour l'exercice 6 avec n = 10000 : estimation", estimation_probabilite(10000, 100), "et valeur", calcul_probabilite_simplifie(10000)) # Au bout d'un moment, c'est le calcul qui prend le plus de temps !
print("Test pour l'exercice 6 avec n = 100000 : estimation", estimation_probabilite(100000, 50), "et valeur", calcul_probabilite_simplifie(100000))
print("Test pour l'exercice 6 avec n = 1000000 : estimation", estimation_probabilite(1000000, 20), "et valeur", calcul_probabilite_simplifie(1000000))

### Le jeu de Yam's

# Exercice 7

def est_yams(lancer):
    for i in range(1, len(lancer)): # ou 5…
        if lancer[i] != lancer[i-1]:
            return False
    return True

# Exercice 8

def engendre_lancer():
    return [random.randint(1, 6) for _ in range(5)]

def teste_lancers(n):
    reussites = 0
    for _ in range(n):
        if est_yams(engendre_lancer()):
            reussites += 1
    return reussites

# Exercice 9

def maximum_des_identiques(lancer):
    effectifs = [0] * 6 # compteurs, pour faire un seul parcours
    for face in lancer:
        effectifs[face-1] += 1 # changement d'indice
    return max(effectifs) # ou une boucle…

# Exercice 10

def proba_yams(lancers): # La fonction n'est pas nécessaire, on peut aussi faire les calculs en-dehors. Pour que cela ait de l'intérêt, on considère un nombre d'essais en argument
    assert lancers >= 1 # déclenche une erreur si on autorise moins d'un lancer
    probas_lancers = [[120/1296, 900/1296, 250/1296, 25/1296, 1/1296]] # indice i : avoir i+1 dés identiques au premier lancer
    for i in range(1, lancers):
        probas_lancers.append([])
        probas_lancers[i].append(probas_lancers[i-1][0] * 120/1296) # de 1 à 1
        probas_lancers[i].append(probas_lancers[i-1][0] * 900/1296 + probas_lancers[i-1][1] * 120/216) # de 1 à 2 et de 2 à 2
        probas_lancers[i].append(probas_lancers[i-1][0] * 250/1296 + probas_lancers[i-1][1] * 80/216 + probas_lancers[i-1][2] * 25/36) # de 1 à 3, de 2 à 3 et de 3 à 3
        probas_lancers[i].append(probas_lancers[i-1][0] * 25/1296 + probas_lancers[i-1][1] * 15/216 + probas_lancers[i-1][2] * 10/36 + probas_lancers[i-1][3] * 5/6) # on aura compris
        probas_lancers[i].append(probas_lancers[i-1][0] * 1/1296 + probas_lancers[i-1][1] * 1/216 + probas_lancers[i-1][2] * 1/36 + probas_lancers[i-1][3] * 1/6 + probas_lancers[i-1][4]) # penser à ajouter le cas du Yam's déjà atteint
    return probas_lancers[lancers-1][4] # après le nombre de lancers prévu, la dernière probabilité est celle d'avoir un Yam's

# >>> proba_yams(3)
# 0.04602864252569899

# Exercice 11

# Pour simplifier, on considère que la valeur des dés verrouillés est arbitrairement 1.

def frequence_yams(essais): # 3 lancers ici
    reussites = 0
    for _ in range(essais): # Le contenu n'est pas "factorisé" pour pouvoir imprimer des valeurs intermédiaires et observer les probabilités précédentes…
        lancer1 = engendre_lancer()
        n1 = maximum_des_identiques(lancer1)
        lancer2 = [1] * n1 + [random.randint(1, 6) for _ in range(5-n1)]
        n2 = maximum_des_identiques(lancer2)
        lancer3 = [1] * n2 + [random.randint(1, 6) for _ in range(5-n2)]
        if maximum_des_identiques(lancer3) == 5:
            reussites += 1
    return reussites / essais

print(frequence_yams(10000)) # On attend environ 460 réussites d'où une fréquence de 0.046 environ.

# Exercice 12

# Réponse mathématique : on a une loi binomiale de paramètres (13, p) où p est environ 0.046. La probabilité de n'avoir aucun succès est (1-p)^13, et celle d'en avoir exactement un est 13p(1-p)^12. On en déduit la valeur attendue.
# Par ailleurs, puisque le dénominateur est forcément une puissance de 6 inférieure à 12, on peut tenter de reconstituer le numérateur sans détailler les calculs, et on tombe visiblement sur 2783176 divisés par 6 puissance 10.
# La probabilité d'avoir deux Yam's au moins est donc légèrement inférieure à 12 %.

def frequence_deux_yams_sur_13(essais): # infâme copier-coller
    reussites = 0
    for _ in range(essais):
        succes = 0
        for _ in range(13):
            lancer1 = engendre_lancer()
            n1 = maximum_des_identiques(lancer1)
            lancer2 = [1] * n1 + [random.randint(1, 6) for _ in range(5-n1)]
            n2 = maximum_des_identiques(lancer2)
            lancer3 = [1] * n2 + [random.randint(1, 6) for _ in range(5-n2)]
            if maximum_des_identiques(lancer3) == 5:
                succes += 1
        if succes >= 2:
            reussites += 1
    return reussites / essais

print(frequence_deux_yams_sur_13(10000)) # Premier test : 0.1192, très proche de la véritable probabilité, cela fait plaisir !

### Un peu de dénombrement…

# Exercice 13

def est_surjection(liste, k):
    effectifs = [0] * k # cf. exercice 9 pour le principe
    for element in liste:
        effectifs[element] += 1 # en vrai, on aurait pu utiliser des booléens
    for valeur in effectifs: # on cherche des éléments n'ayant pas d'antécédent
        if valeur == 0:
            return False
    return True

# Exercice 14

def compte_surjections(n, k):
    nombre_surjections = 0
    fonction = [0] * n # principe pour engendrer les fonctions : compter comme en base n
    while True: # pas de souci, on quittera la fonction autrement
        if est_surjection(fonction, k):
            nombre_surjections += 1
        fonction[n-1] += 1
        indice = n-1
        while indice >= 0 and fonction[indice] == k:
            fonction[indice] = 0
            indice -= 1
            fonction[indice] += 1
        if indice == -1:
            return nombre_surjections

# Exercice 15

# On réutilise la fonction coeff_bin de la première partie !

def calcule_nombre_surjections(n, k):
    if n == k == 0:
        return 1
    if n < k or k == 0: # au moins c'est fait !
        return 0
    reponses = [0, 1] # reponse[i] sera le nombre de surjections d'un ensemble de taille n dans un ensemble de taille i
    for i in range(2, k+1): # utilisation de la formule de récurrence pour chaque i intermédiaire
        reponse_pour_i = i ** n
        for j in range(i):
            reponse_pour_i -= coeff_bin(i, j) * reponses[j]
        reponses.append(reponse_pour_i)
    return reponses[k]