import random
import matplotlib.pyplot as plt

# Exercice 1

def pi_monte_carlo(nombre_points, dessin=False):
    """Détermine une approximation de pi par une méthode de Monte-Carlo
    en engendrant des couples de réels entre 0 et 1 (exclus) et en déterminant
    quelle proportion est dans le quart de disque délimité par le cercle
    trigonométrique.
    Pour l'esthétique, quand l'argument optionnel demandant s'il faut faire
    une représentation graphique est à vrai, un signe arbitraire est ajouté
    aux coordonnées avant le dessin.
    Rappel : la fréquence d'appartenance au disque est pi / 4."""
    dedans = 0
    if dessin:
        lx, ly = [[], []], [[], []] # abscisses dehors, absisses dedans, idem ordonnées
    for _ in range(nombre_points):
        x = random.random()
        y = random.random()
        reussite = x**2 + y**2 < 1 # ne sera a priori jamais égal
        dedans += reussite # 1 ou 0
        if dessin:
            lx[reussite].append(x * random.choice([-1, 1]))
            ly[reussite].append(y * random.choice([-1, 1]))
    if dessin:
        plt.plot(lx[0], ly[0], "rx")
        plt.plot(lx[1], ly[1], "gx")
        plt.show()
    return 4 * dedans / nombre_points

# Exercice 2

arborescence = [(True, [1, 2, 3], 0), (False, [4, 5, 6], 0), (False, [7, 8, 9], 0), (False, [10, 11, 12], 0), (True, [], 10), (True, [], 42), (True, [], 7), (True, [], 19), (True, [], 12), (True, [], 18), (True, [], 6), (True, [], 4), (True, [], 88)]

# Exercice 3

def minmax(arbre):
    """Algorithme minmax pour la représentation d'une arborescence
    sous forme de liste de triplets (J, succ, val), où J est un booléen
    indiquant le propriétaire du sommet (True est le joueur voulant maximiser),
    succ est la liste des indices où se trouvent les successeurs du sommet
    et val est la valeur du sommet (fixée à 0 sauf si le sommet n'a pas
    de successeurs).
    """
    def aux(indice): # top-down
        (joueur, suivants, valeur) = arbre[indice]
        if suivants:
            valeurs = []
            for sommet in suivants:
                aux(sommet)
                valeurs.append(arbre[sommet][2])
            if joueur:
                nouvelle_valeur = max(valeurs)
            else:
                nouvelle_valeur = min(valeurs)
            arbre[indice] = (joueur, suivants, nouvelle_valeur) # un tuple n'est pas mutable
    aux(0)
    return arbre[0][2]

# Version bottom-up, plus compliquée en pratique mais plus rapide

def minmax(arbre):
    """Algorithme minmax pour la représentation d'une arborescence
    sous forme de liste de triplets (J, succ, val), où J est un booléen
    indiquant le propriétaire du sommet (True est le joueur voulant maximiser),
    succ est la liste des indices où se trouvent les successeurs du sommet
    et val est la valeur du sommet (fixée à 0 sauf si le sommet n'a pas
    de successeurs).
    """
    arbre_renverse = [[None, None] for _ in arbre]
    a_traiter = []
    for i in range(len(arbre)):
        if arbre[i][1] == []:
            arbre_renverse[i][1] = arbre[i][2]
            a_traiter.append(i)
        else:
            for j in arbre[i][1]:
                arbre_renverse[j][0] = i
    a_traiter_bientot = dict()
    for sommet in a_traiter:
        if sommet == 0:
            return arbre_renverse[sommet][1]
        predecesseur = arbre_renverse[sommet][0]
        if arbre_renverse[predecesseur][1] is None:
            arbre_renverse[predecesseur][1] = arbre_renverse[sommet][1]
            a_traiter_bientot[predecesseur] = len(arbre[predecesseur][1])-1
        else:
            if arbre[predecesseur][0]:
                condition = arbre_renverse[predecesseur][1] < arbre_renverse[sommet][1]
            else:
                condition = arbre_renverse[predecesseur][1] > arbre_renverse[sommet][1]
            if condition:
                arbre_renverse[predecesseur][1] = arbre_renverse[sommet][1]
            a_traiter_bientot[predecesseur] -= 1
            if a_traiter_bientot[predecesseur] == 0:
                a_traiter.append(predecesseur)
    raise ValueError("Ceci ne devrait pas se rencontrer")

