Revue de code des Top CodinGamers de The Last Crusade

STAY CONNECTED, FOLLOW CODINGAME NOW



Les gagnants de The Last CrusadeGangrene et NewbOo, reviennent sur leur code et nous expliquent comment ils ont procédé pour sauver la peau d'Indy.

NDRL: si certains d'entre vous souhaitent partager leurs revues de code avec la communauté CodinGame, n'hésitez pas à nous envoyer un lien vers vos debriefs  (issus de votre blog ou autre), on se fera un plaisir de relayer !


Le debrief de Gangrene :
(1ère place sur le podium | France | Python | 2:22:54)

Pour la première épreuve, j'ai stocké les différentes pièces sous la forme d'un tableau 8x3 (8 pièces, 3 entrées haut, gauche, droite).
Chaque case de ce tableau indique si une sortie existe, et le cas échéant le calcul à effectuer pour obtenir les nouvelles coordonnées.


Pour la première épreuve, il suffit donc de lire la case correspondante pour les coordonnées actuelles d'Indiana.

Pour la seconde épreuve, il faut à présent trouver un chemin qui n'existe pas encore.

Je décide de réaliser un parcours en profondeur.
Je me rends aussi loin que le chemin actuel me le permet.
Dès que j'atteins une pièce qui n'offre pas de sortie, je cherche si possible à la tourner, sinon je retourne en arrière. Bien entendu pour ne pas perdre de tours, je veille à tester d'abord la pièce sans la tourner, puis en la faisant pivoter d'un seul cran vers la droite ou la gauche, et enfin en la retournant complètement en dernier recours.
Je garde toujours en compte le nombre de tours d'avance dont je dispose pour atteindre cette pièce (nombre de tours de déplacement moins le nombre de pivots déjà effectués).

Lorsque la sortie est atteinte, je remonte le long de ma récursion en renvoyant en résultat le premier pivot effectué, et le nombre de tours dont je dispose avant de le faire.

Ce résultat est ensuite analysé.
Si je dispose de tours d'avance et que des rochers sont présents, je vais donc préférer m'occuper de ceux-ci.

A ce stade, l'épreuve est déjà commencée depuis deux heures, et je me dis qu'au vu des épreuves précédentes, les premières places sont déjà prises.
Je ne fais donc pas dans la dentelle.
Je teste les rochers dans l'ordre d'apparition. Pour chacun je calcule son chemin jusqu'à la première pièce pivotante. Si celle-ci offre une sortie, je la tourne pour bloquer la pierre (cela est possible en 1 coup quelle que soit la pièce et sa position), sinon je teste la pierre suivante.

Si toutes les pierres présentes sont déjà bloquées, je pivote la pièce obtenue précédemment pour libérer le passage d'Indiana.

Si aucune pièce n'est à bouger, plus qu'à WAIT, c'est gagné.

Mon code n'est pas parfait, et je m'en rends encore plus compte en l'analysant pour écrire ces lignes.
Par exemple, si une pièce doit être tournée d'un cran et la suivante de deux, ma fonction retournera que j'ai besoin d'un tour pour tourner la première pièce, alors qu'il m'en faudrait deux pour également commencer le mouvement de la pièce suivante.
Les cas proposés avec les rochers auraient pu être bien plus complexes, obligeant Indiana à suivre une route et pas une autre, piège dans lequel je serais tombé.


Une fois de plus, CodinGame nous aura présenté une belle épreuve, très complexe sur le papier, mais heureusement simplifiée par les cas proposés.

---

Le debrief de Newboo :
(2e place sur le podium | France | PHP | 2:34:57)

Autant l'avouer tout de suite, dans un premier temps j'étais un peu paumé. Contrairement aux éditions précédentes où le terrain de jeu était globalement fixe, il était ici variable et on n'avait pas la maîtrise du pauvre Indy, ce qui revient finalement à inverser les problèmes de recherche de chemin plus classiques. Heureusement, le premier exercice a tendance à mettre sur la bonne voie en nous apprenant à simuler le déplacement d'Indy (et du coup, des rochers aussi).


Définition de constantes
Avant de m'attaquer réellement à la résolution, j'ai commencé par une étape importante pour la suite, définir deux tableaux en lien avec les différents types de pièce :
- un premier pour donner le type de mouvement selon le type de pièce et le point d'entrée, qui peut se lire $moves[type de pièce][point d'entrée] = [delta x, delta y, point d'entrée dans la pièce suivante]
- un second pour les rotations des pièces, car tourner une pièce revenait en réalité à changer son type.


Recherche de chemin
Je me suis d'abord occupé uniquement des tests 1 à 5, laissant (presque) totalement de côté le cas des rochers. J'ai choisi de partir sur une recherche en profondeur, avec des optimisations pour avoir un minimum de branches à tester et donc la solution complète dès le premier tour. Pour résumer simplement, je me contente de simuler le déplacement d'Indy et à chaque nouvelle pièce je regarde ce qui lui permet de rester en vie :
- WAIT si tout va bien
- LEFT sur cette pièce
- RIGHT toujours sur cette pièce
- ou enfin un 180, par exemple deux fois RIGHT
Oui, tourner deux fois la pièce est possible, si jamais on a au moins un WAIT dans notre solution provisoire ! Au lieu de simplement ajouter une instruction, je transforme également un WAIT en une rotation, ce qui revient en quelque sorte à backtrack et explorer une autre branche de manière instantanée. À noter que je remplace le WAIT le plus "récent", de manière à disposer des autres WAIT le plus tôt possible pour m'occuper des rochers.


Les rochers
Il me restait donc maintenant à intégrer les rochers, sachant qu'ils ne sont pas tous là dès le premier tour. Profitant du fait que les cas avec rochers étaient vraiment gentils (je vous invite à regarder le niveau bonus pour vous en convaincre ^_^), je me suis contenté d'une solution vraiment minimaliste qui par chance fonctionne sur ces deux fameux tests 6 et 7. Je continue toujours de calculer la solution au premier tour, puis lorsque j'ai un WAIT à donner, je regarde s'il y a des rochers à éliminer. Pour éliminer un rocher, je simule son déplacement et je tourne la première pièce non verrouillée à gauche ou à droite si nécessaire (si ce n'est pas nécessaire, je peux m'occuper d'un autre rocher). Au tour suivant, je recalcule la solution pour Indy pour intégrer les éventuels changements sur son parcours initial.
Je ne me préoccupe donc absolument pas de savoir si un rocher va croiser ou non la route d'Indy, ni si l'un est plus prioritaire qu'un autre (me contentant d'éliminer le premier dans la liste), ni s'il ne vaudrait mieux pas tourner une pièce plus loin sur le chemin d'un rocher que la première possible. Mais, comme je l'ai dit, les cas étaient vraiment gentils et un algo aussi simpliste passait tout juste.


Le mot de la fin
J'ai vraiment été surpris de terminer 2ème avec un temps aussi "long" par rapport aux éditions précédentes, surtout avec du temps perdu bêtement sur mon parcours d'arbre dans lequel, à l'origine, je ne testais jamais les rotations si le WAIT fonctionnait... mais quelque soit le classement j'aurais de toute façon pris beaucoup de plaisir à sauver Indy. Merci à CodinGame pour les sujets toujours originaux (et le mode black de l'IDE ^_^).

1 commentaire :