Revue de code des Top CodinGamers de Shadows of the Knight

STAY CONNECTED, FOLLOW CODINGAME NOW

Les gagnants de Shadows of the Knight, Gangrene et MockingHawk, reviennent sur leur code et nous expliquent leur stratégies.

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 | 1:34:48)


Dans la première épreuve, Batman connaît directement la direction dans laquelle se trouvent les otages.
La façon de les atteindre le plus rapidement est donc, à chaque tour, de diviser la zone de recherche par deux en se rendant au milieu.

Pour ce faire, je suis parti sur deux tableaux à 1 dimension, représentant l'ensemble des lignes ou colonnes disponibles.


A chaque nouveau tour ces deux tableaux sont recalculés, et la valeur moyenne est renvoyée.

Ce choix n'est pas optimal en terme de temps de calcul, car j'aurais pu n'utiliser que 4 variables xmin,xmax,ymin,ymax pour définir mon champ de recherche.
J'ai fait ce choix car le langage python permet très facilement de manipuler les tableaux (listes), et que cela me permettait de m'affranchir des calculs d'arrondis, sources d'erreurs.


Dans la deuxième épreuve, Batman n'a plus accès à la direction, mais sait uniquement s'il se rapproche ou s'éloigne des otages.

Comme le montre l'exemple de l'énoncé, la zone de recherche peut ainsi prendre la forme d'un polygone défini par nos déplacements et les réponses obtenues.
Dans la pratique, il n'est pas ou peu utile de jouer avec un tel polygone.
Je décide de rester sur le même système que pour l'exercice précédent, avec deux listes d'entiers.

Comme les indications ne donnent plus la direction à suivre, je cherche coordonnée par coordonnée : d'abord le X, puis le Y.

Je commence donc par le X.
De la même façon qu'à l'exercice précédent, on cherche intuitivement à diviser l'espace de recherche par deux.
L'équation pour obtenir la nouvelle position est donc x_new = x_max + x_min - x (x_min et x_max sont les valeurs min et max calculées, et non pas 0 et W-1).

Cependant il y a un problème : avec ce calcul on peut sauter hors de l'immeuble et ... mourir!
Ce problème est facile à résoudre : il suffit de se ramener à 0 ou à x_max. Mais il implique un second problème : l'espace n'est plus divisé en deux parties égales.
Ca, les organisateurs de CodinGame l'ont bien remarqué, et ils ont incité le joker à placer ses otages aux extrémités de l'immeuble dans plusieurs cas de tests.

La solution que j'ai trouvée est de diviser le mouvement du Batman par 2 lorsqu'il se trouve au bord de l'immeuble.
De cette façon, j'obtiens une sorte d'équilibre : lorsqu'il devrait sauter hors de l'immeuble et qu'il s'arrête au bord, la zone de recherche n'est réduite qu'un petit peu, mais lorsqu'il repart de l'autre côté, il va moins loin qu'il ne devrait, et ainsi et la zone de recherche est réduite d'un plus gros morceau (si les otages sont effectivement près du bord).

Lorsque la zone de recherche est réduite à 1 seule solution, je place le Batman sur le X qui va bien, et je recommence pour le Y.

Le mot de la fin:

Je remercie l'équipe de CodinGame pour cette épreuve, qui m'a encore une fois fait chauffer les neurones. On n'en demande pas plus.
J'ai en plus de ça pu parfaire mes connaissances en mangas, puisque je sais à présent que Gotham City compte des immeubles de 8000 étages (test 8 de l'exercice 2)!

Lorsque sur irc j'ai appris que l'équipe de CodinGame souhaitaient lire mon code, j'ai eu honte.
En effet il n'était pas commenté et contenait des bouts de code inutiles et des affichages de débug (je la voulais cette ps4!).
Je vous livre du coup une version épurée et commentée (en anglais).
Le déroulement est le même que dans celui de l'épreuve, mais j'ai déplacé une partie vers la fonction get_next() pour plus de lisibilité (et moins de redondance de code).

import sys

W,H = [int(v) for v in raw_input().split()]
int(raw_input()) # number of available jumps. We don't need that
X0,Y0 = [int(v) for v in raw_input().split()]

X = X0
Y = Y0

TX = range(W)
TY = range(H)

def set_warmer(X0,X,Y0,Y):
   """
       Reduces available values in TX or TY
       Remaining values are closer to X than to X0 or closer to Y than to Y0
   """
   global TX,TY
   if X != X0:
       TX = [v for v in TX if abs(v-X)<abs(v-X0)]
   else:
       TY = [v for v in TY if abs(v-Y)<abs(v-Y0)]

