Ghost Legs

Introduction

Ghost Legs est un jeu de lotterie commun en Asie. On retrouve un diagramme comme celui-dessous. On choisit un element en haut. Ici un element parmis Sandwich, Tacos, Pizza, Korean BBQ. On suit la ligne verticale associée à l’élément et, dès que l’on croise un connecteur on doit le prendre et aison continuer. Ansi chaque élément du haut est associé à un unique élément du bas. Les pairs de ce diagramme sont: (sandwich-dinner,Tacos-lunch,Pizza-No,Korean BBQ-NO). Le but du problème est de déterminer chaque pair pour toute taille et élément du diagramme. En entrée il y la hauteur et la largeur du diagramme. Il y a aussi le diagramme écrit ligne par ligne. La première ligne correspont au élément du haut et la dernière les elementrs du bas.

Description de ma méthode de résolution

Synopsis

Lorsque un élément du haut croise un connecteur il est obligé de le prendre. Il advient donc que chaque élément du haut est associé à un unique élément du bas. J’ai donc décidé d’associer d’abord chaque élément du haut avec celui du bas dans une liste de liste sans me soucier des connecteurs. Puis je parcours le diagramme afin de trouver les connecteurs pour modifier ma liste afin d’intervertir les bons élements. ### Description algorithmique

Exemple d'entrée :
7 7
A  B  C
|  |  |
|--|  |
|  |--|
|  |--|
|  |  |
1  2  3

Tout d’abord j’initialise deux liste vides, diagramme qui récuperera le diagramme et associe qui stockera les labels haut et bas associe sous forme de liste. Je récupère la largeur et hauteur du diagramme dans les variables h et w. Ensuite je récupère les chaines de caractères pour chaque ligne dans la variable diagramme. Grâce à la fonction replace j’enlève les espaces contenu dans la première et dernière ligne pour associer plus simplement chaque élément du haut et du bas. J’associe ensuite ces elements afin de les mettre dans la variable associe. A cette étape associe vaut [[A,1][B,2][C,3]] avec l’exemple d’entrée. Ensuite j’étudie les connecteurs du diagramme, pour cela je boucle avec i qui va de 1 à la longueur de la variable diagramme moins un. Diagramme[i] correspondra donc à une ligne du diagramme différente de la première et de la dernière. J’initialise une variable connecteur_i=0 qui me permettra de savoir entre quelle ligne k se situe car ensuite je boucle avec k qui va de 0 à la longueur de diagramme[1] qui correspond à la longueur d’une ligne du diagramme. Je test si k se situe entre deux pipe et j’observe si le caractère ‘-’ apparait. Si oui, il y a donc un connecteur donc j’interverti ce qu’il faut dans associe. J’obtient donc à la fin des deux boucles associe qui detient les pairs du diagramme. Or ces pairs ne sont pas dans l’ordre donc je boucle sur chaque élément de diagramme[0] pour les écrire dans l’ordre.

Code commentée

import sys
import math

def main():
    diagramme=[]                                # Liste stockant ligne par ligne le diagramme
    associe=[]                                  # Liste qui associe chaque label du haut avec celui en bas
    w, h = [int(i) for i in input().split()]
    for i in range(h):
        line = input()
        diagramme.append(line)
    diagramme[0]=diagramme[0].replace(" ","")           # Suppression d'espace inutiles pour les label du haut et du bas
    diagramme[h-1]=diagramme[h-1].replace(" ","")           # Same
    for k in range(len(diagramme[0])):
        associe.append([diagramme[0][k],diagramme[h-1][k]])           # Association du label du haut avec celui du bas
    for i in range(1,len(diagramme)-1):                                # Boucle sur chaque ligne du diagramme sauf première et dernière
        connecteur_i=0                                          # Initialisation de la variable connecteur_i qui permet de savoir à quel connecteur on se situe(même si ce connecteur n'existe pas)
        for k in range(len(diagramme[1])):                      # Boucle sur chaque caractère d'une ligne
            if (k%3==1):                                        # On place k entre chaque pipe pour voir si il y a le caractère "-"
                if (diagramme[i][k]=="-"):                      # Si oui on change donc l'association entre label haut et bas des lignes connectés
                    temp=associe[connecteur_i][1]
                    associe[connecteur_i][1]=associe[connecteur_i+1][1]
                    associe[connecteur_i+1][1]=temp

                    temp_2=associe[connecteur_i]                   # intervertion de la position dans la liste 'associe' des elements qu'on a interverti
                    associe[connecteur_i]=associe[connecteur_i+1]
                    associe[connecteur_i+1]=temp_2
                connecteur_i+=1
    for k in range(len(diagramme[0])):
        bool=True
        m=0
        while bool:
            if diagramme[0][k]==associe[m][0]:
                print(associe[m][0]+associe[m][1])
                bool=False
            m+=1                                            # J'ai interverti la position des elements de 'associe', il faut donc les remmettre dans l'ordre pour les afficher
main()

Tout les tests de codingame ont été validées.

Description d’une solution différente.

C’est un code que j’ai trouvé très intérressant car il est très court mais n’utilise pas plus en mémoire et en temps que le mien. Contrairement à mon code, celui-ci boucle sur chaque label du haut. Pour chaque label il va donc tester si il n’y a pas de connecteurs adjacents si oui il se déplacera en fonction sinon il descendra. Puis dès qu’il atteindra le bas il écrira le label du haut associe à celui du bas. Le code est donc simple à comprendre, il utilise la méthode que l’homme choisirait pour résoudre le problème de tête. De plus il n’y a pas trop de variable, celle-ci sont simple à comprendre.

w, h = [int(i) for i in input().split()]
board = [input() for _ in range(h)]

for cur_col in range(0, w, 3):  # starting leg
    start = board[0][cur_col]
    
    for row in board[1:-1]:  # iterate through board and follow horizontal connectors
        if cur_col > 0 and row[cur_col - 1] == "-":
            cur_col -= 3
        elif cur_col < w - 1 and row[cur_col + 1] == "-":
            cur_col += 3
    
    print(f"{start}{board[-1][cur_col]}")

Avis sur mon code + apprentissage

• Points positifs:
  1. Je ne parcours qu’une seule fois le diagramme, il est donc rapide à éxecuter.
  2. Nom de variable assez simple à comprendre
• Points négartifs:
  1. Pas d’utilisation de fonction, lors de l’échange dans la liste associe j’aurais pu utiliser des fonctions pour que le code soit plus lisible et donc plus compréhensible.
  2. Indice parfois peu compréhensible
  3. Trop de variable au vue de la solution différente

J’ai compris qu’il fallait d’abord écrire un algorithme sur papier pour pouvoir l’optimiser dès le début, la difficulté n’est pas tant dans la solution mais dans l’optimisation en temps et en mémoire du code. Mon code comporte 13 variables et la solution différente uniquement 5. L’utilisation de fonction aurait été plus judicieux dans certins cas.