Rapport sur Ghost legs

Par Benoit DAJOUX

groupe MI7 / Prep’Isima

Année 2022/2023

Introduction

Le Ghost Legs est une sorte de jeux de Loterie en Asie, Il commence avec des lignes verticales ‘|’ qui sont toute relié a une entrée A,B,C,… Notre “bille” descend le long des lignes verticales mais dès qu’elle rencontre une ligne horizontale ‘–’, elle change de ligne verticale, les lignes horizontales sont comme un pont que la bille est obligés de traverser. La bille fait cela jusqu’a arriver tout en bas ou elle tombe sur une sortie 1,2,3,…

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

voici l’exemple du diagramme donné sur codingame qui nous fait comprendre réellement comment ce jeux fonctionne.
Le but de l’exercice est de coder ce jeux en python sur la plateforme codingame, en utilisant la base de code fourni et en le complétant pour qu’il fonctionne.

Code personnel

Pour résoudre le problème posé je suis parties sur une méthode à triple boucle bornée:
* Une boucle pour parcourir toute les lignes du diagramme
* Une deuxième boucle pour parcourir chaque éléments de la ligne à laquelle on avait enlever les ‘|’
* Une troisième boucle pour appliquer le changements a chaque bille utiliser (1 par entrées pour les tests)
le but étant qu’à chaque fois qu’on change de ligne, toute les billes ai potentiellement pu changer d’indice, ce qui permet de ne pas relancer les 2 premières boucles pour chaque bille qui utilise 1 entrée. Cela permet d’éviter d’augmenter la complexité du programme qui pourrait devenir très grande lorsqu’on a beaucoup de billes.

import sys
import math

#récupération de la largeur et la hauteur
w, h = [int(i) for i in input().split()]

#récupération des entrées ainsi que de leurs indices
T = input().split('  ')
Tindice=[i for i in range(len(T))]

#parcours des billes dans la diagramme

#on parcours chaque ligne une par une
for i in range(h-2): 

    #on récupère la valeur d'une ligne
    line = input().split('|')

    #on parcours chaque éléments de la ligne
    for j in range(len(line)):

        if line[j]=='--':

            #on fait le changements pour toute les billes lancées
            for k in range(len(Tindice)):
                #
                if Tindice[k]==j-1:
                    Tindice[k]+=1

                elif Tindice[k]==j:
                    Tindice[k]-=1

#récupération des sorties
B = input().split('  ')

#affichage des couples entrée/sortie qui correspondent
for i in range(len(T)):
    print(T[i]+B[Tindice[i]]) 

voici le code éxécuté pour trouver les bonnes réponses, pour le diagramme déjà vu plus haut,

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

les sorties consoles donnent “A2”, “B1”, “C3”, qui sont effectivement les bonnes réponses si l’ont fait le jeux à la main en utilisant le diagramme bien dessiné.

description d’une solution différente

import sys
import math


class VLine:
    def __init__(self, letter):
        self.letter = letter
        self.number = None
        self.legs = list()
        
        
w, h = [int(i) for i in input().split()]
vlines = [VLine(l) for l in input().split()]

for _ in range(1, h-1):
    i = 0
    for leg in input().split():
        if leg == '|':
            vlines[i].legs.append(0)
        elif leg == '|--|':
            vlines[i].legs.append(1)
            vlines[i+1].legs.append(-1)
            i += 1
        i += 1
        
i = 0
for n in input().split():
    vlines[i].number = n
    i += 1
        
for i in range(len(vlines)):
    k = i
    vline = vlines[k]
    for j in range(h-2):
        k += vline.legs[j]
        vline = vlines[k]
    print(f'{vlines[i].letter}{vline.number}') 

J’ai choisi de parler du code de redCroc car je trouve cela interessant qu’il est décider d’utiliser la programmation orienté objet afin de réussir ce problème, il a su avoir une approche différente de la plupart des dévellopeurs.
Il définie une classe Vline avec 3 attributs de classe: letter, number et legs, ou letter représente l’entrée (A,B,C,…), number représente la sortie (1,2,3,…), et legs représente une liste ou il rapporte chaque action, s’il change de colonne ou pas avec des 0, 1, et -1. Il définie une liste vlines ou chaque élément de la liste est un objet de la classe Vline. Il a en plus grace a l’attribut legs, le détail de tout les changement qu’une bille fait, il peut savoir exactement lorsqu’une bille change de colonne, et a quelle ligne cela se passe, et ce pour chaque bille. Il utilise ensuite la la liste contenue dans l’attribut legs pour trouver l’indice de sortie.
Sa méthode n’est pas la plus efficace mais c’est une méthode différente qui montre qu’on peut toujours faire d’une autre manière