Indiana - Episode 1 – solution CodinGame en Python
On lit la grille des types de salle une fois, puis à chaque tour on consulte où Indy quitte la salle courante selon son type et le côté par lequel il est entré (TOP, LEFT ou RIGHT). Les sorties sont toujours DOWN, LEFT ou RIGHT, donc la salle suivante est (x, y+1), (x-1, y) ou (x+1, y), et on affiche ces coordonnées. Une petite table de (type, entrée) vers sortie remplace toute recherche de chemin : O(1) par tour.
L'énoncé
Le tunnel est une grille de W × H salles (jusqu'à 20 × 20), chacune d'un type de 0 à 13 décrivant les ouvertures qu'elle relie. Indy part du haut et tombe de salle en salle ; dans l'Episode 1, la disposition est fixe et garantit de le mener à la sortie en bas.
À chaque tour, on reçoit la salle courante d'Indy x, y et le côté par lequel il y est entré. Il faut afficher les coordonnées de la salle où il se trouvera au tour suivant. La colonne de sortie est fournie mais inutile, puisque les salles y mènent déjà.
La démarche, étape par étape
- Stocker la grille en entiersOn lit H lignes de W nombres séparés par des espaces et on les indexe grid[y][x]. Les types de salle sont ici de simples entiers ; les types négatifs (non pivotables) n'apparaissent que dans les épisodes suivants.
- Encoder les 14 types de salle une fois pour toutesPour chaque type, on liste où Indy sort selon le côté d'entrée : par exemple le type 4 envoie TOP vers la gauche et RIGHT vers le bas, le type 5 envoie TOP vers la droite et LEFT vers le bas, et les types 10 et 11 envoient TOP respectivement à gauche et à droite. Les types 1, 3, 7, 8, 9, 12 et 13 sortent toujours vers le bas pour toute entrée valide, et les types 2 et 6 se déplacent horizontalement à l'opposé du côté d'entrée.
- Convertir la sortie en coordonnéesDOWN signifie y+1, LEFT signifie x-1, RIGHT signifie x+1. Indy ne remonte jamais, donc il n'y a pas de cas y-1.
- Répondre à chaque tourOn lit l'entrée du tour dans une boucle infinie et on affiche « x y ». Il n'y a aucun état à conserver entre les tours, car l'entrée dit déjà tout.
Complexité
O(1) per turnO(W·H)Chaque tour est une simple consultation de table. La seule mémoire est la grille elle-même.
Code de la solution
Indiana - Episode 1 – Python
Utilise une chaîne de tests if/elif sur le type de salle regroupés par comportement, ce qui est compact puisque beaucoup de types sortent toujours vers le bas. Un dictionnaire indexé par (type, entrée) rendrait chaque règle explicite et serait plus facile à réutiliser dans l'Episode 2.
W, H = [int(i) for i in input().split()]
rooms = []
for i in range(H):
rooms.append([int(i) for i in input().split()])
exit = int(input())
while 1:
XI, YI, POS = input().split()
XI, YI = int(XI), int(YI)
if rooms[YI][XI] in (1, 3, 7, 8, 9, 12, 13):
YI+=1
elif rooms[YI][XI] in (2, 6):
XI+= 1 if POS == 'LEFT' else -1
elif rooms[YI][XI] == 4:
if POS == 'TOP':
XI-=1
else:
YI+=1
elif rooms[YI][XI] == 5:
if POS == 'TOP':
XI+=1
else:
YI+=1
elif rooms[YI][XI] == 10:
XI-=1
elif rooms[YI][XI] == 11:
XI+=1
print("{} {}".format(XI, YI))
Erreurs fréquentes
- Confondre le côté d'entrée et la direction du déplacementPOS est le côté par lequel Indy est entré, pas celui vers lequel il va. Entrer dans un type 2 par la gauche (LEFT) signifie qu'il va vers la droite (RIGHT), donc x+1.
- Mélanger les types 4 et 5Ce sont des images miroir. Dans le type 4, l'ouverture TOP mène à LEFT et l'ouverture RIGHT mène à DOWN ; dans le type 5, TOP mène à RIGHT et LEFT mène à DOWN. Les intervertir échoue dès qu'un test en utilise un.
- Lire les lignes comme des chaînes de chiffres isolésLes types 10 à 13 ont deux chiffres, donc découper une ligne caractère par caractère casse. Il faut découper sur les espaces.
- Chercher un cheminL'Episode 1 ne demande aucune recherche : le trajet est fixe et on ne prédit qu'un seul pas. Un BFS ou une récursion ajoute des bugs sans rien apporter.
Pour aller plus loin
Encoder les salles sous forme de dictionnaire, par exemple {(4, 'TOP'): 'LEFT', (4, 'RIGHT'): 'DOWN', ...}, est plus qu'une question de style : dans Indiana - Episode 2 et 3, il faut faire pivoter des salles et simuler Indy et les rochers plusieurs pas à l'avance, et chacune de ces simulations a besoin exactement de la même fonction « type plus entrée donne sortie ». Les rotations s'y greffent aussi très naturellement, car faire pivoter une salle ne change que son numéro de type (2 et 3 s'échangent, 4 et 5 s'échangent, 6 à 9 tournent entre eux, de même que 10 à 13). Si vous écrivez proprement la table des sorties et la table des rotations dès maintenant, l'Episode 2 devient une recherche sur les rotations bâtie sur du code déjà validé.
Questions fréquentes
A-t-on besoin de la coordonnée de sortie EX ?
Pas dans l'Episode 1. Les salles sont disposées de sorte qu'en les suivant on arrive à la sortie, et on ne prédit que la salle suivante.
Indy peut-il entrer dans une salle par le bas ?
Non. L'entrée est toujours TOP, LEFT ou RIGHT et il ne remonte jamais, c'est pourquoi toute sortie est DOWN, LEFT ou RIGHT.
Et le type 0 ?
Le type 0 est un bloc plein. Indy n'y entre jamais dans un niveau valide de l'Episode 1, donc il n'a besoin d'aucune règle.