# Exercice 4

def construit_racines(L):
    """Crée la liste des racines de l'arbre utilisé pour le jeu du partage
    du gâteau à partir d'une liste de tailles de parts.
    Les racines sont des listes [reste, val, 0] où val est un élément
    de la liste et reste est composé de tous les autres éléments dans l'ordre
    en repartant au début de la liste une fois la fin atteinte.
    En fait val est le gain de Bob s'il sélectionne la part en question
    au premier tour.
    """
    racines = []
    for i in range(len(L)):
        racines.append([L[i+1:] + L[:i], L[i], 0])
    return racines

def construit_arbre(L):
    """Construit l'arbre utilisé pour le jeu du partage du gâteau
    à partir d'une liste de tailles de parts.
    On part de la liste des racines obtenue par la fonction construit_racines
    et on retire au fur et à mesure de l'avancée en profondeur dans l'arbre
    le premier ou le dernier élément du reste.
    Les feuilles (toutes au même niveau) contiennent des listes
    [[], B, A] où B est le score de Bob et A le score d'Alice.
    """
    arbre = [construit_racines(L)]
    for niv in range(len(L)-1): # redondance au dernier niveau, pour faciliter
        niveau = []
        for noeud in arbre[niv]:
            Bob = noeud[1] + (noeud[0][0] * (niv % 2))
            Alice = noeud[2] + (noeud[0][0] * ((niv + 1) % 2))
            niveau.append([noeud[0][1:], Bob, Alice])
            Bob = noeud[1] + (noeud[0][-1] * (niv % 2))
            Alice = noeud[2] + (noeud[0][-1] * ((niv + 1) % 2))
            niveau.append([noeud[0][:-1], Bob, Alice])
        arbre.append(niveau)
    return arbre

def strategie(L, joueurs):
    """Complète l'arbre obtenu par la fonction construit_arbre
    de sorte que chaque nœud soit accompagné de l'information
    du joueur gagnant ainsi que de la stratégie à appliquer
    (0 : prendre le premier morceau, 1 : prendre le dernier, None : peu importe
    car c'est l'adversaire qui a une stratégie gagnante).
    """
    arbre = construit_arbre(L)
    for noeud in arbre[len(L)-1]:
        noeud.append(joueurs[noeud[2] > noeud[1]]) # vainqueur
    for niv in range(len(L)-2, -1, -1):
        for ind, noeud in enumerate(arbre[niv]):
            if arbre[niv+1][2*ind][3] == joueurs[(niv+1) % 2]:
                noeud.extend([joueurs[(niv+1) % 2], 0])
            elif arbre[niv+1][2*ind+1][3] == joueurs[(niv+1) % 2]:
                noeud.extend([joueurs[(niv+1) % 2], 1])
            else:
                noeud.extend([joueurs[niv % 2], None])
    return arbre

def compte_rendu(L):
    """Détermine si Alice a une stratégie gagnante pour le jeu
    du partage de gâteau étant donné le partage représenté par la liste L.
    """
    joueurs = ["Bob", "Alice"]
    arbre = strategie(L, joueurs)
    for i in range(len(L)):
        if arbre[0][i][3] != "Alice":
            return False
    return True

## Tests :

### decoupage = [1, 16, 1, 15, 1, 1, 14, 1, 13, 1, 1, 12, 1, 11, 1] # Spoiler d'un découpage gagnant pour Alice
### print(compte_rendu(decoupage))

# Exercice 5

# on suppose random importé ici encore

