I- Présentation du problème
A) Les entrées
Le programme prend comme entrée deux entiers w et h représentant la taille du diagramme qui va suivre. Ensuite, il reçoit w lignes de h caractères.
B) Le but du jeu
Ghost Legs est un jeu de loterie courant en Asie. Il commence par un certain nombre de lignes verticales. Entre les lignes se trouvent des connecteurs horizontaux aléatoires reliant toutes les lignes dans un diagramme connecté, comme celui ci-dessous.
Pour jouer, un joueur choisit une ligne en haut et la suit vers le bas. Lorsqu'il rencontre un connecteur horizontal, à gauche ou à droite, il doit suivre le connecteur pour se tourner vers une autre ligne verticale et continuer vers le bas. Répétez cette opération jusqu'à atteindre le bas du diagramme.
Dans l'exemple de diagramme, lorsque vous démarrez à partir de A, vous vous retrouverez en 2. En commençant par B, vous vous retrouverez en 1. En commençant par C, vous vous retrouverez en 3. Il est garanti que chaque étiquette supérieure correspondra à une étiquette inférieure unique.
C) La sortie
Étant donné un diagramme Ghost Legs, découvrez quelle étiquette supérieure est connectée à quelle étiquette inférieure. Répertoriez toutes les paires connectées.
II- Ma méthode de résolution
A) Approche synoptique
Pour résoudre ce problème, il fallait que je m'adapte au fait que le programme envoyait à chaque itération une seule ligne. Par exemple au début il nous envoie une chaîne de caractère contenant les entrées. Pour expliquer simplement mon programme, je suis parti du fait que s'il n'y avait pas de connecteur horizontal, tout reste dans la normale. Mais s'il y en avait un ou plus, j'inversais les entrées de part et d'autre du connecteur. À la fin, j'associe l'ordre des entrées obtenues avec les sorties pour pouvoir écrire les couples entrées sorties.
B) Appproche algorithmique et explication de mon programme
import math
w, h = [int(i) for i in input().split()]
for i in range(h):
line = input()
if i==0:
liste_entree = list(line.replace(" ",""))
liste_en_cours = list(liste_entree)
liste_sortie = list()
if i==(h-1):
liste_sortie = list(line.replace(" ",""))
position_finale_des_entrees = list()
for i in range(len(liste_en_cours)):
position_finale_des_entrees.append(liste_en_cours.index(liste_entree[i]))
a = 0
for position in position_finale_des_entrees:
print(liste_entree[a]+liste_sortie[position])
a += 1
else:
position_tiret_h = int()
position_caractere_a_inverser = list()
while '--' in line:
position_tiret_h = line.index('-')
position_caractere_a_inverser.append(position_tiret_h-1)
position_caractere_a_inverser.append(position_tiret_h+2)
debut_ligne=line[:position_tiret_h+2]
fin_ligne=line[position_tiret_h+2:]
debut_ligne=debut_ligne.replace("-"," ")
line=debut_ligne+fin_ligne
liste_en_cours[position_caractere_a_inverser[0]//3] , liste_en_cours[position_caractere_a_inverser[1]//3] = liste_en_cours[position_caractere_a_inverser[1]//3] , liste_en_cours[position_caractere_a_inverser[0]//3]
position_caractere_a_inverser = list()
Mon programme se base donc sur une boucle for qui itère sur le nombre de ligne en entrée. Je stocke ensuite la ligne que je recois à chaque itération dans une variable line. Mon programme va ensuite se décomposer en trois partie. Une correspondante à la première itération, une pour la dernière puis celle concernant toute les itérations intermédiaires. On s'intéresse d'abord à la condition ou i=0 soit la première itération:
Je crée une liste "liste_entree" qui gardera tout au long du programme les entrées dans l'ordre, puis j'initialise la liste "liste_en_cours" avec la liste précédente. J'initialise aussi une liste "liste_sortie" qui nous servira à la fin.
Maintenant, nous allons étudier la condition générale correspondant au else puis nous reviendrons sur la condition i=h-1 à la fin pour faire dans le même ordre que lors de l'exécution. J'initialise une variable "position_tiret_h" puis une liste "position_caractere_a_inverser", puis j'entre dans un while s'il y a un double tiret dans la ligne actuelle. Si il n'y en a pas, on continu à l'itération suivante avec le même ordre pour les entrées sinon, on rentre dans la boucle while qui va d'abord stocker la position du premier tiret horizontale puis qui va ajouter à la liste les 2 caractères ui sont de part et d'autres. Je supprimer dans la ligne les deux premiers tirets puis j'inverse dans la liste "liste_en_cours" les deux caractères. Pour finir je supprimer ce que contenait la liste "position_caractere_a_inverser".
Désormais, il faut sortir du for et retourner les couples entrées/sorties à la dernière itération. Pour cela, on va rentrer dans le deuxième if où on va d'abord trasnformer en liste sans espace les caractères de sorties dans la liste "liste_sortie". On initialise ensuite une liste "position_finale_des_entrees". La boucle for permet ensuite de remplir cette liste avec la nouvelle position des caractères d'entrées. Par exemple, le premier chiffre corrrespondera à la nouvelle position du premier caractère qui était la première entrée au début du programme, et ainsi de suite. Puis on initialise une variable a qui servira d'indice pour la boucle for. A l'intérieur de cette dernière, on affiche la première entrée du début avec la sortie dont l'indice corespond à la position du caractère d'entrée lors de l'avant dernière itération(Dernier moment possible pour inverser des caractères).
III- Un autre programme
import math
w, h = [int(i) for i in input().split()]
graph = []
for i in range(h):
line = input()
graph.append(" " + line + " ")
for i in range(1, len(graph[0]), 3):
letter = (graph[0][i])
y = 1
while y != len(graph) - 1:
if graph[y][i-1] == "-":
i -= 3
elif graph[y][i+1] == "-":
i += 3
y += 1
print(letter + graph[y][i])
Ce programme est différent du mien car il traite le cas de chaque lettre une par une, et non comme moi toutes les lettres en même temps ligne par ligne. Il y a d'abord une première boucle of rqui enregistre chaque ligne dans une liste, puis dans sa seconde boucle for, il va gérer chaque lettre une après l'autre. Il parcourt donc chaque ligne présent dans la liste puis il regarde où sont les tirets pa rapport à la lettre actuelle pour enregistrer la nouvelle position de la lettre s'il y a des tirets, sinon il garde l'ancienne position. Lorsque qu'il sort du while imbriquée dans la deuxième for, il affiche la première entrée associé à sa sortie, puis il va traiter la lettre suivante et ainsi de suite.
IV- Bilan / Retour d'expérience
Je n'ai pas réellement appris de chose nouvelle, néanmoins j'ai revu deux choses que je ne me suis jamais vraiment servi ou sinon très rapidement, dans mon programme, cela je parle du fait d'inverser deux valeurs dans une liste en ne la parcourant pas, juste en se servant des indices des deux valeurs. Tandis que dans le code d'un autre codeur, j'ai revu le principe d'aller "chercher" un caractère contenu dans une liste de liste avec les doubles crochets de suite.