''' Intelligence artificielle & theorie de jeux'''
''' Jeu des tablettes '''

#________________________________________________
##  Partie 1 - Lister les coups possibles
#________________________________________________
# Q1 - Etat de x
''' Situation 1: x=[[0,1],[0,1],[1,1],[1,1]]
    Situation 2: x=[[0,2],[1,1],[1,1]]
'''
# Q2 - empile
def empile(x,i,j):
    """ empile ( x : list, i : int, j : int )-> list
        entrees : x, liste de listes(ci,hi), represente la situation initiale. Chaque sous liste correspod à une pile représntée par (ci=couleur du haut,hi=hauteur)
                : i, j, entiers, indices des piles que l'on veut empiler 
        sortie; LXij , liste de situations possibles après empilement
    """
    LXij = []
    ci , hi = x[i]
    cj , hj = x[j]
    if ci==cj or hi==hj : #empilement possible 
        reste = x[:i] + x[i+1:j] + x[j+1:]
        pij = [ci,hi+hj] # pile ci sur cj (arbitrairement)
        X = reste + [pij]
        X.sort()
        LXij.append(X)
        if ci!=cj: # si couleur différente => ajouter la situation avec cj au dessus
            pji = [cj,hi+hj] # pile cj sur ci
            X = reste + [pji]
            X.sort()
            LXij.append(X)
    return LXij

# tests de la fonction empile
x = [ [0,1] , [0,1] , [1,1] , [1,1] ] # situation 1
res1 = empile( x, 0, 1 )
print( res1 )   # affiche [[[0, 2], [1, 1], [1, 1]]]

x = [ [0,1],[0,1],[1,1],[1,1]]  # situation 1
res2 = empile(x,0,3)
print(res2)     # affiche [[[0, 1], [0, 2], [1, 1]], [[0, 1], [1, 1], [1, 2]]]

x = [ [0,2],[0,2],[1,1],[1,1]]  
res3 = empile(x,0,1)
print(res3)     # affiche [[[0, 4], [1, 1], [1, 1]]]

x = [[0,2],[1,1],[1,1]]
res4 = empile(x,0,1)
print(res4)     # affiche []

# Q3 - coups
def coups(x):
    """ coups(x : list) -> list
        entree: x, liste de liste(ci,hi), situation initiale
        sortie : ensemble des situations possibles en realisant toutes les combinaisons d'empilement possibles 
                (chaque situation est unique => doublons elimines)
    """
    LX = []
    for i in range( len(x) ):
        for j in range( i+1 , len(x) ):
            LXij = empile( x,i,j )
            for X in LXij:
                if X not in LX: # On n'ajoute la situation que si elle n'a pas dejà ete stockée
                    LX.append(X)
    return LX

x = [ [0,2],[0,3],[1,1],[1,2] ]

lesCoups1 = coups(x)
print( lesCoups1 )
# affiche [[[0, 5], [1, 1], [1, 2]], [[0, 3], [0, 4], [1, 1]], [[0, 3], [1, 1], [1, 4]], [[0, 2], [0, 3], [1, 3]]]

x = [[0,1],[0,1],[1,1],[1,1]]
lesCoups2 = coups(x)
print( lesCoups2 )
# affiche [[[0, 2], [1, 1], [1, 1]], [[0, 1], [0, 2], [1, 1]], [[0, 1], [1, 1], [1, 2]], [[0, 1], [0, 1], [1, 2]]]


'''
sans sort dans empile, les élèves ne trouveront pas le même résultat 
'''
#________________________________________________
##      Partie 2 : Création du graphe du jeu
#________________________________________________
# Q4 - init
def init(C,N):
    """ init( C : int, N: int ) -> list
        entrees : C, entier positif, nombre de couleurs differentes
                : N , entier positif, nombre de tablettes par couleur
        sortie : x0, liste de listes (ci,hi) correspondant à la situation initiale (hi est systematiqueme =1)
    """
    x0 = []
    for c in range(C):
        for _ in range(N):
            x0.append([c,1])
    x0.sort() # Inutile compte tenu de la programmation avec c croissant
    return x0

test = init(3,4)
print(test)  
# affiche [[0, 1], [0, 1], [0, 1], [0, 1], [1, 1], [1, 1], [1, 1], [1, 1], [2, 1], [2, 1], [2, 1], [2, 1]]

# Q5 - Tuple
def Tuple(L):
    """
        Tuple(L:list)-> tuple
        fonction recursive
        entree : L,liste de liste de liste, ... que l'on veut transformer en tuple de tuple de tuple, ...
        sortie : tuple
    """
    if L==[]:
        return ()
    elif type(L[0])!=list:
        return tuple(L)
    else:
        Res = []
        for l in L:
            Res.append(Tuple(l))
        return tuple(Res)

L = [ [ [1,2],[3,4,5] , [[6]]] ]
#lesTuples = Tuple(L)
#print(lesTuples) # affiche (((1, 2), (3, 4, 5), ((6,),)),)

"""
L1 = [[1]]
lesTuples2 = Tuple(L1)
print(lesTuples2) # affiche  ((1,),)
"""

# Q6 - graphe
from collections import deque
def graphe(C,N):
    """ graphe(C : int ,N:int )-> dict
        entrees : C, entier positif, nombre de couleurs differentes
                : N , entier positif, nombre de tablettes par couleur
        sortie : G, dictionnaire, representant le graphe :clé : tuple de la situation, valeur : liste de liste de situation atteignables   
    """
    # constitution de la situation initiale
    x0 = init(C,N) 
    G = {} # initialisation du dictionnaire G qui représente le graphe    
    file = deque()
    file.append(x0) # initialisation de la file avec la situation initiale x0
    while len(file) != 0:
        x = file.popleft()  # recuperation du 1er element de la file
        Cle = Tuple(x)      # génération de la cle sous forme de tuple 
        LCoupsSuivants = coups(x)       # recuperation de la liste des situations atteignables depuis x
        #Valeur = LCoupsSuivants
        G[Cle] = LCoupsSuivants # ajout dans le graphe du couple clé, valeur
        # ajout dans la file des differentes situations (si elles n'ont pas dejà été stockées) pour traitement ultérieur
        for c in LCoupsSuivants:
            if Tuple(c) not in G:
                file.append(c)
    return G

