Introduction au puzzle
Ghost leg, ou amidakuji est une sorte de jeu de lotterie populaire en Asie. Il permet d'associer une valeur à une autre, permettant de répartir des objets parmi un groupe de personne, créer des équipes ou bien de savoir quel plat manger pour quel repas. Le principe du jeu est simple à comprendre. Le jeu commence par une séquence de valeurs (chiffres, noms, objets). Chaque valeur est reliée en ligne droite verticale à une valeur d'une deuxième séquence, située plus bas. Les valeurs sont donc reliées par des tubes. Cependant, chaque ligne verticale peut être reliée à une autre par une ou plusieures lignes horizontales, donc un autre tube, créant un lien. Une partie débute à la première valeur de la première séquence. Il suffit ensuite de longer le tube correspondant à cette valeur jusqu'à tomber sur un tube horizontal, qu'il faut emprunter afin de changer de tube vertical, il suffit de répéter ce procédé jusqu'à atteindre un valeur de la deuxième séquence, maintenant associée à la première valeur de la première séquence. Répéter cela pour toutes les valeurs de la première séquence pour associer toutes les valeurs. Une partie peut ainsi ressembler à la suivante :
Le problème python à traiter est donc de créer un programme qui puisse automatiquement, selon une grille donnée, associer les valeurs des deux séquences. Cela revient à créer une sorte d'intelligence artificielle jouant à la place d'un humain.
Les données auxquelles nous disposons sont donc :
- h et w, respectivement la hauteur et la largeur de la grille (sachant qu'un tube horizontal possède une largeur 2 dans cette grille)
- h lignes où la première et dernière représentent les première et deuxième séquences et les autres les tubes verticaux et horizontaux.
Une précision est apportée pour ce problème : un tube vertical ne peut être relié, à un même niveau, qu'à un seul tube horizontal. Autrement dit, la situation : --|-- ne peut pas se produire.
Les données à renvoyer sont donc :
- L'association des valeurs des deux séquences après une partie, en commençant par la valeur de la première séquence et en séparant chaque association par un retour à la ligne.
Résolution du puzzle
Résumé de la méthode
On peut facilement transformer la grille en une matrice, pour une compréhension plus facile pour un humain. En python, cela peut se réaliser avec une liste de listes, où chaque élément est soit une valeur d'une des deux séquence, un tube vertical ou horizontal, ou un espace vide (ce dernier ne sera cependant pas pris en compte par l'algorithme). On peut ainsi, pour chaque valeur de la première séquence parcourir le chemin "traditionnel" en regardant les cases adjacentes de la grille.
Transposition en Python
La matrice, comme dit précédemment est créée à partir d'une liste de listes.
On créé donc une liste vide, qui va contenir les autres listes.
On initialise les variables de réponses et deux listes contenant les valeurs des première et deuxième séquences
Dans la boucle des entrées de valeurs(celles permettant de donner chaque ligne), on sauvegarde chaque caractère de la chaîne d'entrée et les dispose sur la ligne de notre grille correspondant à l'itération de la boucle, et on ajoute les valeurs des première ou deuxième séquences si l'on se trouve sur la prmière ou dernière ligne.
Pour chaque tour, la méthode est la suivante :
- Commencer à la valeur de la première séquence en y plaçant un "curseur",
- Si un tube horizontal se trouve à droite ou à gauche du curseur, déplacer le curseur le long de ce tube,
- Faire descendre le curseur,
- Ajouter la valeur de la première séquence suivie de la valeur de la deuxième séquence et d'un caractère de retour à la ligne dans la chaîne de caractères de réponse.
Code python de la résolution
map = []
answer = ""
top = []
bot = []
ghost = 0
Nous commençons par initialiser les variables, respectivement la matrice qui nous servira de grille, la chaîne de caractère de réponse, la liste contenant les valeurs de la première séquence, la liste des valeurs de la deuxième séquence et notre curseur
for i in range(h):
map.append([])
line = input()
for j in range(len(line)):
if (i == 0) and ((j+1)%3 == 1):
top.append(line[j])
elif (i == h-1) and ((j+1)%3 == 1):
bot.append(line[j])
map[i].append(line[j])
L'instruction map.append([]) ajoute une ligne dans notre grille.
On ajoute ensuite, selon si la ligne donnée par l'utilisateur est la première ou dernière, les valeurs des séquences dans les listes correspondantes, tout en prenant en compte que les valeurs sont espacées entre elles de trois cases. On ajoute dans tous les cas chaque caractère de la ligne entrée dans notre grille à la ligne correspondante.
for i in range(len(top)):
ghost = 3*i
for j in range(1, h, 1):
if ghost != 0 and map[j][ghost-1] == '-':
ghost -= 3
elif ghost != w-1 and map[j][ghost+1] == '-':
ghost += 3
answer += str(top[i]) + str(bot[ghost//3]) + '\n'
answer = answer[:-1]
Pour chaque valeur de la première séquence, le curseur se place à la première ligne (après celle des valeurs de la première séquence) de la colonne correspondante. Il descend ensuite de h-2 (La hauteur moins deux) cases.
S'il croise, à gauche ou à droite, un tube horizontal, il l'emprunte (sachant qu'un tube horizontal a une longueur de trois cases)
À la fin de la boucle, le curseur étant arrivé sur une valeur (celle de la deuxième séquence), on ajoute à la chaîne de caractères réponse la valeur sur laquelle le curseur a commencé, suivie de la valeur sur laquelle le curseur a fini son parcours, et d'un retour à la ligne.
Avant de soumettre le résultat (la chaîne de caractères réponse), on retire le dernier caractère de la chaîne, c'est-à-dire un retour à la ligne. Cela évitera les bugs indésirables.
Comparaison avec un autre Codingamer
Le code donné par l'utilisateur m3m0ry sur Codingame propose une solution différente du parcours classique de la grille.
En effet, au lieu de faire descendre un curseur à la fois, tous seront descendu en même temps et deux curseurs échangront leur place à la rencontre d'un tube horizontal.
Cette stratégie s'appuie sur le prédicat qui dit que la situation : --|-- ne puisse pas se produire, ce qui permet d'échanger les positions de deux curseurs
La réponse commencera par le point de départ du curseur, soit sa valeur correspondante, suivi par son point d'arrivé, soit la valeur sur laquelle il se trouve.
top = input().split()
original = top.copy()
legs = []
for i in range(h-2):
i = 0
line = input()
for leg in line.split():
if '-' in leg:
tmp = top[i]
top[i] = top[i+1]
top[i+1] = tmp
i += 2
else:
i += 1
bottom = input().split()
for a in original:
print(f'{a}{bottom[top.index(a)]}')
La stratégie de faire descendre tous les curseurs en même temps est intéressante, car elle permet un gain de temps pour un joueur humain.
Un autre détail attirant particulièrement l'attention est le fait de s'approprier le fonctionnement de codingame. En effet les inputs des différentes lignes sont dispersés pour, dans un premier temps créer la liste top, parcourir la grille en second lieu, et enfin créer la liste bot.
En temps normal les inputs des lignes se font dans une boucle, sans être séparés, (cf le code vu plus haut)
Bilan
Ce puzzle développe la réflexion sur la transformation d'un travail humain en algorithme, puis en un programme. Cela permet d'exprimer explicitement sa stratégie personnelle pour un tel jeu. Ce puzzle peut constituer une sorte introduction à la création d'intelligence artificielle non-générative capables de réaliser certaines missions, pour des jeux ou situations réelles.