Revue de code des Top CodinGamers de Ragnarok

STAY CONNECTED, FOLLOW CODINGAME NOW


Aux challenges de CodinGame, personne n'explique mieux un code parfait que CodinGamer lui-même. On a donc demandé au Top 5 de Ragnarok de bien vouloir commenter leur code, pour que tout le monde puisse apprendre des choses de leurs stratégies. Ils ont accepté, merci à eux !

La solution Java de Gawen (1ère place) commentée:
1èr exercice :

Ici pas grand chose à dire. C'est un problème assez classique de trajectoire sur échiquier (avec mouvements 8 directions).

2ème exercice :

Après quelque essais triviaux consistant à attendre que les géants viennent d'eux-même à portée, j'ai adopté une stratégie agressive en demandant à Thor d'aller au plus vite vers les géants.

La base a été de calculer le nombre minimal de géant à abattre par attaque, et de ne surtout pas déclencher l'attaque tant que le nombre de géants à porté ne dépasse pas ce seuil (sauf si Thor se retrouve acculé).

Ensuite, j'ai défini un critère de dangerosité d'une case : une case est dangereuse si elle contient un géant, ou si elle est à une distance de 1 d'un géant (et donc si elle est atteignable par un géant au cours du tour actif)

Ceci étant dit, la stratégie de déplacement consistait à aller vers "la case sûre la plus dangereuse", c'est à dire la case sûre la plus proche d'un géant. En cas d'égalité, on choisi d'aller plutôt vers le centre de l'aire de jeu.
J'avais en premier lieu choisi d'aller vers le barycentre des géants plutôt que vers le centre du terrain, mais les tests on montré que cela avait tendance à coincer Thor sur les bords de la carte si les géants n'étaient pas centrés au départ, ce qui faisait échouer notamment le test n°10. Il reste encore pas mal de traces de ce barycentre dans le code.

Petite anecdote : j'avais mal lu l'énoncé au début en croyant que l'éclair touchait 9 cases centées sur Thor (un carré de 3 sur 3 en somme). C'est en arrivant au dernier jeu de test que j'ai réalisé mon erreur, puisque avec mon hypothèse, il est impossible d'éliminer 15 géants en 1 coup. J'ai donc codé la majorité du temps en sur-contrainte, ce qui a été au final plutôt bénéfique et stimulant.

Autre anecdote : j'ai basé mes calculs de distance sur la norme infinie en dimension 2 (qui est la norme par excellence pour les déplacements 8 directions sur échiquier), que j'ai d'ailleurs appelé norme 1 par erreur dans le code.


La stratégie de Zoyd (3e place, Java) :

"Je n'ai pas cherché à bouger par rapport aux géants. Si aucun géant ne peut me tuer au coup suivant, je ne fais rien. Si un géant peut me tuer, j'envisage de frapper. Je le fais directement si je peux tuer (nombre de géants / nombre de coups).

Sinon, je cherche à bouger en cherchant une case sûre en priorité vers le centre du terrain, de façon à éviter que Thor ne se coince tout seul dans un coin. Donc je cherche d’abord vers le nord si je suis dans la partie sud, et vice versa ; et d’abord vers l’est si je suis dans la partie ouest, et vice versa. Si aucune case n'est sûre, je frappe. 

Comme les géants se déplacent d'eux-mêmes vers Thor, rien de plus n'est nécessaire : ce n'est pas moi qui vais chercher les géants, ce sont eux qui viennent se faire tuer :)".


Pour lire les commentaires de Redvasily (2e place, Python) et Gaurav (4e place, C++), c'est par ici (en anglais)

Aucun commentaire

Enregistrer un commentaire