## TP8


def Graphe_Nim(n):
    """
    def Graphe_Nim(n:int)-> Tuple[List[int],List[List[int]],List[str]]:
    
    prend un entier n en entrée et retourne un tuple contenant 3 listes :
    La première liste est une liste d'entiers qui représente les sommets du graphe.
    La seconde liste est une liste de listes d'entiers qui représente les arêtes du graphe ou les fils de chaque noeud de l'arbre.
    La troisième liste est une liste de chaînes de caractères qui représente les étiquettes des sommets ou des noeuds.
    
    La fonction permet de créer un graphe pour le jeu de Nim, où chaque état est défini par un couple (i,j) où i est le nombre de bâtons restants et j est le joueur qui doit jouer ("0" ou "1").
    """
    S=[0]
    A=[]
    E=[str(n)+";0"]
    i=0
    while i < len(S):
        s=E[i]
        batons,joueur=s.split(";")
        batons=int(batons)
        joueur_suivant = "1" if joueur=="0" else "0"
        for k in [1,2,3]:
            if batons-k >=1:
                etiq=str(batons-k)+";"+joueur_suivant
                if etiq in E:
                    j=E.index(etiq)
                    A.append([i,j])
                else :
                    S.append(len(S))
                    E.append(etiq)
                    A.append([i,len(S)-1])
        i=i+1
    return S,A,E
                
                
                
                
def Arbre_Nim(n):
    """
    def Arbre_Nim(n:int)-> Tuple[List[int],List[List[int]],List[str]]:
    
    prend un entier n en entrée et retourne un tuple contenant 3 listes :
    La première liste est une liste d'entiers qui représente les sommets de l'arbre.
    La seconde liste est une liste de listes d'entiers qui représente les arêtes du graphe ou les fils de chaque noeud de l'arbre.
    La troisième liste est une liste de chaînes de caractères qui représente les étiquettes des sommets ou des noeuds.
    
    La fonction permet de créer un arbre pour le jeu de Nim, où chaque état est défini par un couple (i,j) où i est le nombre de bâtons restants et j est le joueur qui doit jouer ("0" ou "1").
    """
    S=[0]
    A=[]
    E=[str(n)+";0"]
    i=0
    while i < len(S):
        s=E[i]
        batons,joueur=s.split(";")
        batons=int(batons)
        joueur_suivant = "1" if joueur=="0" else "0"
        for k in [1,2,3]:
            if batons-k >=1:
                etiq=str(batons-k)+";"+joueur_suivant
                S.append(len(S))
                E.append(etiq)
                A.append([i,len(S)-1])
        i=i+1
    return S,A,E