print("Constitution du graphe")
C,N = 2,2
Graphe = graphe(C,N)
print(Graphe)
# affiche (avec mise en forme)
"""
{((0, 1), (0, 1), (1, 1), (1, 1)): [[[0, 2], [1, 1], [1, 1]], 
                                    [[0, 1], [0, 2], [1, 1]],
                                    [[0, 1], [1, 1], [1, 2]],
                                    [[0, 1], [0, 1], [1, 2]]],
 ((0, 2), (1, 1), (1, 1))        : [[[0, 2], [1, 2]]],
 ((0, 1), (0, 2), (1, 1))        : [[[0, 3], [1, 1]],
                                    [[0, 2], [0, 2]],
                                    [[0, 2], [1, 2]]],
 ((0, 1), (1, 1), (1, 2))        : [[[0, 2], [1, 2]], 
                                    [[1, 2], [1, 2]], 
                                    [[0, 1], [1, 3]]], 
 ((0, 1), (0, 1), (1, 2))        : [[[0, 2], 
                                    [1, 2]]], 
 ((0, 2), (1, 2))                : [[[0, 4]], 
                                   [[1, 4]]], 
 ((0, 3), (1, 1))                : [], 
 ((0, 2), (0, 2))                : [[[0, 4]]], 
 ((1, 2), (1, 2))                : [[[1, 4]]], 
 ((0, 1), (1, 3))                :  [],
 ((0, 4),): [], 
 ((1, 4),): []
 }
"""

# Définition des positions pour la suite
Pos_0 = [[0,1],[0,1],[1,1],[1,1]]
Pos_1a = [[0,2],[1,1],[1,1]]
Pos_1b = [[0,1],[0,2],[1,1]]
Pos_1c = [[0,1],[1,1],[1,2]]
Pos_1d = [[0,1],[0,1],[1,2]]
Pos_2a = [[0,2],[1,2]]
Pos_2b = [[0,3],[1,1]]
Pos_2c = [[0,2],[0,2]]
Pos_2d = [[1,2],[1,2]]
Pos_2e = [[0,1],[1,3]]
Pos_3a = [[0,4]]
Pos_3b = [[1,4]]

# Q7 - N1 et N2

N1 = len(Graphe)
N2 = sum([len(Graphe[x]) for x in Graphe])

'''
print("Sommets:",N1)
print("Arêtes:",N2)
'''

''' Résultat
Sommets: 12
Arêtes: 16
'''

# Q8 - Remplissage du tableau
from time import perf_counter 
C,N = 2,2 # A modifier pour chaque cas
tic = perf_counter()
Graphe = graphe(C,N)
toc = perf_counter()
T = toc - tic

print("Pour C = "+str(C)+" et N = "+str(N))
Nb_Sommets = len(Graphe) # N1
print("Sommets:",Nb_Sommets)
Nb_Aretes = sum([len(Graphe[x]) for x in Graphe]) # N2
print("Arêtes:",Nb_Aretes)
print("Temps (s):",T)

''' Résultat
Pour C = 2 et N = 2
Sommets: 12
Arêtes: 16
Temps (s): 8.039999966058531e-05

'''

## Graphe biparti
# Q9 - sommets_12
def sommets_12( G, C, N ):
    """ sommets_12( G, C, N )
        entrees : G, dictionnaire, represente le graphe
                : C, N, entiers representant le nombre de couleurs et le nombre de tablettes
        sorties: 2 tuples pour les sommets de J1 et de J2
    """
    S1 = []
    S2 = []
    n = N*C # nombre total de tablettes = nb de piles initial
    for e in G:
        if len(e)%2 == n%2: 
            S1.append(e)
        else:
            S2.append(e)
    return tuple(S1),tuple(S2) # S1 et S2 déjà Tuples, donc Tuples inutile

# Q10 - Création des sommets S1 et S2

C,N = 2,2
Graphe = graphe(C,N)
S1,S2 = sommets_12(Graphe,C,N)

'''
print("Sommets S1:",S1)
print("Sommets S2:",S2)
'''

''' Résultat
Sommets S1: (((0, 1), (0, 1), (1, 1), (1, 1)), ((0, 2), (1, 2)), ((0, 3), (1, 1)), ((0, 2), (0, 2)), ((1, 2), (1, 2)), ((0, 1), (1, 3)))
Sommets S2: (((0, 2), (1, 1), (1, 1)), ((0, 1), (0, 2), (1, 1)), ((0, 1), (1, 1), (1, 2)), ((0, 1), (0, 1), (1, 2)), ((0, 4),), ((1, 4),))
Soit:
S1: 0 2a 2b 2c 2d 2e
S2:  1a 1b 1c 1d 3a 3b
'''

## Les parties

# Q11 - Une partie
C,N = 2,2
Graphe = graphe(C,N) #generation du graphe du jeu
x0 = init(C,N) #situation initiale
Joueur = 1
print( "Joueur:" , Joueur )
print( "Jeu:", x0 )
lesSuccesseurs = Graphe[Tuple(x0)] #successeurs de la situation initiale
while len( lesSuccesseurs )>0:
        succ = lesSuccesseurs[0] #1er successeur
        Joueur = 3 - Joueur
        print( "Joueur:", Joueur )
        print( "Jeu:",succ )
        lesSuccesseurs = Graphe[Tuple(succ)] #successeurs du 1er successeur

