## Bibliothèques, à exécuter une fois pour toute

import matplotlib
import matplotlib.colors
import matplotlib.pyplot as plt
from copy import deepcopy
from collections import deque

## Codes pour les cases et directions

HAUT = 0
BAS = 1
GAUCHE = 2
DROITE = 3

V = 0 # vide
M = 1 # mur
C = 2 # caisse
P = 3 # personnage

## Fonctions d'affichage

# pour une seule carte
def affiche_carte(carte:list, cibles:list = []) -> None:
    '''Affichage graphique d'une carte - avec éventuellement ses cibles'''
    d = 0.3
    h = len(carte)
    w = len(carte[0])
    fig, ax = plt.subplots(1, 1, tight_layout=True)
    # couleurs pour [V, M, C, P]
    couleurs = matplotlib.colors.ListedColormap(['w','#555', '#ff8800', 'w'])
    bornes = [0, 1, 2, 3, 4]
    norme = matplotlib.colors.BoundaryNorm(bornes, couleurs.N, clip=True)   
    # tracé des cases
    ax.imshow(carte, interpolation='none', cmap=couleurs, norm=norme, extent=[0, w, 0, h], zorder=0)
    # tracé de la grille
    for i in range(h + 1):
        ax.axhline(i, lw=2, color='k', zorder=5)
    for j in range(w + 1):
        ax.axvline(j, lw=2, color='k', zorder=5)
    for i in range(h):
        for j in range(w):
            if carte[i][j] == P:
                circle = plt.Circle(( j+0.5 , h-i-0.5 ), 0.3, color = '#55cc77') 
                ax.add_artist(circle)
    # affichage des cibles
    for c in cibles:        
        plt.plot([c[1]+d,c[1]+1-d],[h-c[0]-d,h-(c[0]+1)+d], color = '#aa4400', linewidth = 3)
        plt.plot([c[1]+1-d, c[1]+d],[h-c[0]-d,h-(c[0]+1)+d], color = '#aa4400', linewidth = 3)
    # suppression des axes
    ax.axis('off')
    fig.show()
    

# Pour plusieurs cartes !