def un_resultat(choix1, choix2):
    """Détermine le gain (potentiellement négatif) en fonction du choix
    des deux joueurs dans le jeu inspiré du dilemme du prisonnier.
    """
    res1, res2 = 0, 0
    if choix1:
        res1 -= 1
        res2 += 3
    if choix2:
        res2 -= 1
        res1 += 3
    return res1, res2

def mute_avec_un_resultat(res, choix1, choix2):
    """Mute la liste des scores en incorporant le gain en fonction du choix
    des deux joueurs dans le jeu inspiré du dilemme du prisonnier.
    """
    (res1, res2) = un_resultat(choix1, choix2)
    res[0] += res1
    res[1] += res2

def resultat(l1, l2):
    """Retourne le couple des scores de deux joueurs en fonction des listes
    des choix des deux joueurs dans le jeu inspiré du dilemme du prisonnier.
    """
    res = [0, 0]
    for x, y in zip(l1, l2):
        mute_avec_un_resultat(res, x, y)
    return tuple(res)

# !!! Astuce possible : compter le nombre de True dans chacune des listes et faire un seul calcul global !!!

# Exercice 6

def gentille(l):
    """Stratégie gentille pour le jeu inspiré du dilemme du prisonnier.
    Le choix est toujours de donner en ignorant la liste l de l'adversaire.
    La liste des coups, de même taille que l, est retournée.
    """
    return [True for _ in l]

def mechante(l):
    """Stratégie méchante pour le jeu inspiré du dilemme du prisonnier.
    Le choix est toujours de garder en ignorant la liste l de l'adversaire.
    La liste des coups, de même taille que l, est retournée.
    """
    return [False for _ in l]

def copieuse(l):
    """Stratégie copieuse pour le jeu inspiré du dilemme du prisonnier.
    Le choix est de donner au premier tour puis d'imiter le coup précédent.
    La liste des coups, de même taille que l, est retournée.
    """
    if l == []:
        return []
    return [True] + l[:-1]

def mefiante(l):
    """Stratégie méfiante pour le jeu inspiré du dilemme du prisonnier.
    Le choix est de donner jusqu'à la première fois que l'adversaire garde,
    puis de garder jusqu'à la fin.
    La liste des coups, de même taille que l, est retournée.
    """
    if l == []:
        return []
    choix = True
    rep = [True]
    for i in range(len(l)-1):
        if not l[i]:
            choix = False
        rep.append(choix)
    return rep

def aleatoire(l):
    """Stratégie aléatoire pour le jeu inspiré du dilemme du prisonnier.
    Le choix aléatoire en ignorant la liste l de l'adversaire.
    La liste des coups, de même taille que l, est retournée.
    """
    return [random.choice([True, False]) for _ in l]

# Exercice 7

def gentille_un_coup(l):
    """Stratégie gentille pour le jeu inspiré du dilemme du prisonnier.
    Le choix est toujours de donner en ignorant la liste de l'adversaire.
    Seul le coup suivant est retourné.
    """
    return True

def mechante_un_coup(l):
    """Stratégie méchante pour le jeu inspiré du dilemme du prisonnier.
    Le choix est toujours de garder en ignorant la liste l de l'adversaire.
    Seul le coup suivant est retourné.
    """
    return False

def copieuse_un_coup(l):
    """Stratégie copieuse pour le jeu inspiré du dilemme du prisonnier.
    Le choix est de donner au premier tour puis d'imiter le coup précédent.
    Seul le coup suivant est retourné.
    """
    if l == []:
        return True
    return l[-1]

def mefiante_un_coup(l):
    """Stratégie méfiante pour le jeu inspiré du dilemme du prisonnier.
    Le choix est de donner jusqu'à la première fois que l'adversaire garde,
    puis de garder jusqu'à la fin.
    Seul le coup suivant est retourné.
    """
    return False not in l

def aleatoire_un_coup(l):
    """Stratégie aléatoire pour le jeu inspiré du dilemme du prisonnier.
    Le choix aléatoire en ignorant la liste l de l'adversaire.
    Seul le coup suivant est retourné.
    """
    return random.choice([True, False])