''' Résultat
Joueur: 1
Jeu: [[0, 1], [0, 1], [1, 1], [1, 1]]
Joueur: 2
Jeu: [[0, 2], [1, 1], [1, 1]]
Joueur: 1
Jeu: [[0, 2], [1, 2]]
Joueur: 2
Jeu: [[0, 4]]
Le joueur 2 a gagné
Cela correspond à 0 - 1a - 2a - 3a
'''

## Détermination des positions gagnantes

# Q12 - Positions gagnantes sur le schéma

'''
Positions
2b 2e 3a 3b pas gagnantes car pas de successeurs
2a 2c 2d gagnantes car au moins un successeur n'est pas gagnant
1a et 1d pas gagnant car tous les successeurs sont gagnants (2a)
1b gagnant car au moins un successeur pas gagnant (2b)
1c gagnant car au moins un successeur pas gagnant (2e)
0 gagnant car au moins un successeur pas gagnant (1a et 1d)

Finalement, les positions gagnantes sont:
0 1b 1c 2a 2c 2d
'''

# Q13 - est_gagnante
'''
Version 1: On vérifie que tous les successeurs sont gagnants
Pour gagner du temps, on s'arrête dès qu'un successeur pas gagnant a été trouvé
'''
def est_gagnante(G,x): # x liste ou Tuple
    """ est_gagnante(G : dict, x : list)-> bool
        entrees : G, dictionnaire, représente le graphe (tuple(position), liste des successeurs)
                : x ; liste, position pour laquelle on souhaite savoir si elle gagnante ou pas
        sortie: booleen qui indique si la position est gagnante ou pas
    """
    lesSuccesseurs = G[Tuple(x)]
    if len(lesSuccesseurs) == 0:
        return False # Non gagnant
    else: # Tous les successeurs sont gagnants
        Tous_Gagnants = True
        for succ in lesSuccesseurs: # succ est une liste
            Tous_Gagnants = Tous_Gagnants and est_gagnante(G,succ)
            if Tous_Gagnants == False: # gagne du temps
                break  # Position gagnante
        return not(Tous_Gagnants) # Position pas gagnante

'''
Version 2: On cherche un successeur pas gagnant
Cela revient au même, mais c'est rédigé un peu autrement
'''
def est_gagnante(G,x): # x liste ou Tuple
    lesSuccesseurs = G[Tuple(x)]
    if len(lesSuccesseurs) == 0:
        return False # Aucun successeur => Pas gagnant
    else: # Aucun successeur pas gagnant?
        Res = False
        for succ in lesSuccesseurs: # succ est une liste
            if not est_gagnante(G,succ): # Un pas gagnant trouvé
                Res = True # Position gagnante
                break # Gagne du temps
        return Res

'''
L_Pos = [Pos_0,Pos_1a,Pos_1b,Pos_1c,Pos_1d,Pos_2a,Pos_2b,Pos_2c,Pos_2d,Pos_2e,Pos_3a,Pos_3b]
L_Pos_Nom = ["0","1a","1b","1c","1d","2a","2b","2c","2d","2e","3a","3b"]
for i in range(len(L_Pos)):
    Pos = L_Pos[i]
    Nom = L_Pos_Nom[i]
    print(Nom + ":",est_gagnante(Graphe,Pos))
'''

''' Résultat
0: True
1a: False
1b: True
1c: True
1d: False
2a: True
2b: False
2c: True
2d: True
2e: False
3a: False
3b: False
'''

# Q14 - dico_gagnant

def dico_gagnant(G):
    """ dico_gagnant(G)
        entrees : G, dictionnaire, représente le graphe (tuple(position), liste des successeurs)
        sortie: dico , dictionnaire qui contient pour chaque position(cle) si elle est gagnante ou pas (position, booleen)
    """
    dico = {}
    for x in G:
        dico[x] = est_gagnante(G,x)
    return dico

C,N = 2,2
Graphe = graphe(C,N)
x0 = init(C,N)
dico_g = dico_gagnant(Graphe)

print(dico_g)
#affiche {((0, 1), (0, 1), (1, 1), (1, 1)): True, ((0, 2), (1, 1), (1, 1)): False, ((0, 1), (0, 2), (1, 1)): True, ((0, 1), (1, 1), (1, 2)): True, ((0, 1), (0, 1), (1, 2)): False, ((0, 2), (1, 2)): True, ((0, 3), (1, 1)): False, ((0, 2), (0, 2)): True, ((1, 2), (1, 2)): True, ((0, 1), (1, 3)): False, ((0, 4),): False, ((1, 4),): False}
Statut_x0 = dico_g[Tuple(x0)]
print("Le joueur 1 dispose d'une position gagnante ?",Statut_x0)

''' Résultat
Le joueur 1 dispose d'une position gagnante ? True
'''

# Q15 - dico_gagnant_opt

def dico_gagnant_opt(G):
    def est_G(G,x): # Programmé pour que x soit un Tuple (*)
        if x in dico: # Nouveau
            # print('mémo')
            return dico[x] # Nouveau
        else: # Nouveau
            if len(x) == 0:
                dico[x] = False # Nouveau
                return False
            else:
                lesSuccesseurs = G[x]
                Res = False
                for succ in lesSuccesseurs:
                    if not est_G(G,Tuple(succ)): # (*) x est un Tuple
                        Res = True
                        break
                dico[x] = Res # Nouveau
                return Res
    dico = {}
    for x in G:
        dico[x] = est_G(G,x) # x est un Tuple
    return dico

''' Erreurs à ne pas commettre
Oublier de remplacer est_gagnante par est_G
Chercher x in dico avec x une liste au lieu d'être un Tuple
Oublier de mettre un dico[x]= au return False intermédiaire
'''
def est_Gagnante_rec(G,x, dico): # Programmé pour que x soit un Tuple (*)
        if x in dico: # Nouveau
            # print('mémo')
            return dico[x] # Nouveau
        else: # Nouveau
            if len(x) == 0:
                dico[x] = False # Nouveau
                return False
            else:
                lesSuccesseurs = G[x]
                Res = False
                for succ in lesSuccesseurs:
                    if not est_Gagnante_rec(G,Tuple(succ), dico): # (*) x est un Tuple
                        Res = True
                        break
                dico[x] = Res # Nouveau
                return Res