def get_next(v, tab, vmax):
   """
       Compute next coordinate from current one and available solutions
       v    : Batman current position (X or Y)
       tab  : available solutions (TX or TY)
       vmax : max possible position, we don't want to kill Batman
   """
   res = tab[0]+tab[-1]-v

   # Make sure res != v
   if v == res:
       res += 1
   res = min(max(res,0),vmax)

   # If we are currently on the border of the building, we half the distance
   if v==0 or v==vmax:
       res = (res+v)/2

       # Make sure res != v
       if res==0:
           res=1
       elif res==W-1:
           res -= 1
   return res

while 1:
   # X and Y are new position
   # X0 and Y0 are previous position
   # TX and TY are remaining possible solutions
   
   # Read information from standard input
   line = raw_input()

   # If we got the position, just move!
   if len(TX)==1 and TX[0]!=X:
       # little mistake here, I should have added X0 = X
       # this makes me lose 1 turn
       X=TX[0]
       print "%s %s" % (X,Y)
       continue
   if len(TY)==1 and TY[0]!=Y:
       Y=TY[0]
       print "%s %s" % (X,Y)
       continue

   # Use input to reduce TX or TY
   if line == 'SAME':
       if X != X0:
           TX = [(X+X0)/2]
       else:
           TY = [(Y+Y0)/2]
   elif line == 'WARMER':
       set_warmer(X0,X,Y0,Y)
   elif line == 'COLDER':
       set_warmer(X,X0,Y,Y0)

   # Update 'previous' values
   X0 = X
   Y0 = Y

   # Compute new coordinates
   if len(TX)>1:
       X = get_next(X, TX, W-1)
   else:
       Y = get_next(Y, TY, H-1)

   # Write new position to standard output
   print "%s %s" % (X,Y)


--

Le débrief de MockingHawk :
(3ème place sur le podium | France | C++ | 1:56:34)


Premier problème
Dès les premières secondes de l'épreuve et après lecture de l'exemple proposé, je me rends compte que la recherche dichotomique à la fois sur l'axe x et y s'impose. Je regarde le dernier test et vois que Batman n'a que 14 tours à jouer, ce qui correspond bien au logarithme en base 2 de 10000. Dès lors, plus de doutes, je commence une recherche qui se base sur les bornes supérieure et inférieure d'une zone où la bombe pourrait se trouver. Je remercie d'ailleurs toute l'équipe CG pour avoir colorié cette zone dans le mode Debug.

A chaque fois la position de Batman est la moyenne des bornes supérieures et inférieures sur les deux axes. Ensuite la position de Batman devient la borne supérieure ou inférieure et l'autre borne reste inchangée. On procède ainsi tant que le résultat n'a pas été trouvé. On réalise bien une recherche dichotomique.

En ce qui concerne mes impressions, j'ai trouvé intéressant le premier exercice et je déplore le temps relativement long que j'y ai passé (45 min) à cause d'une lecture hasardeuse de l'entrée pour mon premier contest en C++.


Second problème
J'aborde cet exercice avec le sentiment que j'ai déjà beaucoup de retard pour cette épreuve. Après lecture de l'énoncé, j'avouerai que j'étais un peu perdu.

J'ai alors pris une feuille et un crayon et j'ai fait des dessins. Après une vingtaine de minutes, je me rends compte que l'on ne peut faire varier qu'une coordonnée à la fois pour pouvoir être sur que le changement n'était lié qu'à elle seule, un peu comme dans les expériences de SVT au collège où l'on variait un seul paramètre.

En repensant au collège et en regardant des exemples sur le débug, je me suis aussi rappelé que c’était la médiatrice d'un segment qui séparait les points plus près d'une extrémité et de l'autre. Dès lors, je compris que l'on pouvait réaliser une recherche dichotomique sur un axe puis sur l'autre en faisant en sorte que la médiatrice coupe le plus au milieu possible la zone bleue du débug (qui a le même rôle que dans l'exercice 1). La complexité d'un tel algorithme est O(log W + log H) avec W la largeur et H la hauteur. Cette complexité était en accord avec les 30 tours accordés au dernier test.

J'étais alors convaincu que l'algorithme auquel je réfléchissais depuis 40 minutes pouvait fonctionner et je décidai alors de l'implémenter, de manière analogue à la méthode de l'exercice 1.


Conclusion
Je souhaitais remercier toute l'équipe CG pour ce nouveau challenge très intéressant. Les exercices proposés étaient difficiles et nécessitaient une grande analyse préparatoire. Je conseille à tous ceux qui n'ont pas fait le challenge d'essayer d'implémenter leur propre solution résoudre un tel problème est toujours instructif.

Aucun commentaire

Enregistrer un commentaire