def interaction(adversaire, nb_coups):
    """Permet de jouer contre un adversaire, stratégie en tant que fonction
    de type profil_un_coup, sur un nombre défini de coups.
    Le couple des résultats est retourné.
    """
    l1, l2 = [], []
    for i in range(nb_coups):
        coup1 = eval(input("Voulez-vous offrir (1) ou garder (0) ?" ))
        coup2 = adversaire(l1)
        l1.append(coup1)
        l2.append(coup2)
        if coup2:
            print("L'adversaire offre.")
        else:
            print("L'adversaire garde.")
    return resultat(l1, l2)

# Exercice 8

def construit_jeu(f1, f2, nb_coups):
    """Construit une partie entre deux adversaires, stratégies en tant que
    fonctions de type profil_un_coup, sur un nombre défini de coups.
    Les deux listes de coups sont retournées.
    """
    l1, l2 = [], []
    for i in range(nb_coups):
        coup1 = f1(l2)
        coup2 = f2(l1) # calculer avant ajout
        l1.append(coup1)
        l2.append(coup2)
    return l1, l2

# Exercice 9

def fait_jouer(f1, f2, nb_coups):
    """Construit une partie entre deux adversaires, stratégies en tant que
    fonctions de type profil_un_coup, sur un nombre défini de coups.
    Le couple des résultats est retourné.
    """
    l1, l2 = construit_jeu(f1, f2, nb_coups)
    return resultat(l1, l2)

def tournoi(liste_f, nb_coups):
    """Fait jouer un tournoi entre de nombreux adversaires mis dans une liste,
    contenant des stratégies en tant que fonctions de type profil_un_coup.
    Le nombre de coups est défini.
    La liste des couples (fonction, score) dans l'ordre décroissant
    est retournée ainsi qu'auparavant la liste des scores dans l'ordre
    en vue de brancher sur la fonction suivante.
    """
    n = len(liste_f)
    scores = [0 for _ in range(n)]
    for i in range(n-1):
        for j in range(i+1, n):
            res1, res2 = fait_jouer(liste_f[i], liste_f[j], nb_coups)
            scores[i] += res1
            scores[j] += res2
    compte_rendu = zip([strat.__name__ for strat in liste_f], scores) # J'aime vraiment zip, et j'ai improvisé __name__, apparemment ça marche
    compte_rendu_trie = sorted(compte_rendu, key=lambda x:-x[1]) # le tri ne supporte pas de comparer deux fonctions, donc il faut restreindre la condition
    return scores, compte_rendu_trie

# Exercice 10

def tournoi_genetique(liste_f, nb_coups, nb_repetitions):
    """Fait jouer un tournoi entre de nombreux adversaires mis dans une liste,
    contenant des stratégies en tant que fonctions de type profil_un_coup.
    Le nombre de coups est défini.
    Le tournoi est répété nb_repetitions fois en gardant deux copies de chaque
    participant ayant fini dans la meilleure moitié.
    Le dictionnaire contenant le nombre d'occurrences de chaque stratégie
    parmi celles qui existent encore est retourné.
    """
    n = len(liste_f)
    liste = liste_f
    for _ in range(nb_repetitions):
        scores, _ = tournoi(liste, nb_coups)
        effectif = sorted(zip(scores, liste), key=lambda x:x[0])
        liste = [x[1] for x in effectif[n//2:] + effectif[n-n//2:]]
    dico = {}
    for strat in liste:
        if strat.__name__ not in dico:
            dico[strat.__name__] = 1
        else:
            dico[strat.__name__] += 1
    return dico # évidemment, tous les effectifs sont pairs

## Tests :

### population = [gentille_un_coup] * 10 + [mechante_un_coup] * 10 + [copieuse_un_coup] * 10 + [mefiante_un_coup] * 10 + [aleatoire_un_coup] * 10
### print(tournoi_genetique(population, 10, 100)) # Les méchants survivent rarement, et les gentils gagnent parfois (ou les méfiants, qui sont équivalents quand il n'y a plus de méchant)