def dico_gagnant_opt( G ):
    
    dico = {}
    for x in G:
        dico[x] = est_Gagnante_rec(G,x,dico) # x est un Tuple
    return dico




dico_g_opt = dico_gagnant_opt(Graphe)

'''
test = dico_g==dico_g_opt
print('Dictionnaires identiques ?',test)
'''

''' Résultat
Dictionnaires identiques ? True
'''

# Q16 - Temps d'exécution

C,N = 3,3
Graphe = graphe(C,N)

tic = perf_counter()
dico_gagnant(Graphe)
toc = perf_counter()
T1 = toc - tic
tic = perf_counter()
dico_gagnant_opt(Graphe)
toc = perf_counter()
T2 = toc - tic
Rapport = T1/T2
print("Pour C = "+str(C)+" et N = "+str(N))
print("Temps non optimisé (s):",T1)
print("Temps optimisé (s):",T2)
print("Temps divisé par:",round(Rapport,2),":)")

'''
Pour C = 3 et N = 3
Temps non optimisé (s): 0.049233700000002045
Temps optimisé (s): 0.0050749000000109845
Temps divisé par: 9.7 :)

Pour C = 3 et N = 4
Temps non optimisé (s): 1.978249899999355
Temps optimisé (s): 0.03185489999850688
Temps divisé par: 62.1 :)
'''

# Pour la suite

dico_gagnant = dico_gagnant_opt

## Etude des positons gagnantes au départ

# Q17 - Remplissage du tableau
print("Joueur disposant d'une position gagnante au départ: ")
Cmax = 3
Nmax = 3

Titre = "  N="
for N in range(1,Nmax+1):
    Titre += str(N) + " "
print(Titre)

for C in range(1,Cmax+1):
    Ligne = 'C=' + str(C) + " "
    for N in range(1,Nmax+1):
        G = graphe(C,N)
        x0 = init(C,N)
        dico_g = dico_gagnant(G)
        Statut_x0 = dico_g[Tuple(x0)]
        if Statut_x0:
            Ligne += '1 '
        else:
            Ligne += '2 '
    print(Ligne)

''' Résultats
  N=1 2 3 4
C=1 2 1 2 1
C=2 1 1 2 2
C=3 1 2 1 1

  N=1 2
C=1 2 1
C=2 1 1
C=3 1 2
C=4 1 1

Soit par reconstruction
  N=1 2 3 4
C=1 2 1 2 1
C=2 1 1 2 2
C=3 1 2 1 1
C=4 1 1
'''

## Calcul des attracteurs
# Q18 - init_attracteurs
def init_attracteurs(G,S1):
    """ init_attracteurs(G : dict, S1 list)
        entrees : G : dictionnaire representant le graphe
                : S1, liste des sommets gagnants du joueur1
        sortie : d1, d2, dictionnaires - cle : sommet (tuple), valeur : booleen inidiquant si le sommet est dans les sommets gagnants du joueur j1 
    """
    # initialisation des dictionnaires d1 et D2 - cle : sommet du graphe(tuple) - valeur: False par defaut
    d1 = {cle:False for cle in G}
    d2 = {cle:False for cle in G}
    for x in G: # x Tuple
        lesSuccesseurs = G[Tuple(x)]
        if len(lesSuccesseurs) == 0: # sans successeurs
            if x in S1: # de S1 contenant des Tuples
                d2[x] = True
            else:
                d1[x] = True
    return d1,d2

C,N = 2,2
Graphe = graphe(C,N)
S1,S2 = sommets_12(Graphe,C,N)
dA1,dA2 = init_attracteurs(Graphe,S1)


print("dA1=",dA1)
print("dA2=",dA2)
''' Résultat
{((0, 1), (0, 1), (1, 1), (1, 1)): False, ((0, 2), (1, 1), (1, 1)): False, ((0, 1), (0, 2), (1, 1)): False, ((0, 1), (1, 1), (1, 2)): False, ((0, 1), (0, 1), (1, 2)): False, ((0, 2), (1, 2)): False, ((0, 3), (1, 1)): False, ((0, 2), (0, 2)): False, ((1, 2), (1, 2)): False, ((0, 1), (1, 3)): False, ((0, 4),): True, ((1, 4),): True}
{((0, 1), (0, 1), (1, 1), (1, 1)): False, ((0, 2), (1, 1), (1, 1)): False, ((0, 1), (0, 2), (1, 1)): False, ((0, 1), (1, 1), (1, 2)): False, ((0, 1), (0, 1), (1, 2)): False, ((0, 2), (1, 2)): False, ((0, 3), (1, 1)): True, ((0, 2), (0, 2)): False, ((1, 2), (1, 2)): False, ((0, 1), (1, 3)): True, ((0, 4),): False, ((1, 4),): False}
'''

# Q19 - cond_1
def cond_1(G,di,x):
    ''' cond_1(G : dict ,di : dict ,x : list)
        entrees : G, dictionnaire, qui représente le graphe
                : di, dictionnaires des attracteurs
                : x, liste représentant le sommet
        sortie : booléen, à True si au moins un successeur de x est à True dans di'''
    lesSuccesseurs = G[Tuple(x)]
    for succ in lesSuccesseurs:
        if di[Tuple(succ)] == True:
            return True
    return False

