Vous devez écrire une fonction solve(sourcename:str, destname:str) qui reçoit le nom de fichier sourcename qui contient le labyrinthe, et le nom de ficher destname qui contiendra la solution.

Il vous faudra

• ouvrir le fichier sourcename
• lire le contenu du fichier et constituer un tableau représentant le labyrinthe,
• trouver le point de départ marqué par 'D',
• trouver la solution du labyrinthe
• écrire le labyrinthe avec solution dans destname.

Je vous propose deux approches simples.

Supposons que le point de départ soit en ligne 3 et colonne 5. On a donc les coordonnées (5,3).

On commence par créer un tableau chemin = [(5,3)] puis, tant que l'on n'a pas trouvé le point d'arrivée, on répète :

• trouver tous les voisins possibles de la dernière position trouvée,
• choisir au hasard parmi ces voisins
• si ce voisin est déjà présent dans la liste, retirer tout ce suis ce voisin.
  Par exemple, si

  chemin = [(5,3), (5,4), (5,5), (6,5), (7,5), (7,4), (7,3), (8,3), (9,3), (9,4), (9,5), (8,5)]

  et que l'on a décidé d'aller ensuite en (7,5) qui est déjà dans le chemin, alors c'est qu'on a fait un détour inutile et on peut l'enlever :

  chemin = [(5,3), (5,4), (5,5), (6,5), (7,5)]

• sinon, ajouter ce voisin à la suite.
  Par exemple, si

  chemin = [(5,3), (5,4), (5,5), (6,5), (7,5)]

  et que l'on a décidé de visiter (8,5) qui n'est pas déjà présent dans la liste, alors on se contente de l'ajouter à la suite :

  chemin = [(5,3), (5,4), (5,5), (6,5), (7,5), (8,5)]

Le chemin se constitue au hasard. Théoriquement on pourrait tourner en rond sans jamais trouver la sortie, mais en répétant l'opération un assez grand nombre de fois, on fini toujours par trouver un chemin.

homme ivre fait référence à la démarche aléatoire, comme un homme ivre qui ne sait pas où il va.

La méthode est connue : toujours suivre le mur de droite – ou le mur de gauche, cela revient au même.

Pour suivre cette méthode, il faut suivre pas à pas l'itinéraire du marcheur imaginaire qui parcours le labyrinthe et toujours tenir compte de son orientation.

La règle est simple :

• si le marcheur a un couloir sur sa droite, il tourne sur sa droite et avance d'un pas,
• sinon, il tourne sur sa gauche

Pour garder la mémoire de son itinéraire, on crée un tableau chemin qui est initialisé avec la position de départ. Par exemple chemin = [(5,3)] si la position de départ est 5e ligne et 3e colonne.

Chaque fois que le marcheur avance, on ajoute à chemin la nouvelle position atteinte.

Comme pour le cas de l'homme ivre, cette méthode peut conduire à passer plusieurs fois par la même position. Cela arrive si on a essayé une impasse par exemple. Dans une telle éventualité, c'est mieux de supprimer le détour inutile de l'itinéraire.

# exemple :
chemin = [(5,3), (5,4), (5,5), (6,5), (7,5), (7,4), (7,3), (8,3), (9,3), (9,4), (9,5), (8,5)]
# on s’apprête à ajouter la position (7,5) mais (7,5) déjà dans chemin
# à la place, on supprime tout ce qui suit (7,5) dans chemin
chemin = [(5,3), (5,4), (5,5), (6,5), (7,5)]

f = open(filename, 'r', encoding='utf8')
content = f.read()
f.close()
lines = content.split('\n')

Suite à ce code, lines contient un tableau où chaque item est une ligne du fichier.

['*******************', '*D*          *A   *', '* ******** ****** *', '*                 *', '*******************', '']

Vous remarquez que la dernière ligne est vide. Cela peut arriver mais n'est pas certain. Cela dépend de comment à été écrit le fichier. On peut s'assurer que la dernière ligne n'est pas vide en supprimant toute dernière ligne qui serait vide :

while lines[-1] == '':
    lines.pop()

La fonction `pop`a pour effet d'enlever le dernier élément.

Maintenant que nous disposons de lines, nous pouvons facilement consulter le contenu du fichier.

>>> lines[2][0]
'-'

En effet, lines[2] correspond au contenu de la ligne d'indice 2, c'est à dire '* ******** ****** *'. Donc lines[2][1] est le caractère de rang 0 dans cette ligne : '*'.

Il sera plus simple de raisonner en points cardinaux. Le bonhomme cheminant dans le labyrinthe peut aller au Nord, au Sud, à l'Est, à l'Ouest. La position du bonhomme est donnée par une paire de coordonnées (line, col) qui donne sa ligne et sa colonne.

Aller vers le Nord, c'est diminuer le numéro de ligne de 1. La colonne ne change pas. On peut raisonner de la même façon pour les autres de sorte que l'on pourra définir :

NORD = (-1,0)
SUD = (1,0)
EST = (...) # je vous laisse deviner
OUEST = (...) # idem

Ensuite, on dit que dans certains cas, le bonhomme tourne à droite. Tourner à droite quand on va au Nord, cela fait aller à l'Est. Si on va au Sud, tourner à droite fait aller à l'Ouest.

C'est bien de placer tout ça dans une fonction :

def droite(dir_actuelle):
    if dir_actuelle == NORD:
        return EST
    elif dir_actuelle == SUD:
        return ...
    ...  # je vous laisse compléter

Vous pouvez facilement faire l'équivalent pour la gauche.

Je souhaite savoir si une certaines position (line, col) correspond à un mur. Cela arrive si le caractère à cet endroit est '*', ou bien si (line, col) correspond à une position hors du tableau.

C'est bien de prévoir une fonction pour cela :

def is_wall(lines, line, col):
    """
    lines: lignes du fichier
    line, col: position demandée
    renvoie True si la position correspond à un mur
    """
    hauteur = ... # nombre de lignes
    largeur = ... # nombre de colonnes
    if not 0 <= line < hauteur or not 0 <= col < largeur:
        # en dehors du cadre donc
        return ...
    car = lines[line][col]
    # en fonction de la valeur de car, on sait si c'est un mur
    ...

On a obtenu une réponse comme chemin = [(5,3), (5,4), (5,5), (6,5), (7,5)] qui est une liste de coordonnées. On souhaiterait remplacer les caractères à ces position par '.' et écrire le résultat dans un fichier. Il se peut qu'une de ces coordonnées tombe sur 'D' ou 'A'. Dans ce cas, c'est mieux de ne pas remplacer. On ne remplace donc que si ça tombe sur un espace.

On pourra utiliser la fonction suivante qui remplace le caractère à un certain indice :

def replace_car_at(chaine, new_car, index):
    """
    chaine: chaine de caractère originale
    new_car: nouveau caractère
    index: position du remplacement
    renvoie une copie de chaine où le caractère à la position
    index est remplacé par new_car. Si index trop grand, aucun changement
    """
    if index >= len(chaine):
        return chaine
    return chaine[:index] + new_car + chaine[index+1:]

Une fois lines modifié, on peut faire l'opération inverse de l'ouverture :

content = '\n'.join(lines) # recolle les lignes
f = open(filename, 'w', encoding='utf8')
f.write(content)
f.close()