''' 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

def est_gagnante(G,x): # x liste ou Tuple
  

# Q14 - dico_gagnant

def dico_gagnant(G):






# Q15 - dico_gagnant_opt 
# Q15/16 a faire uniquement si vous avez le temps

def dico_gagnant_opt(G):
  # Q16 - Temps d'exécution
'''