'''
test = cond_1(Graphe,dA1,Pos_2a)
print(test)
test = cond_1(Graphe,dA1,Pos_2b)
print(test)
test = cond_1(Graphe,dA1,Pos_2c)
print(test)
test = cond_1(Graphe,dA1,Pos_2d)
print(test)
test = cond_1(Graphe,dA1,Pos_2e)
print(test)

test = cond_1(Graphe,dA2,Pos_1a)
print(test)
test = cond_1(Graphe,dA2,Pos_1b)
print(test)
test = cond_1(Graphe,dA2,Pos_1c)
print(test)
test = cond_1(Graphe,dA2,Pos_1d,)
print(test)

test = cond_1(Graphe,dA2,Pos_2a)
print(test)
test = cond_1(Graphe,dA2,Pos_2b)
print(test)
test = cond_1(Graphe,dA2,Pos_2c)
print(test)
test = cond_1(Graphe,dA2,Pos_2d)
print(test)
test = cond_1(Graphe,dA2,Pos_2e)
print(test)

test = cond_1(Graphe,dA1,Pos_1a)
print(test)
test = cond_1(Graphe,dA1,Pos_1b)
print(test)
test = cond_1(Graphe,dA1,Pos_1c)
print(test)
test = cond_1(Graphe,dA1,Pos_1d)
print(test)
'''

''' Résultat
True  : de 2a, 1 peut mener à A1 (3a et 3b)
False : de 2b, 1 ne mène pas à A1
True  : de 2c, 1 peut mener à A1 (3a)
True  : de 2d, 1 peut mener à A1 (3b)
False : de 2e, 1 ne mène pas à A1

False : de 1a, 2 ne mène pas à A2
True  : de 1b, 2 peut mener à A2 (2b)
True  : de 1c, 2 peut mener à A2 (2e)
False : de 1d, 2 ne mène pas à A2

False : aucun successeur dans les sommets verts initialisés
False : aucun successeur dans les sommets verts initialisés
False : aucun successeur dans les sommets verts initialisés
False : aucun successeur dans les sommets verts initialisés
False : aucun successeur dans les sommets verts initialisés

False : aucun successeur dans les sommets violets initialisés
False : aucun successeur dans les sommets violets initialisés
False : aucun successeur dans les sommets violets initialisés
False : aucun successeur dans les sommets violets initialisés
'''

# Q20 - cond_2
def cond_2(G,di,x):
    ''' cond_2(G : dict ,di : dict ,x : list)
            entrees : G, dictionnaire, qui représente le graphe
                    : di, dictionnaires des attracteurs
                    : x, liste représentant le sommet
            sortie : booléen, à True si tous les successeurs de x sont True dans di
    '''
    lesSuccesseurs = G[Tuple(x)]
    if len(lesSuccesseurs) == 0:
        return False
    else:
        Res = True
        for succ in lesSuccesseurs:
            Res = Res and di[Tuple(succ)]
        return Res

'''
test = cond_2(Graphe,dA1,Pos_2a)
print(test)
test = cond_2(Graphe,dA1,Pos_2b)
print(test)
test = cond_2(Graphe,dA1,Pos_2c)
print(test)
test = cond_2(Graphe,dA1,Pos_2d)
print(test)
test = cond_2(Graphe,dA1,Pos_2e)
print(test)

test = cond_2(Graphe,dA2,Pos_1a)
print(test)
test = cond_2(Graphe,dA2,Pos_1b)
print(test)
test = cond_2(Graphe,dA2,Pos_1c)
print(test)
test = cond_2(Graphe,dA2,Pos_1d)
print(test)

test = cond_2(Graphe,dA2,Pos_2a)
print(test)
test = cond_2(Graphe,dA2,Pos_2b)
print(test)
test = cond_2(Graphe,dA2,Pos_2c)
print(test)
test = cond_2(Graphe,dA2,Pos_2d)
print(test)
test = cond_2(Graphe,dA2,Pos_2e)
print(test)

test = cond_2(Graphe,dA1,Pos_1a)
print(test)
test = cond_2(Graphe,dA1,Pos_1b)
print(test)
test = cond_2(Graphe,dA1,Pos_1c)
print(test)
test = cond_2(Graphe,dA1,Pos_1d)
print(test)
'''

''' Résultat
True  : de 2a, 1 mène forcément à A1 (3a et 3b)
False : de 2b, 1 ne mène pas à A1 (mène nulle part)
True  : de 2c, 1 mène forcément à A1 (3a)
True  : de 2d, 1 mène forcément à A1 (3b)
False : de 2e, 1 ne mène pas à A1 (mène nulle part)

False : de 1a, 2 ne mène pas que à A2
False : de 1b, 2 ne mène pas que à A2
False : de 1c, 2 ne mène pas que à A2
False : de 1d, 2 ne mène pas que à A2

False : aucun successeur dans les sommets verts initialisés
False : aucun successeur dans les sommets verts initialisés
False : aucun successeur dans les sommets verts initialisés
False : aucun successeur dans les sommets verts initialisés
False : aucun successeur dans les sommets verts initialisés

False : aucun successeur dans les sommets violets initialisés
False : aucun successeur dans les sommets violets initialisés
False : aucun successeur dans les sommets violets initialisés
False : aucun successeur dans les sommets violets initialisés
'''

# Q21 - attracteurs_it
def attracteurs_it(G,di,Si):
    """ attracteurs_it(G,di,Si)-> bool
            entrees : G, dictionnaire, qui représente le graphe
                    : di, dictionnaires des attracteurs du joueur i modifie en place
                    : Si, liste représentant les sommets du joueur i
            sortie : booléen, à True si une modification a été apportée a di
    """
    Changement = False
    for x in G:
        if di[x] == False:
            if x in Si:
                Cond = cond_1(G,di,x)
            else:
                Cond = cond_2(G,di,x)
            di[x] = Cond
            Changement = Changement or Cond
    return Changement

# Q22 - attracteurs_Ji

def attracteurs_Ji(G,di,Si):
    """ attracteurs_it(G,di,Si)
            entrees : G, dictionnaire, qui représente le graphe
                    : di, dictionnaires des attracteurs du joueur i rempli intégralement par la focntion
                    : Si, liste représentant les sommets du joueur i
    """
    Changement = True
    while Changement:
        Changement = attracteurs_it(G,di,Si)

