Rapport de résolution du problème Ghost Legs
21/01/2023
Année universitaire 2023
Retour à l'accueil
Dans ce rapport, nous allons nous intérresser à la résolution d’un problème tiré du site Codingames, Ghost Legs. Ce problème est originaire d’Asie (on le retrouve sous le nom de Amidakuji au Japon) et, est avant tout une méthode de loterie qui permet de “tirer au sort” des paires d’élements. Le principe de cette méthode est assez simple, on a un certain nombre de points de départ, chacuns reliés à une barre verticale. Ces barres verticales, parallèles entres elles, aboutissent toutes à un point d’arrivée (voir figure A ci-dessous). Mais les barres verticales possèdent une particularitée. En effet chaque barre verticale peut être reliée de manière aléatoire à une barre horizontale, les “ghost legs”, qui sont évidemment masquées au début du jeu.
Pour jouer, le joueur doit choisir un point de départ, le chemin sera alors découvert, et le joueur devra suivre la barre verticale reliée aupoint choisi. Mais dès qu’il rencontrera une barre horizontale, il devra obligatoirement la suivre, et donc, changer de barre verticale. Arrivé au bout du chemin, il retombera forcement sur un des points d’arrivée qui peut correspondre à différentes choses tel qu’une somme d’argent, une équipe, ect…
Prenons l’exemple de la figure B ci dessous. Le joueur a choisi la lettre f, il suit alors le chemin, passe sur la colonne de gauche deux fois et se retrouve au niveau de la branche d. Ensuite il continu suivant le même principe jusqu’à l’arrivée. Il arrive finalement au niveau du chiffre 5. Un des couples représenté par ce diagramme est donc le couple (f:5).
Le but du problème Ghost legs est alors le suivant :
Creer un programme capable de calculer tout les couples d’un diagramme de type ghost legs. Afin de réaliser ce programme et de pouvoir le tester, le site Codingame nous fournit différents diagrammes de ce type, où les points de départ et d’arrivée peuvent être n’importe quel caractère de la table ASCII. Dans ces diagrammes les barres verticales sont représentées grace au caractère |, et les barres horizontales grace aux caractères – –.
Le site nous donne également deux autres variables en entrée, deux entiers représentant la taille en longueur et en hauteur du diagramme.
Afin de résoudre le problème Ghost legs j’ai voulu procéder de la manière suivante. Tout d’abord, il me fallait récupérer les informations données par Codingame. Puisque les variables définissant la hauteur et la longueure du diagramme étaient déja définies, et qu’une ligne de commande leurs étaient déja consacrée, il ne me restait plus qu’à récupérer le diagramme en lui même. J’ai donc décidé de stocker ce diagramme dans une liste. J’ai également voulu stocker à part la première et la dernière ligne du diagramme, celles contenant les noms des points de départ et d’arrivée, afin de pouvoir les stocker plus facilement.
Une fois toutes les informations de l’énoncé à ma disposition, il fallait créer le coeur du programme, les lignes de commandes qui allaient permettre de trouver les paires de variables. Mon raisonnement était le suivant, partir de chaque point de départ et essayer de retrouver, une à une les paires. Alors, pour chaque point de départ je voulais parcourir les lignes (ou étages) du diagramme une à une, et vérifier à chaque fois si le joueur devait changer de chemin.
Il y avait trois cas à distinguer :
Tout dabord, si le joueur se trouvait sur la première ligne verticale, il fallait uniquement vérifier si il n’y avait pas de Ghost legs (barres horizontales) à sa droite. Cela permettait d’éviter des opérations inutiles ou des erreurs dans le programme.
Ensuite, si le joueur se trouvait sur la dernière ligne verticale, il fallait uniquement vérifier qu’il n’y ai pas de Ghost legs à sa gauche. En effet cette distinction était selon moi utile pour les mêmes raisons que celles citées précedemment.
Enfin, il fallait s’occuper de tout les autres cas, c’est-à-dire les cas où le joueur se trouvait sur une des autres barres verticales. Il fallait alors vérifier qu’il n’y ai, ni de Ghost legs à sa gauche, ni de Ghost legs à sa droite.
Après avoir pris en compte, et distingué les cas précedents, le but était de trouver un moyen de détecter si il y avait une barre horizontale, et dans ce cas, changer de chemin en conséquence. Enfin, on répétait ce même raisonnement pour chaque ligne et chaque variable jusqu’à atteindre l’arrivée. Le programme affichait donc les différents couples (départ:arrivée).
Afin de mettre mon raisonnement en place, il me fallait coder. Tout d’abord, pour récupérer le diagramme j’ai choisi d’utiliser une liste de liste, afin de pouvoir rendre le reste du code plus simple. En effet les listes de listes sont facilement manipulables grace au système d’indice. J’ai donc créé une double boucle afin de créer cette liste de liste. Ensuite j’ai récupéré la première et dernière sous liste afin de les stocker dans des variables à part entière et de pouvoir les manipuler plus facilement lors de la création des couples de solutions.
La seconde étape consistait en la création d’une double boucle pour que mon programme se répete le nombre de fois voulu. La première boucle se répéte autant de fois qu’il y a de points de départ, et la seconde, imbriquée dans la première, se répète pour chaque ligne du programme. En même temps j’ai également initialisé une variable position, qui prenait comme valeur de départ l’indice du point de départ dans la liste, et qui allait être modifié à chaque répétition de la boucle consacrée aux lignes du diagramme. Cette variable est réinitialisée dès qu’un couple est trouvé.
Au moyen de conditions utilisées dans une instruction if (si, en français), j’ai pu distinguer les trois cas évoqués précedement. Et, à l’intérieur de ses instructions, selon le cas traité j’ai modifié la valeur de ma variable position (qui permet de retrouver le point d’arrivé).
Une fois toutes les lignes du diagramme parcourue, il ne me restait que deux opérations à faire. La première était de convertir la valeur obtenue de la variable position et de la faire correspondre au bon caractère d’arrivée. Pour cela il m’a suffit de prendre l’indice de valeur égale à position dans la liste des points d’arrivée, créé au début du programme. J’ai ensuite affiché le résultat obtenu. C’est-à-dire un des couples trouvé. Ces deux dernières opérations étant placées dans la boucle principale, elles se répétent donc pour chaque couple.
Afin d’avoir un meilleur aperçu de ce que fait mon programme, voici ci dessous une vesion en pseudo code de la boucle principale de ce dernier :
pour i allant de 0 au nombre de points de départ
si le point de départ n'est pas un espace, alors
la varible position vaut i
pour k allant de la première à la dernière ligne du diagramme
alors la ligne courante est égale à la ligne numéro k
si le joueur est sur la dernière ligne, alors
si il y a un tiret à gauche, alors
position vaut position moins 3
sinon si le joueur est sur la première ligne, alors
si il y a un tiret à droite, alors
position vaut position plus 3
sinon
si il y a un tiret à gauche, alors
position vaut position moins 3
sinon si il y a un tiret à droite
position vaut position plus 3Ci dessous, voici ma proposition de résolution de Ghost Legs en langage Python :
#importation des bibliothèques nécessaires à la réalisation du programme
import sys
import math
#definition de la hauteur et de la largeur du graphique
w, h = [int(i) for i in input().split()]
#creation d'une liste contenant chaque ligne du diagramme
liste_ligne=[]
for i in range(h):
ligne = input()
ligne2 = []
for j in range(len(ligne)):
ligne2.append(ligne[j])
liste_ligne.append(ligne2)
#creation d'une liste contenant chaques points de depart
ligne_depart = liste_ligne[0]
#creation d'une liste contenant chaques points d'arriver
ligne_arrivee = liste_ligne[-1]
# On cherche chaques points d'arrivée pour chaques points de départ
for i in range(len(ligne_depart)): # Boucle qui s'actionne en fonction du nombre de points de départs
if ligne_depart[i] != " ":
position = i # Initialisation de la position du point de départ
for k in range(1,h-1): # Boucle qui s'actionne en fonction du nombre de lignes
ligne_courante = liste_ligne[k]
if position == w-1: # Boucle consacrée au traitement de la dernière ligne du graphique
if ligne_courante[position-1] == "-":
position -= 3
elif position == 0: # Boucle consacrée au traitement de la première ligne du graphique
if ligne_courante[1] == "-":
position += 3
else: # Boucle consacrée au traitement des autres lignes du graphique
if ligne_courante[position-1] == "-":
position -= 3
elif ligne_courante[position+1] == "-":
position += 3
arrivee = ligne_arrivee[position] # Etape de conversion de l'indice numérique utilisé, au résultat symbolique attendu
print(ligne_depart[i]+arrivee) # Affichage du résutatNous allons maintenant nous intéresser à une autre solution au probème Ghost legs, réalisée par un autre utilisateur de la plateforme Codingame, Patricia. J’ai choisi de présenter sa solution car je la trouve très intéressante. En effet, elle est beaucoup plus compacte et courte que la mienne. Ainsi, elle nécessite moins de temps de code et moins de ressources pour l’executer. De plus elle est assez claire et ne donne pas lieu à des disjonctions de cas.
Après avoir discuté des avantages de cette solution par rapport à ma proposition, nous allons maintenant nous intérresser plus en détail à son fonctionnement. Tout dabord, le programme récupère les entrées fournies par Codingame. Il commence par stocker sous la forme d’une liste lines les différentes lignes du diagramme. Ensuite il crée une liste avec les différents points de départ, et la copie dans une autre variable.
Alors la boucle principale débute. Elle est executée autant de fois qu’il y a de lignes dans le diagramme, sans prendre en compte la ligne consacrée aux points de départ et celle consacrée aux points d’arrivée. Dans cette boucle, est imbriquée une autre boucle s’executant autant de fois qu’il y a de variables, moins une fois. Cette boucle est utile pour l’instruction d’après. En effet, l’instruction if se sert d’une variable i qui doit prendre un certain nombre de valeurs, donc la boucle précedente permet d’obtenir cette variable sans avoir d’erreur de dépassement d’indice. Cela peut arriver lorsque l’on travail avec des listes, d’où l’importance du -1 dans la ligne précedente.
La ligne 7 du programme permet donc de détecter où sont les tirets sur chaque ligne du diagramme, et lorsqu’il y a un tiret détecté, un mécanisme assez particulier se met en place. On change l’ordre des variables dans la liste order, contenant le nom des différents points de départ.
Prenons un exemple, celui de la figure B. Le programme détecte un trait horizontale entre a et b, alors il inverse la position de a et b dans la liste order. Il procède de la même manière pour toutes les lignes du programme, et on obtient donc une liste order totalement modifiée à la fin.
Enfin, une dernière boucle est utile pour l’affichage du résultat. Elle renvoie la concaténation de chaque point d’arrivée avec chaque élement de la liste order modifiée. Par exemple si on a les listes order=[B,A] et arrivée=[1,2], alors il affichera B1, A2.
C’est le mécanisme d’échange de colonne qui rend selon moi ce programme extrèmement intéressant. En effet, le créateur de ce programme a remarqué qu’il existait une méthode permettant d’obtenir tout les couples d’un coup. Contrairement à ma proposition, il n’y a pas besoin de répeter la boucle principale pour chaque variable (le programme ne calcul pas le couple A, puis le B, ect… mais modifie toute la liste d’un coup).
Si dessous, voici la proposition de résolution de Ghost Legs en langage Python par Patricia:
lines = [input() for i in range(int(input().split()[1]))] # Récupération des lignes du diagramme
names = lines[0].split() # Création de la liste des points de départ
order = [i for i in names] # Copie de names
for line in lines[1:-1]: # On parcourt les lignes de la deuxième à l'avant dernière
for i in range(len(names)-1):
if line[3 * i + 1] == "-": # Permet de détecter si il y a un tiret
order[i], order[i+1] = order[i+1], order[i] # Echange l'ordre des élements de order
for name in names: # On parcourt tout les elements de name
print(name + lines[-1].split()[order.index(name)]) # Affichage de la solutionPour conclure sur ce travail sur Ghost legs, il a été assez enrichissant. Il m’a appris à poser un problème sur papier avant de chercher une solution directement en codant. En effet, au début je ne savais pas comment m’y prendre et la distinction de différents cas m’a aidé à coder mon programme. De plus, ce travail m’a permis de découvrir un outil de travail utile pour progresser en programmation, Codingame.
J’ai également pu étudier les propositions d’autres personnes et me rendre compte qu’il existait un certain nombre d’approches différentes pour un même problème. Le travail de Patricia m’a beaucoup inspiré car il montre qu’en réflechissant aux différents mécanismes d’un problème, on pouvait obtenir une solution beaucoup plus propre et efficace, ce qui est notamment utile en entreprise lorsque l’on cherche à optimiser au maximum un code. Mais également lorsque l’on fait de la recherche complexe avec des moyens matériels limités. Il est alors important d’avoir le code le plus propre afin d’utiliser au mieux les ressources dont on dispose.