#%%

##############
# JEU DE NIM #
##############

# Question 1

def GrapheNim(N:int) -> dict:
    '''Renvoie le dictionnaire d'adjacence du jeu de Nim'''
    G={}
    G[0]=[]
    G[1]=[0]
    G[2]=[0,1]
    for k in range(3,N+1):
        G[k]=[k-1,k-2,k-3]
    return G

print(GrapheNim(9))

# Question 2

for N in range(2,100,10):
    G=GrapheNim(N)
    arc=0
    for s in G:
        arc+=len(G[s])
    print("Nb d'arcs=",arc," et 3*N-3=",3*N-3)

# Question 3
"""
Un dictionnaire d'adjacence est plus adapté ici car chaque sommet a au maximum 3 voisins.
Une matrice d'adjacence nécessite un stockage de N^2 coefficients.
Pour un dictionnaire, seulement N clefs et 3N valeurs ici.
"""

# Question 4
""" Le graphe de jeu ne doit surtout pas comporter de cycle.
Sinon il existe une partie infinie en suivant les sommets du cycle. """

# Question 5
"""
Il y a 5 bâtonnets et c'est au joueur b de jouer.
Le joueur b ne peut prendre que 1, 2 ou 3 bâtonnets.
Il en laisse donc 4, 3 ou 2 au joueur a.
Dans tous les cas le joueur a peut prendre juste ce qu'il faut pour
n'en laisser qu'un.
Le joueur b sera alors obligé de prendre cet unique bâtonnet et aura perdu.
"""

# Question 6
"""
A chaque tour il faut laisser au joueur b un nombre 
de bâtonnets de la forme 4n+1. 
Ainsi quel que soit le nombre de bâtonnets X retirés 
par le joueur b,
il suffit que le joueur a en retire Y avec X+Y=4.
Le nombre de bâtonnets sera alors de la forme
 4n+1-4 = 4(n-1)+1.
Ceci jusqu'à la fin et laisser 5, puis 1 bâtonnet au joueur b.
"""

# Question 7
"""
Si N n'est pas de la forme 4n+1
Celui qui possède une stratégie gagnante est le joueur
 qui commence. En effet quel que soit le nombre de bâtonnets,
il peut toujours en laisser exactement un nombre de la forme
 4n+1 au joueur b en en enlevant 1, 2 ou 3.
Si N est de la forme 4n+1 c'est le joueur b qui possède
 une stratégie gagnante
"""

# Question 8

""" On a doublé le nombre de sommets et le nombre d'arêtes,
il y a donc maintenant 2N sommets et 6N-6 arrêtes."""

# Question 9

def GrapheNim2(N:int,j1:str,j2:str) -> dict:
    '''Renvoie le dictionnaire d'adjacence biparti du jeu de Nim'''
    G={}
    opp={j1:j2,j2:j1}
    for j in [j1,j2]:
        G[(0,j)]=[]
        G[(1,j)]=[(0,opp[j])]
        G[(2,j)]=[(0,opp[j]),(1,opp[j])]
        for k in range(3,N+1):
            G[(k,j)]=[(k-1,opp[j]),(k-2,opp[j]),(k-3,opp[j])]
    return G

print(GrapheNim2(5,"Malo","Morgan"))

#%%

##############################
# SELECTION BAGUETTE MAGIQUE #
##############################

## À exécuter une fois pour toute

import matplotlib.pyplot as plt
import matplotlib.image as mpimg
import os
from random import randint
from math import sqrt

# Modifier de façon à indiquer le répertoire où se trouvent les images!

# charge une image sous forme de liste de listes
img = (mpimg.imread('./guepiers.JPG')).tolist()
# affichage de l'image
plt.imshow(img)
plt.show()

#%%%

# Question 1

def dim(img:list) -> tuple:
    '''Renvoie le couple (largeur,hauteur) de l'image'''
    return len(img[0]),len(img)

print("Les dimensions de l'image img sont",dim(img))

#%%%

# Question 2

def niveau_de_gris_pixel(p:list) -> None:
    '''modifie un pixel en niveau de gris'''
    [r,g,b] = p
    m = (r+g+b)//3
    p[0],p[1],p[2]=m,m,m