def affiche_cartes(cartes:list, liste_cibles:list = None) -> None:
    '''Affichage graphique d'une liste de carte - avec éventuellement ses cibles'''
    d = 0.3
    
    if liste_cibles == None:
        liste_cibles = [[] for _ in range(len(cartes))]
    
    # couleurs pour [V, M, C, P]
    couleurs = matplotlib.colors.ListedColormap(['w','b', '#ff8800', 'w'])
    bornes = [0, 1, 2, 3, 4]
    norme = matplotlib.colors.BoundaryNorm(bornes, couleurs.N, clip=True)   
    
    fig, axs = plt.subplots(4, len(cartes)//4 + 1, tight_layout=True)
    for ax in axs.flat:
        # suppression des axes
        ax.axis('off')
    
    for (ax, carte, cibles) in zip(axs.flat, cartes, liste_cibles):
        
        h = len(carte)
        w = len(carte[0])
        # tracé des cases
        ax.imshow(carte, interpolation='none', cmap=couleurs, norm=norme, extent=[0, w, 0, h], zorder=0)
        # tracé de la grille
        for i in range(h + 1):
            ax.axhline(i, lw=2, color='k', zorder=5)
        for j in range(w + 1):
            ax.axvline(j, lw=2, color='k', zorder=5)
        for i in range(h):
            for j in range(w):
                if carte[i][j] == P:
                    circle = plt.Circle(( j+0.5 , h-i-0.5 ), 0.3, color = '#55cc77') 
                    ax.add_artist(circle)
        # affichage des cibles
        for c in cibles:        
            ax.plot([c[1]+d,c[1]+1-d],[h-c[0]-d,h-(c[0]+1)+d], color = '#aa4400', linewidth = 3)
            ax.plot([c[1]+1-d, c[1]+d],[h-c[0]-d,h-(c[0]+1)+d], color = '#aa4400', linewidth = 3)
        
    fig.show()
##    

carte1 = [
[M, M, M, M, M, M],
[M, M, M, V, P, M],
[M, M, M, C, V, M],
[M, V, C, V, V, M],
[M, V, V, V, V, M],
[M, M, M, V, V, M],
[M, M, M, V, V, M],
[M, M, M, M, M, M],
]


carte1_resolue = [
[M, M, M, M, M, M],
[M, M, M, V, P, M],
[M, M, M, V, V, M],
[M, V, V, C, V, M],
[M, V, V, V, V, M],
[M, M, M, V, C, M],
[M, M, M, V, V, M],
[M, M, M, M, M, M],
]   

cibles1 = [(3, 3), (5, 4)]

carte2 = [
[M,M,M,M,M,M],
[M,M,V,V,M,M],
[M,V,P,C,M,M],
[M,M,C,V,M,M],
[M,M,V,C,V,M],
[M,V,C,V,V,M],
[M,V,V,C,V,M],
[M,M,M,M,M,M],
]

cibles2 = [(5,1),(6,1),(6,2),(6,3),(6,4)]

carte3 = [
[M,M,M,M,M,M,M,M,M],
[M,V,V,V,M,M,M,M,M],
[M,V,M,V,M,V,V,V,M],
[M,V,C,V,V,V,C,V,M],
[M,V,V,M,V,M,V,M,M],
[M,V,P,V,C,V,V,M,M],
[M,V,V,C,V,M,M,M,M],
[M,M,M,M,M,M,M,M,M],
]

cibles3 = [(4,1), (4,2), (6,1), (6,2)]

carte4 = [
[M,M,M,M,M,M,M,M],
[M,M,M,V,V,V,V,M],
[M,M,M,C,C,C,V,M],
[M,P,V,C,V,V,V,M],
[M,V,C,V,V,V,M,M],
[M,M,M,M,M,V,V,M],
[M,M,M,M,M,M,M,M],
]

cibles4 = [(3,4),(3,5),(4,3),(4,4),(4,5)]




## Premières fonctions

# N. B. 
# L'instruction "pass" est là pour dire à Python de "passer" à la suite. En effet laisser vide provoquerait une erreur.
# Vous devez la supprimer pour mettre votre code à la place


def dim(c):
    '''Renvoie les dimensions de la carte, sous forme d'un couple (w, h)'''
    pass

def succes(carte, cibles):
    '''Renvoie True ssi la position est gagnante'''
    for (a, b) in cibles:
        pass
    
 
 # on donne la fonction suivante déjà complète
 def coordonnees_personnage(c):
    '''Renvoie les coordonnées d'une case de la carte contenant un personnage'''
    (w, h) = dim(c)
    for i in range(h):
        for j in range(w):
            if c[i][j] == P:
                return (i, j)
    assert(False) # Il doit y avoir un personnage quelquepart...   
    
   
    
def cases_libres_voisines(c, i, j):
    '''Renvoie la liste des cases vides voisines de (i, j) dans la carte c'''
    cases_vides = []  # liste de couples
    pass
    
    
def clone_personnage(c, i, j):
    '''Transforme la carte c en carte où toutes les positions accessibles par le personnage sans déplacer de caisse sont de valeur P. Effet de bord : modifie la carte passée en argument.'''
    accessibles = deque()  # cases accessibles
    accessibles.append( (i,j) )  # Attention, on veut des *couples*
    
    while len(accessibles) > 0:
        (i_cour, j_cour) = accessibles.pop()
        voisines = "à compléter"
        for (i_voisin, j_voisin) in voisines:
            pass
        
    
    

def clone_personnage_recursif(c, i, j):
    '''Transforme la carte c en carte où toutes les positions accessibles par le personnage sans déplacer de caisse sont de valeur P. Effet de bord : modifie la carte passée en argument.'''
    pass


## Détermination des positions accessibles

# La fonction suivante est déjà complète !
def coordonnees_caisses(c):
    '''Renvoie la liste des coordonnées des caisses'''    
    (w, h) = dim(c)
    liste_coords = []
    for i in range(h):
        for j in range(w):
            if c[i][j] == C:
                liste_coords.append( (i, j) )
    return liste_coords

        

def supprime_tous_personnages(c):
    '''Remet à V toutes les cases à P. Effet de bord : modifie la carte passée en argument.'''
    (w, h) = dim(c)
    pass
    
    
def poussable(c, i, j, direction):
    '''Détermine si la caisse en position (i, j) dans la carte c est poussable dans la direction indiquée. Suppose que le personnage a été cloné dans la carte c'''
    if direction == HAUT: 
        return (c[i-1][j] == V or c[i-1][j] == P) and c[i+1][j] == P
    if direction == BAS:
        return (c[i+1][j] == V or c[i+1][j] == P) and c[i-1][j] == P
    if direction == DROITE:
        pass
    if direction == GAUCHE:
        pass
        
def pousser(c, i, j, direction):
    '''Renvoie une nouvelle carte correspondant à c où la caisse en (i, j) est poussée dans la direction indiquée. Suppose que le poussable correspondant renvoie True. La carte renvoyée ne contiendra qu'un personnage.'''
    c2 = deepcopy(c) # copie profonde de la carte




def cartes_accessibles(c):
    '''Renvoie la liste des positions voisines de la position courante.

    Attention c doit être une carte avec personnage "cloné"
    
    '''
    pass

##



    

def code(c):
    '''Renvoie le code correspondant à c'''
    return (coordonnees_personnage(c),)+tuple(coordonnees_caisses(c))
    
## Résolution
    
def nombre_positions(carte):
    pass

def resoluble(carte, cible):
    pass

def chemin(carte, cibles):
    pass
    
## test de la fonction chemin : affichage du solution complète pour le premier niveau
def test_chemin():
    for c in chemin(carte1, cibles1):
        affiche_carte_leger(c, cibles1)


## Plus courts chemins

def plus_court_chemin(carte, cibles):
    pass
    
## Exploration guidée

def carte_distances(carte, cibles):
    pass
    
def liste_caisses(carte):
    pass
    
def heuristique(carte, distance):
    pass
    
## File de priorité et exemple d'utilisation

# Téléchargez le module et décommentez la ligne suivante
# from priorityqueue import PriorityQueue

def code2(l):
    return tuple(l)

def exple_PriorityQueue():
    p = PriorityQueue(code2)
    
    p.add([1, 2, 3], 5)
    p.add([0, 3, 2], 4)
    p.add([2, 4, 0], 6)
    p.add([3, 5, 1], 8)
    
    p.decreasepriority([3, 5, 1], 5)
    
    while not p.empty():
        print (p.popmin())


##

def plus_court_chemin_astar(carte, cibles):
    pass