Revue de code des Top CodinGamers de Kirk's Quest

STAY CONNECTED, FOLLOW CODINGAME NOW

cup_of_tea (1er au classement) et redvasily (2e) partagent avec nous leur revue de code pour Kirk's Quest. Merci à tous les 2 et encore bravo pour vos performances !

Le debrief de cup_of_tea


Ma solution pour le premier problème est quasi classique et valide, mais avec un ajout de complexité non nécessaire basée sur une hypothèse erronée.
En effet, je pensais naivement qu’un cas spécial était rencontré si après avoir tiré sur une montagne celle-ci restait la plus haute, mais comme un seul tir par aller/retour était autorisé, le fait de vouloir se focaliser sur une autre montagne n’ayant pas la plus grande taille pendant le même déplacement n’avait pas lieu d’être.

Ma seconde solution se base sur une heuristique simple:
Lors de l’exploration, on cherche avant tout à dévoiler les cases marquées d’un point d’interrogation les plus proches. Cela permet d’avoir en moyenne une utilisation d’energie faible pour explorer l’intégralité du graphe. Deuxième point, lorsque l’on a localisé la position permettant de déclencher l’alarme, on se retrouve confronté à deux choix:
  • Soit on continue l’exploration
  • Soit on va déclencher l’alarme et on retourne au point de départ
La première option est choisie lorsque l’on est sûr d’avoir assez d’énergie pour continuer l’exploration puis se diriger vers la salle de commande et retourner au point de départ. Cette exploration permet d’être sûr de connaître le chemin optimal entre la salle de commande et le point de départ, qui ne correspond pas forcément au chemin trouvé précédemment.
Sinon, s’il n’existe plus de zone à explorer ou que l’énergie est trop faible pour faire un détour, la seconde option est choisie.

Pour trouver les points les plus proches ou la distance entre deux points, j’utilise une implémentation classique de parcours en largeur avec une file, Dijkstra n’étant pas nécessaire vu que toutes les distances sont égales à 1.

Ce problème m’a légèrement désarçonné, car avec les contraintes affichées, il était possible de se retrouver confronté à un graphe impossible à explorer en entier avec l’énergie donnée (et donc avec des chances de ne pas trouver la salle de commande ou bien de pouvoir revenir même en ayant trouvé le chemin optimal), mais les tests finaux n’utilisèrent pas de grandes dimensions.

Le concours était intéressant, mais j’espère pouvoir trouver plus de rigueur au niveau des contraintes lors des prochains concours.


Le debrief de redvasily (en anglais)

Aucun commentaire

Enregistrer un commentaire