# Q23 - attracteurs

def attracteurs(G,C,N):
    """ attracteurs(G,C,N)-> dict, dict
            entrees : G, dictionnaire, qui représente le graphe
                    : C,N, entiers respectivement nombre de couleurs et de jetons par couleur
            sorties : dA1, dA2, dictionnaires qui correspondent aux attracteurs de J1 et J2
    """
    S1,S2 = sommets_12(G,C,N)
    dA1,dA2 = init_attracteurs(G,S1)
    attracteurs_Ji(G,dA1,S1)
    attracteurs_Ji(G,dA2,S2)
    return dA1,dA2

C,N = 2,2
Graphe = graphe(C,N)
dA1,dA2 = attracteurs(Graphe,C,N)

'''
print(dA1)
print(dA2)
'''

''' Résultat
{((0, 1), (0, 1), (1, 1), (1, 1)): True, ((0, 2), (1, 1), (1, 1)): True, ((0, 1), (0, 2), (1, 1)): False, ((0, 1), (1, 1), (1, 2)): False, ((0, 1), (0, 1), (1, 2)): True, ((0, 2), (1, 2)): True, ((0, 3), (1, 1)): False, ((0, 2), (0, 2)): True, ((1, 2), (1, 2)): True, ((0, 1), (1, 3)): False, ((0, 4),): True, ((1, 4),): True}
Sont à True: 0 1a 1d 2a 2c 2d 3a 3b

{((0, 1), (0, 1), (1, 1), (1, 1)): False, ((0, 2), (1, 1), (1, 1)): False, ((0, 1), (0, 2), (1, 1)): True, ((0, 1), (1, 1), (1, 2)): True, ((0, 1), (0, 1), (1, 2)): False, ((0, 2), (1, 2)): False, ((0, 3), (1, 1)): True, ((0, 2), (0, 2)): False, ((1, 2), (1, 2)): False, ((0, 1), (1, 3)): True, ((0, 4),): False, ((1, 4),): False}
Sont à True: 1b 1c 2b 2e
'''

# Q24 - dico_gagnant_att

def dico_gagnant_att(G,C,N):
    """ dico_gagnant_att(G,C,N)->dict
            entrees : G, dictionnaire, qui représente le graphe
                    : C,N, entiers respectivement nombre de couleurs et de jetons par couleur
            sorties : dico, dictionnaires qui indique pour chaque position si elle est gagnante ou pas
    """
    S1,S2 = sommets_12(G,C,N)
    d1,d2 = init_attracteurs(G,S1)
    attracteurs(G,C,N)
    dico = {}
    for x in G:
        if x in S1 and d1[x]:
            dico[x] = True
        elif x in S2 and d2[x]:
            dico[x] = True
        else:
            dico[x] = False
    return dico

C,N = 2,2
Graphe = graphe(C,N)
dico_g_att = dico_gagnant_att(Graphe,C,N)
dico_g = dico_gagnant(Graphe)
test = dico_g==dico_g_att

'''
print('Dictionnaires identiques ?',test)
'''

''' Résultat
Dictionnaires identiques ? True
'''

## Stratégie optimale

# Q25 - strategie_opt

from random import randint as rd

def strategie_opt(G,dg,x):
    """ strategie_opt(G,dg,x)-> list
        entrees : G, dictionnaire, qui représente le graphe
                : dg, dictionnaire ( positions, bool)
                : x, liste , position
        sortie : Choix, liste, position à choisir (optimale si possible) 
    """
    lesSuccesseurs = G[Tuple(x)]
    if len(lesSuccesseurs) == 0:
        Choix=[]
    else:
        L_Choix = []
        for succ in lesSuccesseurs:
            if not dg[Tuple(succ)]:
                L_Choix.append(succ)
        if len(L_Choix) == 0:
            L_Choix = lesSuccesseurs
        ind = rd(0,len(L_Choix)-1)
        Choix = L_Choix[ind]
    return Choix

C=N=2
G = graphe(C,N)
dg = dico_gagnant(G)

'''
x0 = init(C,N)
for _ in range(5):
    test = strategie_opt(G,dg,x0)
    print(test)
'''

''' Résultat
On arrive sur les deux positions
[[0, 1], [0, 1], [1, 2]] # 1d
[[0, 2], [1, 1], [1, 1]] # 1a
On ne tombe jamais sur 1b
'''

'''
x0 = init(C,N)
for _ in range(10):
    test = strategie_opt(G,dg,x0)
    bool = (test==Pos_1a) or (test==Pos_1d)
    print(bool)
'''

''' Résultat
True
True
True
True
True
True
True
True
True
True
'''

# Q26 - strategies_opt

def strategies_opt(G,dg):
    """strategies_opt(G : dict,dg:dict) ->dict
            entrees : G, dictionnaire, qui représente le graphe
                : dg, dictionnaire ( positions, bool)
            sortie : dico_s, dictionnaire, qui correspond à l'ensemble des positions gagnantes
    """
    dico_s = {}
    for x in G: # x Tuple
        dico_s[x] = strategie_opt(G,dg,x)
    return dico_s

C=N=2
G = graphe(C,N)
dico_g = dico_gagnant(G)
st_opt = strategies_opt(G,dico_g)


print(st_opt)


''' Résultat
{((0, 1), (0, 1), (1, 1), (1, 1)): [[0, 2], [1, 1], [1, 1]], ((0, 2), (1, 1), (1, 1)): [[0, 2], [1, 2]], ((0, 1), (0, 2), (1, 1)): [[0, 3], [1, 1]], ((0, 1), (1, 1), (1, 2)): [[0, 1], [1, 3]], ((0, 1), (0, 1), (1, 2)): [[0, 2], [1, 2]], ((0, 2), (1, 2)): [[1, 4]], ((0, 3), (1, 1)): [], ((0, 2), (0, 2)): [[0, 4]], ((1, 2), (1, 2)): [[1, 4]], ((0, 1), (1, 3)): [], ((0, 4),): [], ((1, 4),): []}
'''

