# Equipe n° :
# Lycée :
################################################################

#################################
#  Fonctions à ne pas modifier  #
#################################

noms_colonnes = "abcdefghijklmnopqrstuvwxyz"

def nom_case(coord):
    """ Renvoie le nom de la case à partir des coordonnées :
        par exemple : (2, 4) -> 'c5' """
    colonne, ligne = coord
    return noms_colonnes[colonne] + str(ligne+1)

def coord_case(case):
    """ Renvoie les coordonnées à partir du nom de la case :
        par exemple : 'e2' -> (4, 1) """
    colonne = noms_colonnes.index(case[0].lower())
    ligne = int(case[1:]) - 1
    return (colonne, ligne)

def taille(grille):
    """ Renvoie le nombre de colonnes et de lignes de la grille """
    nb_col, nb_lignes = len(grille[0]), len(grille)
    return nb_col, nb_lignes

def echiquier(n):
    """ Renvoie une grille de dimension n*n """
    return [[0 for col in range(n)] for ligne in range(n)]

def valeur(grille, case):
    """ Renvoie la valeur stockée dans la case de la grille """
    colonne, ligne = coord_case(case)
    return grille[ligne][colonne]

def modification(grille, case, valeur):
    """ Remplace la valeur dans la case de la grille par valeur """
    colonne, ligne = coord_case(case)
    grille[ligne][colonne] = valeur

def voisins(grille, case):
    """ Renvoie la liste des voisins de la case dans la grille """
    liste_voisins = []
    colonne, ligne = coord_case(case)
    for dc, dl in deplacements:
        coord = (colonne + dc, ligne + dl)
        if 26 > colonne + dc >= 0:
            case2 = nom_case(coord)
            if dans_echiquier(grille, case2):
                liste_voisins.append(case2)
    return liste_voisins

def tri(grille, liste_voisins):
    """ Trie une liste de cases par score """
    liste_voisins.sort(key=lambda c: score(grille, c))

def affichage(grille, case=None, aff_voisins=False, aff_nb_vois=False,
              case_vide=".", case_vue="O", cavalier="C", case_voisine="V", autre="X"):
    """ Affiche la grille.
        Si case n'est pas None, cela affiche la case actuelle.
        Si aff_voisins est True, affiche les cases accessibles.
        Si aff_nb_vois est True, affiche le nombre de voisins des cases accessibles.
        Les paramètres suivants servent à indiquer les symboles utilisés. """
    nb_col, nb_lignes = taille(grille)
    ligne_noms_col = "   " + noms_colonnes[:nb_col]
    ligne_bord = "  +" + "-"*nb_col + "+"
    print(ligne_noms_col)
    print(ligne_bord)
    liste_voisins = []
    if case is not None:
        coord = coord_case(case)
        if aff_voisins:
            liste_voisins = voisins_libres(grille, case)
    else:
        coord = (-1, -1)
    for ligne in range(len(grille)-1,-1,-1):
        texte_ligne = f"{ligne+1:2}|"
        for col in range(len(grille[ligne])):
            case = nom_case((col, ligne))
            if coord == (col, ligne):
                texte_ligne += cavalier
            elif case in liste_voisins:
                s = score(grille, case)
                if aff_nb_vois and isinstance(s, int):
                    texte_ligne += str(s)
                else:
                    texte_ligne += case_voisine
            elif grille[ligne][col] == 0:
                texte_ligne += case_vide
            elif grille[ligne][col] == 1:
                texte_ligne += case_vue
            else:
                texte_ligne += autre
        texte_ligne += f"|{ligne+1}"
        print(texte_ligne)
    print(ligne_bord)
    print(ligne_noms_col)

def interactif(grille, case):
    """ Permet de chercher un parcours étape par étape
        dans la grille donnée, en partant de la case donnée.
        On donne soit le nom de la case suivante,
        soit U pour annuler le dernier coup,
        soit Q pour quitter et voir le chemin parcouru. """
    continuer = True
    chemin = [case]
    modification(grille, case, 1)
    while continuer:
        affichage(grille, case, True, True)
        liste_voisins = voisins_libres(grille, case)
        if len(liste_voisins) > 0:
            print("Cases accessibles :", ', '.join(liste_voisins))
        else:
            print("Pas de case accessible")
        if len(chemin) > 1:
            print("U (annuler) ou Q (quitter)")
        else:
            print("Q (quitter)")
        reponse = input("Donner une case ou une commande : ")
        if reponse.upper() == "Q":
            continuer = False
        elif reponse.upper() == "U" and len(chemin) > 1:
            modification(grille, case, 0)
            chemin.pop()
            case = chemin[-1]
        elif reponse.lower() in liste_voisins:
            case = reponse.lower()
            chemin.append(case)
            modification(grille, case, 1)
        else:
            print("Réponse invalide")
    print("Chemin parcouru :")
    print(chemin)

def applique_chemin(grille, chemin):
    """ Effectue les déplacements indiqués par le chemin
        dans la grille en marquant les cases visitées.
        Si un déplacement est invalide,
        on arrête et on renvoie False.
        Sinon on renvoie True. """
    case = chemin[0]
    if valeur(grille, case) != 0:
        return False
    modification(grille, case, 1)
    for i in range(1, len(chemin)):
        liste_voisins = voisins(grille, case)
        case = chemin[i]
        if valeur(grille, case) != 0 or case not in liste_voisins:
            return False
        modification(grille, case, 1)
    return True

def importation(structure):
    grille = []
    n = len(structure)
    for i in range(len(structure)):
        ligne = []
        motif = structure[n-1-i]
        for j in range(len(motif)):
            symbole = motif[j]
            if symbole == " ":
                ligne.append(0)
            else:
                ligne.append(2)
        grille.append(ligne)
    return grille

#################################
#      Fonctions à modifier     #
#################################

# Question 1
deplacements = [(1, 2), (-1, 2), ...]

# Question 2
def dans_echiquier(grille, case):
    """ Renvoie un booléen indiquant si la case
        est dans la grille ou pas """
    nb_col, nb_lignes = taille(grille)
    colonne, ligne = coord_case(case)
    return 0 <= ... < nb_lignes and ...

# Question 3
def voisins_libres(grille, case):
    """ Renvoie la liste des voisins libres de la case dans la grille """
    liste_voisins = []
    for case2 in voisins(grille, case):
        if ...:
            liste_voisins.append(...)
    return liste_voisins

# Question 4
def score(grille, case):
    """ Renvoie le nombre de voisins libres de case dans la grille """
    ...  # Vous pouvez rajouter plusieurs lignes

# Question 5
def voisins_tries(grille, case):
    """ Renvoie la liste triée par score des voisins libres de la case """
    liste_voisins = ...
    ...
    return ...

# Question 6
def warnsdorf(grille, case):
    """ Cherche le plus long chemin possible dans la grille
        à partir de la case en utilisant la règle de Warnsdorf.
        Renvoie la liste des cases visitées. """
    chemin = []
    continuer = ...  # Mettre une valeur qui indique qu'il faut continuer
    while continuer:
        chemin.append(case)
        ...  # mettre la case dans la grille à 1
        liste_voisins = ...  # On récupère la liste triée des voisins libres
        if ...:  # Il y a au moins un voisin
            case = ...  # On prend le premier voisin
        else:
            continuer = ...  # On a fini
    return ...  # Il faut renvoyer le résultat attendu

# Question 7
solution26 = ...

# Question 8
coeur = ...
