1 Présentation du problème

Lien de l’exercice : https://www.codingame.com/training/easy/ghost-legs

Le jeu ghost legs est un jeu de loterie qui ce présente comme ceci :

Le jeu est constitué de lignes verticales et parallèles, ayant chacune un nom. Entre ces lignes, à l’horizontale, on trouve d’autres lignes qui relient les lignes verticales entre elles.

Le but du jeu est que le joueur choisisse une ligne verticale en haut du jeu et suive cette ligne vers le bas. Il faut cependant suivre la regle qui indique que si le joueur rencontre un ligne horizontale,à droite ou à gauche de sa ligne, il doit la suivre jusqu’à la ligne verticale suivante. Le joueur repete cette action jusqu’a ce qu’il arrive en bas du jeu.

Le but de l’algorithme est donc de predire pour chaque ligne verticale, à quelle fin de ligne verticale elle est connectée.

2 Description synoptique de la méthode de résolution et son détail algorithmique

2.1 Description synoptique

Le principe est assez simple, on parcourt une premiere fois le jeu pour enregistrer les connexions entre les lignes verticales. On parcourt ensuite les lignes verticales de haut en bas et on verifie si la ligne verticale est connectée a une autre ligne verticale, si oui, on change de ligne verticale.

2.2 Description algorithmique

1. L’algorithme commence en lisant la première ligne d’entrée qui contient la largeur et la hauteur du jeu. On enregistre la hauteur - 2 car on a pas besoin de la premiere et de la derniere ligne qui contiennent les labels.
2. On recupere les noms des entrées des lignes verticales dans une liste
3. On creer un dictionnaire vide qui contiendra les connexions entre les lignes verticales sous la forme (hauteur, ligneVerticale) : ligneVerticaleSuivante
4. On parcourt les lignes du haut vers le bas
   1. On initialise le numero de la ligne verticale a -1 car on va l’incrementer avant de l’utiliser
   2. On parcours les caracteres de la ligne, si le caractere est un tiret, on ajoute la connexion entre les deux lignes verticales dans les deux sens
5. On recupere les noms des sorties des lignes verticales dans une liste
6. On parcours les lignes verticales de haut en bas
   1. A chaque niveau, on verifie si la ligne verticale est connectée à une autre ligne verticale, si oui, on change de ligne verticale
7. On affiche le nom de la ligne verticale de depart et de la ligne verticale d’arrivé

3 Le code commenté de la résolution

height = int(input().split()[1]) - 2 # on retire 2 car on a pas besoin de la premiere et de la derniere ligne qui contiennent les labels
topLabels = input().split() # on recupere les noms des entrées des lignes verticales

connectors = {} # dictionnaire qui contient les connexions entre les lignes verticales sous la forme (hauteur, ligneVerticale) : ligneVerticaleSuivante
for lineNumber in range(height): # on parcours les lignes du haut vers le bas
    verticalLineNumber = -1 # on initialise le numero de la ligne verticale a -1 car on va l'incrementer avant de l'utiliser
    for char in input(): # on parcours les caracteres de la ligne
        if char == "-":
            # on ajoute la connexion entre les deux lignes verticales dans les deux sens
            connectors[(lineNumber, verticalLineNumber)] = verticalLineNumber + 1
            connectors[(lineNumber, verticalLineNumber + 1)] = verticalLineNumber
        elif char == "|":
            verticalLineNumber += 1

bottomLabels = input().split() # on recupere les noms sorties des lignes verticales

for lineId, lineLabel in enumerate(topLabels): # pour chaque debut de ligne verticale
    for i in range(height):  # on parcours les lignes du haut vers le bas
        if (i, lineId) in connectors.keys(): # si la ligne verticale est connecté a une autre ligne verticale
            lineId = connectors[(i, lineId)] # on change de ligne verticale
    print(lineLabel + bottomLabels[lineId]) # on affiche le nom de la ligne verticale de depart et de la ligne verticale d'arrivé

4 Analyse des résultats

Le code fonctionne comme prévu, il passe tous les tests. On peut cependant ameliorer le code, en effet lors du premier balayage du jeu, on enregistre les connexions entre les lignes verticales ainsi dans l’exemple suivant :

A  B  C
|  |  |
|--|  |
|  |--|
|  |--|
|  |  |
1  2  3

lors du parcours, la troisieme ligne est la suivante : |–| | et lors de la boucle la correspondance du caractère “-” se fera deux fois pour une meme connexion puisqu’il y a deux tirets pour une meme connexion. Cela ne pose cependant pas de probleme puisque les dictionnaires ecrasent les valeurs similaires.

5 Description d’une solution différente

Solution de Danyosate:

https://www.codingame.com/training/easy/ghost-legs/solution?id=13774112

w, h = [int(i) for i in input().split()]
words = input().split()
order = [i for i in range(len(words))]

for i in range(h - 2):
    line = [int(j) for j in input().replace('  ', '0').replace('--', '1').split('|')[1:-1]]
    for j, v in enumerate(line):
        if v:
            order[j], order[j+1] = order[j+1], order[j]
nums = input().split()

for i, v in enumerate(words):
    print(v, nums[order.index(i)], sep='')

Cette solution est interressante puiqu’elle parcourt toutes les lignes en meme temps, elle est donc plus rapide que la mienne. Elle utilise une liste qui contient les numeros des lignes verticales. Elle parcourt ensuite les lignes et lorsqu’elle rencontre un tiret, elle inverse les deux valeurs de la liste. A la fin, elle parcourt la liste des noms des lignes verticales et affiche le nom de la ligne verticale de depart et de la ligne verticale d’arrivé. Cette solution est donc plus efficace puisqu’elle ne parcourt qu’une seule fois le jeu.

Cependant, cette solution est moins lisible car elle multiplie les actions dans une seul ligne de code et utlise des comprehensions de liste pour parcourir les lignes.

6 Bilan

Cette exercice ma permis de revoire les dictionnaires et la fonction enumerate() qui permet de parcourir une liste en recuperant l’index et la valeur de l’élément courant.