## Simulation de jeu en IA

# Q27 - Simulation d'un jeu

def jeu(C,N):
    G = graphe(C,N)
    x0 = init(C,N)
    dico_g = dico_gagnant(G) # pour afficher le joueur qui gagne en théorie
    Statut_x0 = dico_g[Tuple(x0)]
    if Statut_x0:
        print("Le joueur 1 dispose d'une position gagnante")
    else:
        print("Le joueur 2 dispose d'une position gagnante")
    st_opt = strategies_opt(G,dico_g)
    j = 1
    print('Départ:',x0)
    x = x0
    while len(x) > 0:
        x = st_opt[Tuple(x)]
        j = (3-j)%2
        print('Joueur:',j+1)
        print(x)
    print('a perdu')

# Q28 - Utilisation du jeu

''' A exécuter plusieurs fois
jeu(2,2) # Joueur 1 gagne
jeu(3,3) # Joueur 1 gagne
jeu(2,3) # Joueur 2 gagne
jeu(3,2) # Joueur 2 gagne
'''

'''
Dans tous les cas, le joueur disposant d'une position gagnante au départ gagne le jeu
'''

## Heuristique et Min_max

# Q29 - Heuristique

def h(x,bool): # bool = True si le joueur joue, False si adversaire
    """ h(x : list,bool: bool) -> int
        entrees : x, list, correspond à la configuration/position
                : bool, vaut True si le joueur joue, False sinon
        sortie : retourne un entier qui vaut 0,1, ou 2
    """
    Lc = coups(x)
    #cas ou x ne possede pas de successeur
    if len(Lc) == 0: 
        if bool: # Le joueur a perdu
            return -1
        else: # L'adversaire a perdu, donc le joueur a gagné
            return 1
    else:
        return 0

'''
test = h(Pos_0,True)
print(test)
test = h(Pos_1a,False)
print(test)
test = h(Pos_2b,True)
print(test)
test = h(Pos_3a,False)
print(test)
'''

''' Résultat
0
0
-1
1
'''

# Q30 - Min_max

def min_max(x,p,bool):
    """ min_max(x: list, p: int , bool: bool ) -> int
        entrees : x, list, correspond à la configuration/position
                : p, int, profondeur
                : bool, vaut True si le joueur joue, False sinon
        sortie : entier qui correspond à la valeur min-max attendue
    """
    Lc = coups(x)
    if len(Lc)==0 or p==0:
        return h(x,bool)
    else:
        Lh = []
        if bool: # Coup du joueur : on cherche le maximum
            for c in Lc:
                valMinMax = min_max(c,p-1,False)
                Lh.append(valMinMax)
            return max(Lh)
        else: # Coup de l'adversaire : on cherche le minimum
            for c in Lc:
                valMinMax = min_max(c,p-1,True)
                Lh.append(valMinMax)
            return min(Lh)

'''
test = min_max(Pos_0,1,True)
print(test)
test = min_max(Pos_0,2,True)
print(test)
test = min_max(Pos_0,3,True)
print(test)

test = min_max(Pos_1a,2,True)
print(test)
test = min_max(Pos_1b,2,True)
print(test)
test = min_max(Pos_1c,2,True)
print(test)
test = min_max(Pos_1d,2,True)
print(test)
'''

''' Résultats
0
0
1

-1
1
1
-1
'''

# Q31 # Résultats de min-max à la profondeur max

# Tableau des résultats

print("Joueur disposant d'une position gagnante au départ: ")

Cmax = 3
Nmax = 3

Titre = "  N="
for N in range(1,Nmax+1):
    Titre += str(N) + " "
print(Titre)

for C in range(1,Cmax+1):
    Ligne = 'C=' + str(C) + " "
    for N in range(1,Nmax+1):
        x0 = init(C,N)
        test = min_max(x0,C*N,True) # On pourrait mettre C*N-1
        Ligne += str(test) + ' '
    print(Ligne)

''' Résultat
  N=1 2 3
C=1 -1 1 -1
C=2 1 1 -1
C=3 1 -1 1

On va trouver les positions gagnantes au départ :)
'''

# Tableau des positions gagnantes au départ

print("Joueur disposant d'une position gagnante au départ: ")

Cmax = 3
Nmax = 3

Titre = "  N="
for N in range(1,Nmax+1):
    Titre += str(N) + " "
print(Titre)

for C in range(1,Cmax+1):
    Ligne = 'C=' + str(C) + " "
    for N in range(1,Nmax+1):
        x0 = init(C,N)
        test = min_max(x0,C*N,True) # On pourrait mettre C*N-1
        if test==1:
            Ligne += '1 '
        elif test==-1: # Normalement obligatoire si !=1
            Ligne += '2 '
    print(Ligne)

''' Résultat
  N=1 2 3
C=1 2 1 2
C=2 1 1 2
C=3 1 2 1
'''

# Q32 - Mémoïsation

def min_max_opt(x,p,bool):
    def rec(x,p,bool): # x liste ou tuple
        if Tuple(x) in dico:
            return dico[Tuple(x)]
        else:
            Lc = coups(x)
            if len(Lc)==0 or p==0:
                res = h(x,bool)
                dico[Tuple(x)] = res
                return res
            else:
                Lh = []
                if bool: # Coup du joueur
                    for c in Lc:
                        Min_max = rec(c,p-1,False)
                        Lh.append(Min_max)
                    res = max(Lh)
                    dico[Tuple(x)] = res
                    return res
                else: # Coup de l'adversaire
                    for c in Lc:
                        Min_max = rec(c,p-1,True)
                        Lh.append(Min_max)
                    res = min(Lh)
                    dico[Tuple(x)] = res
                    return res
    dico = {}
    return rec(x,p,bool)

