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

'''