## Grundy

from random import randrange

def afficher_partie(partie:list,joueur) :
    if joueur :
        print("C'est au premier joueur de jouer")
    else :
        print("C'est au deuxième joueur de jouer")
    for i in range(len(partie)) :
        print("La ligne", i ," contient ce nombre de jetons : ", partie[i])
    print()
    return

def initialisation(n : int):
    return [n], True


def verif_valid(partie,nb_tas,taille_tas1) :
    return taille_tas1 < partie[nb_tas] and taille_tas1 >= 1 and (partie[nb_tas] - taille_tas1) != taille_tas1

def suivant(partie,joueur,nb_tas,taille_tas1) :
    return partie[:nb_tas] + partie[nb_tas+1:] + [taille_tas1,partie[nb_tas] - taille_tas1], not joueur

def fini(partie) :
    for taille_tas in partie :
        if taille_tas != 1 and taille_tas != 2 :
            return False
    return True

def coup_possible(partie) :
    coup_pos = []

    # On parcourt tous les coups
    for tas in range(len(partie)) :
        for taille_tas1 in range(1,partie[tas]) :
            if verif_valid(partie,tas,taille_tas1):
                coup_pos.append((tas,taille_tas1))
    return coup_pos

def intel_art(partie) :
    coup_pos = coup_possible(partie)
    return coup_pos[randrange(0,len(coup_pos))]


def faire_graphe(n) :
    """
    La fonction faire_graphe renvoie le graphe d'accessibilité du Grundy
    """
    dico = {}
    partie, joueur = initialisation(n)
    pile = [(partie,joueur)]
    while pile != [] :
        partie,joueur = pile.pop()
        dico[(tuple(partie),joueur)] = {}
        for tas,taille_tas in coup_possible(partie) :
            part_suiv,joueur_suiv = suivant(partie,joueur,tas,taille_tas)
            dico[(tuple(partie),joueur)][tuple(part_suiv),joueur_suiv] = 1
            pile.append((part_suiv,joueur_suiv))
    return dico



def faire_graphe(n) :
    dico = {}
    partie, joueur = initialisation(n)
    pile = [(partie,joueur)]
    while pile != [] :
        partie,joueur = pile.pop()
        dico[(tuple(partie),joueur)] = []
        for tas,taille_tas in coup_possible(partie) :
            part_suiv,joueur_suiv = suivant(partie,joueur,tas,taille_tas)
            dico[(tuple(partie),joueur)].append((tuple(part_suiv),joueur_suiv))
            pile.append((part_suiv,joueur_suiv))
    return dico

def est_gagnant(partie,joueur) :
    # Cas de base
    if fini(partie) :
        return not joueur

    # Cas récursif
    else :
        if joueur :
            for (tas,taille_tas) in coup_possible(partie) :
                part_suiv,joueur_suiv = suivant(partie,joueur,tas,taille_tas)
                if est_gagnant(part_suiv,joueur_suiv) :
                    return True
            return False




        else :
            for (tas,taille_tas) in coup_possible(partie) :
                part_suiv,joueur_suiv = suivant(partie,joueur,tas,taille_tas)
                if not est_gagnant(part_suiv,joueur_suiv) :
                    return False
            return True




def jouer_grundy(n : int, intel_art) :
    """
    """
    premier_joueur = int(input("Taper 1 si vous voulez être le premier joueur, 0 sinon "))
    partie, joueur = initialisation(n)
    while not fini(partie) :
        afficher_partie(partie,joueur)
        if joueur == bool(premier_joueur) :
            nb_tas = int(input("Choisis un tas à diviser "))
            taille_tas1 = int(input("Quelle est la taille du premier tas ? "))
            assert verif_valid(partie,nb_tas,taille_tas1)
            partie, joueur = suivant(partie,joueur,nb_tas,taille_tas1)
        else :
            nb_tas,taille_tas1 = intel_art(partie)
            assert verif_valid(partie,nb_tas,taille_tas1)
            partie, joueur = suivant(partie,joueur,nb_tas,taille_tas1)
    if joueur ==  bool(premier_joueur) :
        print("Tu as perdu")
    else :
        print("Tu as gagné")
"""
partie, joueur = initialisation(18)
print(est_gagnant(partie, joueur))
#jouer_grundy(6,intel_art)
"""