## TP jeu de Taquin
# 
#énoncé de Mickaël Péchaud


## 
from collections import deque  # pour la structure de pile
import matplotlib.pyplot as plt



## Premières fonctions

# Q1

def affiche(position = '87 135462'):
    ligne = [0]*5
    ligne[0] = ' --- '
    ligne[1] =  # à compléter  
    ligne[2] =  # 
    ligne[3] = # '|' + position[6 : ] + '|'
    ligne[4] = 
    for line in ligne:
        print  # à compléter


# Q2


def position_vide(position = '87 135462') -> int:
    pass

# Q3


def intervertit(chaine: str, i: int, j:int)-> str:
    # pass

# Q4


'''Il y a quatre déplacements possibles de la case noire (on note i son indice de positions:
- vers le haut: si i >= 3 (on échange alors les éléments d'indice i et i - 3)
- vers le bas: si i <= 5 (on échange alors les éléments d'indice i et i + 3)
- vers la gauche: si i % 3 >= 1 (on échange alors les éléments d'indice i et i - 1)
- vers la droite: si i %3 < = 1 (on échange alors les éléments d'indice i et i + 1)
'''


def positions_voisines(position: str) -> list:
    '''Renvoie la liste des positions accessibles en un coup à partir de la position donnée'''
    n = int(len(position))
    l = []
    i = position_vide(position)
    if i >= 3: #la case vide se déplace vers le haut
        l.append   # (intervertit(position, i, i-3))



# Q6: 
''

# Q7 

# Q8

def resoluble(source = '87 135462' , cible = ' 12345678') -> bool:
    # Structures de données utilisées
    actifs =     # pile dans la laquelle on stocke les positions à explorer
    dejavu =     # dictionnaire dans lequel on stocke les positions déjà explorées
    nbre_positions_explorees = ............ # un compteur
    
    # Exploration
    while       

resoluble(cible ='123 45678') # on trouve 131473 positions explorées
resoluble(cible = '213 45678') # on trouve 181440 positions explorées


## Q9 version récursive

def resoluble_recursif(position: str) -> bool:
    '''Renvoie vrai si et seulement si la position passée en argument est résoluble'''
    dejavu = {position : None}
    def parcours_recursif(position:str) -> bool:
        if position == CIBLE:
            return True
        dejavu[position] = None
        positions = positions_voisines(position)
        for p in positions:
            if not p in dejavu:
                if parcours_recursif(p):
                    return True
        return False
    return parcours_recursif(position)

# test
#print(resoluble_recursif(' 12345678'))
#print(resoluble_recursif('213 45678'))


## Q10 chemins


def calcul_chemin(parents, source, cible):
    pass


parents = {0: None, 9: 0, 2: 0, 1: 9, 3: 2, 5: 2, 6: 2}
calcul_chemin(parents, 0, 3)

## Q10

def chemin(source = '87 135462', cible = '8371 5462'):
    pass



# Q11 parcours en largeur



## importation et test de deque

from collections import deque

q = deque()
q.append(1)
q.append(3)
q.append(7)
while len(q) > 0:
    print(q.popleft())


## Q12 Parcours en largeur 

def plus_court_chemin(source = '87 135462', cible = '8371 5462'):
    pass


 
##



## Q13 et Q14 Statistique sur l'espace des positions

def distances_a_la_cible():
    pass

d = distances_a_la_cible().values()
print(max(d))


plt.hist(d, max(d))
plt.show()