def transpose(G):
#A compléter

def attracteur(G, S, F):
#A compléter

def type_sommet(s):
    for i in range(3):
        if s[i] == (0,0,0):
            return "V0"
        elif s[i] == (1,1,1):
            return "V1"
    for j in range(3):
        C = (s[0][j], s[1][j], s[2][j])
        if C == (0,0,0):
            return "V0"
        elif C == (1,1,1):
            return "V1"
    D1 = (s[0][0], s[1][1], s[2][2])
    D2 = (s[2][0], s[1][1], s[0][2])
    if D1 == (0,0,0) or D2 == (0,0,0):
        return "V0" #victoire joueur 0"
    elif D1 == (1,1,1) or D2 == (1,1,1):
        return "V1" #victoire joueur 1"
    if None not in s[0] and None not in s[1] and None not in s[2]:
        return "N" #match nul
    return "NF" #partie non finie"

def generer_morpion():
    D = {((None, None, None),(None, None, None),(None, None, None)) : 0}
    T = [((None, None, None),(None, None, None),(None, None, None))]
    G = [[]]
    V0 = []
    V1 = []
    N = []
    S = [[0], []]
    def visiter(s, joueur):
        #s est le sommet courant, joueur le joueur actif

        M = T[s]
        e = type_sommet(M)
        if e == "V0":
            V0.append(s)
            return
        elif e == "V1":
            V1.append(s)
            return
        elif e == "N":
            N.append(s)
            return
        for i in range(3):
            for j in range(3):
                if M[i][j] == None:
                    M2 = M[:i] + (M[i][:j]+(joueur,)+ M[i][j+1:],) + M[i+1:]
                    if M2 not in D:
                        n = len(G)
                        T.append(M2)
                        G.append([])
                        D[M2] = n
                        G[s].append(n)
                        S[1-joueur].append(n)
                        visiter(n, 1-joueur)
                    else:
                        G[s].append(D[M2])
    visiter(0, 0)
    return D, T, G, V0, V1, N, S

D, T, G, V0, V1, N, S = generer_morpion()

S0 = [k in S[0] for k in range(len(G))]

F = [k in V0 for k in range(len(G))]

A, strat = attracteur(G, S0, F)

def f(n):
    if n==None: return " "
    elif n==0 : return "x"
    elif n==1 : return "o"

def afficher_grille(grille):
    n, m = 3, 3
    for i in range(n):
        l = []
        l += [f(x) for x in grille[i]]
        print("|".join(l))



def partie_morpion():
    if input("commencer ? o/n") == "o":
        joueur = 0
    else:
        joueur = 1
    M = ((None, None, None),(None, None, None),(None, None, None))

    SIA = [k in S[1-joueur] for k in range(len(G))]
    F = V0 if joueur == 1 else V1
    VIA = [k in F for k in range(len(G))]
    NPIA = [k in F or k in N for k in range(len(G))]

    AV, stratV = attracteur(G, SIA, VIA)

    ANP, stratNP = attracteur(G, SIA, NPIA)

    joueur_courant = 0

    while True:
        afficher_grille(M)
        if joueur_courant == joueur:
            while True:
                i = int(input("ligne :"))
                j = int(input("colonne :"))
                if M[i][j] == None:
                    break
                else:
                    print("coup invalide")
            M = M[:i] + (M[i][:j]+(joueur,)+ M[i][j+1:],) + M[i+1:]
        else:
            n = D[M]
            print(n)
            if AV[n]:
                M = T[stratV[n]]
                print("je vais gagner !")
            elif ANP[n]:
                M = T[stratNP[n]]
                print("je ne vais pas perdre...")
            else:
                M = T[G[n][0]]
                print("tout est fichu...")
        type = type_sommet(M)
        if type == "V0":
            afficher_grille(M)
            print("Victoire du joueur 0")
            return
        if type == "V1":
            afficher_grille(M)
            print("Victoire du joueur 1")
            return
        if type == "N":
            afficher_grille(M)
            print("Match nul")
            return
        joueur_courant = 1 - joueur_courant



#Bonus : morpion qui perd gagne
def partie_morpion_qui_perd_gagne():
    if input("commencer ? o/n") == "o":
        joueur = 0
    else:
        joueur = 1
    M = ((None, None, None),(None, None, None),(None, None, None))

    SIA = [k in S[1-joueur] for k in range(len(G))]
    V = V0 if joueur == 0 else V1
    VIA = [k in V for k in range(len(G))]
    NPIA = [k in V or k in N for k in range(len(G))]

    AV, stratV = attracteur(G, SIA, VIA)

    ANP, stratNP = attracteur(G, SIA, NPIA)

    joueur_courant = 0

    while True:
        afficher_grille(M)
        if joueur_courant == joueur:
            while True:
                i = int(input("ligne :"))
                j = int(input("colonne :"))
                if M[i][j] == None:
                    break
                else:
                    print("coup invalide")
            M = M[:i] + (M[i][:j]+(joueur,)+ M[i][j+1:],) + M[i+1:]
        else:
            n = D[M]
            print(n)
            if AV[n]:
                M = T[stratV[n]]
                print("je vais gagner !")
            elif ANP[n]:
                M = T[stratNP[n]]
                print("je ne vais pas perdre...")
            else:
                M = T[G[n][0]]
                print("tout est fichu...")
        type = type_sommet(M)
        if type == "V0":
            afficher_grille(M)
            print("Victoire du joueur 1")
            return
        if type == "V1":
            afficher_grille(M)
            print("Victoire du joueur 0")
            return
        if type == "N":
            afficher_grille(Mx, w)
            print("Match nul")
            return
        joueur_courant = 1 - joueur_courant