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

#________________________________________________
##      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]]


# 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]]

#=================================
## 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 -1
    """




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


'''
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 ( a faire si vous avez le temps)
def min_max_opt(x,p,bool):
    """
    """    


# 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)
    """

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


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


# Q36 - Utilisation du jeu


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