def niveaux_de_gris(img:list) -> None:
    '''convertit une image en niveaux de gris'''
    (w, h) = dim(img)
    for i in range(h):
        for j in range(w):
            niveau_de_gris_pixel(img[i][j])

def niveaux_de_gris2(img:list) -> None:
    '''convertit une image en niveaux de gris'''
    (w, h) = dim(img)
    for i in range(h):
        for j in range(w):
            [r,g,b] = img[i][j]
            m = (r+g+b)//3
            img[i][j]=[m,m,m]

img = (mpimg.imread('./guepiers.JPG')).tolist()
niveaux_de_gris(img)
#niveaux_de_gris2(img)
plt.imshow(img)
plt.show()

#%%%

# Question 3

def sq_distance_couleurs(c1, c2):
    '''renvoie le carré de la distance entre deux couleurs'''
    [r1, g1, b1] = c1
    [r2, g2, b2] = c2
    return (r1 - r2)**2 + (g1 - g2)**2 + (b1 - b2)**2
    

#%%%

# Question 4

def selection_couleur(img, i, j, seuil):
    '''sélection des pixels d'une image par seuil'''
    p = img[i][j]
    (w, h) = dim(img)
    for i in range(h):
        for j in range(w):
            if sq_distance_couleurs(p, img[i][j]) < seuil**2:
                img[i][j] = [255,0,0]

# Cette fonction est bien entendu de complexité O(h*w). (résolution de l'image)
            
img = (mpimg.imread('./guepiers.jpg')).tolist()
selection_couleur(img, 50, 50, 30)
plt.imshow(img)
plt.show()


#%%%

# Question 5

def voisins(i, j, h, w):
    '''renvoie les quatre (ou moins) pixels voisins de (i,j) dans une image de dimensions (h,w)'''
    r = []
    if i>0:
        r.append([i-1,j])
    if j>0:
        r.append([i,j-1])
    if i<h-1:
        r.append([i+1,j])
    if j<w-1:
        r.append([i,j+1])
    return r

# Question 6

def baguette_magique(img, i, j, seuil):
    '''sélection par baguette magique à partir de (i,j)'''
    c = img[i][j]
    (w, h) = dim(img)
    a_explorer = [(i,j)]
    while a_explorer != []:
        [i, j] = a_explorer.pop()
        img[i][j] = [255, 0, 0]
        lesvoisins = voisins(i, j, h, w)
        for v in lesvoisins:
            if img[v[0]][v[1]] != [255, 0, 0] and (v[0], v[1]) not in a_explorer:
                if sq_distance_couleurs(c, img[v[0]][v[1]]) < seuil**2:
                    a_explorer.append((v[0],v[1]))

def baguette_magique2(img, i, j, seuil):
    '''sélection par baguette magique à partir de (i,j)'''
    c = img[i][j]
    (w, h) = dim(img)
    a_explorer = [(i,j)]
    # Même code avec un dictionnaire (copie de a_explorer)
    # de sorte à ce que la recherche "if ... in Vu" soit en O(1)
    Vu={(i,j):True}
    while a_explorer != []:
        [i, j] = a_explorer.pop()
        img[i][j] = [255, 0, 0]
        lesvoisins = voisins(i, j, h, w)
        for v in lesvoisins:
            if img[v[0]][v[1]] != [255, 0, 0] and (v[0], v[1]) not in Vu:
                if sq_distance_couleurs(c, img[v[0]][v[1]]) < seuil**2:
                    a_explorer.append([v[0],v[1]])
                    Vu[(v[0],v[1])]=True

image = (mpimg.imread('./guepiers.jpg')).tolist()
baguette_magique2(image, 50, 50, 30)
plt.imshow(image)
plt.show()

#%%%

# Question 7

# On a utilisé un algorithme de parcours en profondeur!
# (on visite les sommets fils avant les sommets pères)

from collections import deque

def baguette_magique_pile(img, i, j, seuil):
    '''sélection par baguette magique à partir de (i,j)'''
    c = img[i][j]
    (w, h) = dim(img)
    a_explorer = deque([[i,j]])
    while a_explorer != deque([]):
        [i, j] = a_explorer.pop()
        img[i][j] = [255, 0, 0]
        lesvoisins = voisins(i, j, h, w)
        for v in lesvoisins:
            if img[v[0]][v[1]] != [255, 0, 0] and (v[0], v[1]) not in a_explorer:
                if sq_distance_couleurs(c, img[v[0]][v[1]]) < seuil**2:
                    a_explorer.append([v[0],v[1]])