C,N = 3,3
Graphe = graphe(C,N)
x0 = init(C,N)

tic = perf_counter()
min_max(x0,C*N,True)
toc = perf_counter()
T1 = toc - tic
tic = perf_counter()
min_max_opt(x0,C*N,True)
toc = perf_counter()
T2 = toc - tic
Rapport = T1/T2
print("Pour C = "+str(C)+" et N = "+str(N))
print("Temps non optimisé (s):",T1)
print("Temps optimisé (s):",T2)
print("Temps divisé par:",round(Rapport,2),":)")

''' Résultat
Pour C = 3 et N = 3
Temps non optimisé (s): 2.3268505999999434
Temps optimisé (s): 0.0484791999999743
Temps divisé par: 48.0 :)
'''

# Pour la suite, tant qu'à faire

min_max = min_max_opt

# Tableau des résultats avec optimisation en allant jusqu'à N=C=4

print("Joueur disposant d'une position gagnante au départ: ")

Cmax = 4
Nmax = 4

Titre = "  N="
for N in range(1,Nmax+1):
    Titre += str(N) + " "
print(Titre)

for C in range(1,Cmax+1):
    Ligne = 'C=' + str(C) + " "
    for N in range(1,Nmax+1):
        x0 = init(C,N)
        test = min_max(x0,C*N,True) # On pourrait mettre C*N-1
        if test==1:
            Ligne += '1 '
        elif test==-1: # Normalement obligatoire si !=1
            Ligne += '2 '
    print(Ligne)

''' Résultat
  N=1 2 3 4
C=1 2 1 2 1
C=2 1 1 2 2
C=3 1 2 1 1
C=4 1 1 2 1
'''

# Q33 - Choix

def choix_ind_max(L):
    """ choix_ind_max(L: list) -> int
        entree : L,liste de valeurs,
        sortie : Ind, entier qui correspond à l'indice d'une des valeurs maximales 
            (s'il y en a plusieurs, l'indice sera choisi aleatoirement)
    """
    maxi = max(L)  #determination de la valeur maximale
    L_ind = []   #L_ind, liste qui sert a stocker les indices des valeurs maximales
    for i in range(len(L)):
        if L[i]==maxi:
            L_ind.append(i)
    i = rd(0,len(L_ind)-1)
    Ind = L_ind[i]
    return Ind

'''
L = [2,1,2,1]
for _ in range(4):
    test = choix_ind_max(L)
    print(test)
'''

'''
L = [2,1,2,1]
for _ in range(10):
    test = choix_ind_max(L)
    bool = (test == 0) or (test == 2)
    print(bool)
'''

''' Résultat
True
True
True
True
True
True
True
True
True
True
'''

# Q34 - strategies_h

def strategie_h(x,p):
    """ strategie_h(x,p) -> int
        entrees : x,liste position/configuration
                : p, int, profondeur
        sortie : Choix, liste qui correspond à la position suivante
    """
    Lc = coups(x)
    if len(Lc) == 0:
        Choix=[]
    else:
        if p==0: # Choix aléatoire
            ind = rd(0,len(Lc)-1)
        else:
            Lm = []
            for c in Lc:
                valMinMax = min_max(c,p-1,False) # Penser à mettre False
                Lm.append(valMinMax)
            ind = choix_ind_max(Lm)
        Choix = Lc[ind]
    return Choix

"""
test = strategie_h(Pos_0,1)
print(test)

test = strategie_h(Pos_0,2)
print(test)

test = strategie_h(Pos_1b,2)
print(test)

test = strategie_h(Pos_1c,2)
print(test)
"""

''' Résultats
Doit donner 1a 1b 1c 1d
[[0, 2], [1, 1], [1, 1]] 1a
[[0, 1], [0, 2], [1, 1]] 1b
[[0, 1], [1, 1], [1, 2]] 1c
[[0, 1], [0, 1], [1, 2]] 1d

Doit donner 1a 1d
[[0, 2], [1, 1], [1, 1]] 1a
[[0, 1], [0, 1], [1, 2]] 1d

Doit donner 2b
[[0, 3], [1, 1]] 2b

Doit donner 2e
[[0, 1], [1, 3]] 2e
'''

'''
for _ in range(20):
    test = strategie_h(Pos_0,1)
    bool = (test==Pos_1a) or (test==Pos_1b) or (test==Pos_1c) or (test==Pos_1d)
    print(bool)
'''

'''
for _ in range(20):
    test = strategie_h(Pos_0,2)
    bool = (test==Pos_1a) or (test==Pos_1d)
    print(bool)
'''

'''
for _ in range(20):
    test = strategie_h(Pos_1b,2)
    bool = (test==Pos_2b)
    print(bool)
'''

'''
for _ in range(20):
    test = strategie_h(Pos_1c,2)
    bool = (test==Pos_2e)
    print(bool)
'''

# Q35 - Jeu

def jeu_h(C,N,p):
    """ jeu_h(C:int, N:int , p:int)
        entrees : C,N, entiers, nombre de couleurs et nombre de jetons
                : p,, entier, profondeur
    """
    x0 = init(C,N)
    j = 1
    print('Départ:',x0)
    x = x0
    while len(x) > 0:
        x = strategie_h(x,p)
        j = (3-j)%2
        print('Joueur:',j+1)
        print(x)
    print('a perdu')

# Q36 - Utilisation du jeu

jeu_h(2,2,2) # joueur 1 gagnant

'''
Pour avoir utilisé l'algorithme pour
jeu_h(C,N,C*N)
Ainsi, on explore tout le graphe
La solution est toujours au bénéfice du joueur ayant une position gagnante au départ
L'avantage de cet algorithme est qu'il ne demande pas de RAM en excès qui nous bloquait pour créer le graphe
'''