image = (mpimg.imread('./guepiers.jpg')).tolist()
baguette_magique_pile(image, 50, 50, 30)
plt.imshow(image)
plt.show()

#%%%

# Question 8

# On va utiliser ici un algorithme de parcours en largueur!
# (on visite les sommets père avant les sommets fils)

from collections import deque

def baguette_magique_file(img, i, j, seuil):
    '''sélection par baguette magique à partir de (i,j)'''
    c = img[i][j]
    (w, h) = dim(img)
    a_explorer = deque([[i,j]])
    compt=0
    while a_explorer != deque([]):
        compt+=1
        print(compt)
#        print(len(a_explorer))
        [i, j] = a_explorer.popleft()
        img[i][j] = [255, 0, 0]
        lesvoisins = voisins(i, j, h, w)
        for v in lesvoisins:
            if img[v[0]][v[1]] != [255, 0, 0] and (v[0], v[1]) not in a_explorer:
                if sq_distance_couleurs(c, img[v[0]][v[1]]) < seuil**2:
                    a_explorer.append([v[0],v[1]])

image = (mpimg.imread('./guepiers.jpg')).tolist()
baguette_magique_file(image, 50, 50, 10)
plt.imshow(image)
plt.show()

#%%

#########################
# RETOUR SUR JEU DE NIM #
#########################

# Question 10

N=5
j1="Morgan"
j2="Malo"

def Nim_Profondeur_rec(N,joueur,dico):
    """ Parcours en profondeur récursif """
    if (N,joueur) not in dico:
        if joueur==j1:
            opp=j2
        else:
            opp=j1
        if N>2:
            Voisins=[(N-1,opp),(N-2,opp),(N-3,opp)]
        elif N==2:
            Voisins=[(N-1,opp),(N-2,opp)]
        elif N==1:
            Voisins=[(N-1,opp)]
        elif N==0:
            Voisins=[]
        dico[(N,joueur)]=Voisins
        for v in Voisins:
            Nim_Profondeur_rec(v[0],v[1],dico)

dicoPR={}
Nim_Profondeur_rec(N,j1,dicoPR)
for clef in dicoPR:
    print(clef,dicoPR[clef])

#%%

def Nim_Profondeur(N,joueur):
    """parcours en profondeur itératif avec une pile"""
    dico={}
    pile=[(N,joueur)]
    while len(pile)!=0:
        S=pile.pop()
        N,joueur=S
        if joueur==j1:
            joueur=j2
        else:
            joueur=j1
        if N>2:
            Voisins=[(N-1,joueur),(N-2,joueur),(N-3,joueur)]
        elif N==2:
            Voisins=[(N-1,joueur),(N-2,joueur)]
        elif N==1:
            Voisins=[(N-1,joueur)]
        elif N==0:
            Voisins=[]
        dico[S]=Voisins
        for v in Voisins:
            if v not in dico:
                pile.append(v)
    return dico

dicoP=Nim_Profondeur(N,j1)
for clef in dicoP:
    print(clef,dicoP[clef])
    
assert dicoPR==dicoP

#%%

from collections import deque

def Nim_Largeur(N,joueur):
    """Parcours en largeur itératif avec file format deque"""    
    dico={}
    file=deque([(N,joueur)])
    while len(file)!=0:
        S=file.popleft()
        N,joueur=S
        if joueur==j1:
            joueur=j2
        else:
            joueur=j1
        if N>2:
            Voisins=[(N-1,joueur),(N-2,joueur),(N-3,joueur)]
        elif N==2:
            Voisins=[(N-1,joueur),(N-2,joueur)]
        elif N==1:
            Voisins=[(N-1,joueur)]
        elif N==0:
            Voisins=[]
        dico[S]=Voisins
        for v in Voisins:
            if v not in dico:
                file.append(v)
    return dico

dicoL=Nim_Largeur(N,j1)
for clef in dicoL:
    print(clef,dicoL[clef])

assert dicoPR==dicoP and dicoL==dicoP