Revue de code des Top CodinGamers de Skynet Revolution 1

STAY CONNECTED, FOLLOW CODINGAME NOW


Les 3 gagnants de Skynet Revolution 1, iku, Manger et NewbOo partagent avec nous leur revue de code. Bravo à tous les trois et merci !

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 iku :
(1ère place sur le podium | France | Java | 1:33:10)

Pour le premier exercice, pour bien faire il fallait théoriquement faire attention d'arriver au bord du gouffre avant de sauter. Je ne me suis pas embêté dans une première version, et j'ai simplement pris la longueur du gouffre, qui donnait la vitesse minimale à atteindre. Tant que la moto n'a pas atteint cette vitesse, on accélère, quand elle l'a atteint, on maintient jusqu'au gouffre, puis on saute. De l'autre côté on freine jusqu'à l'arrêt, pas besoin de vérifier si ça passera ou pas puisque la vitesse ne pouvait pas être plus faible. Après avoir passé les codes de tests, tout était OK. J'étais un peu surpris mais j'ai décidé de faire confiance aux tests et de passer à la suite sans perdre de temps.




Pour le deuxième exercice, je ne voyais pas du tout comment m'y prendre... Du coup je suis parti sur un algorithme récursif qui teste chaque mouvement possible, et s'arrête quand il ne reste plus assez de motos. Je pensais que la complexité serait trop forte, mais au final c'est passé du premier coup.

Là j'étais assez content de mon temps, et j'ai décidé de soumettre tel quel sans revenir sur le premier exercice, et apparemment c'était une bonne idée !

Merci à l'équipe pour ce challenge !

-------

Le debrief de Manger :
(2e place sur le podium | France | C#,C | 1:36:40)

Pour le premier exercice, mon premier programme s'est d'abord simplement contenté d'accélérer jusqu'à atteindre une vitesse égale à la distance de saut (taille du gouffre + 1), puis de freiner après le saut. Cela ne suffisait pas car, pour passer le gouffre avec une vitesse égale à la distance de saut, il faut démarrer le saut exactement sur la case avant le gouffre.

Pour cela, je calcule dans SpeedDist la distance d'accélération pour atteindre exactement la vitesse souhaitée à partir de la vitesse actuelle. La moto doit alors commencer à accélérer pile quand sa distance au gouffre est égale à cette distance d'accélération. En pratique, avec mon programme, la moto pourrait ne jamais arriver dans une situation où la distance d'accélération est égale à la distance au gouffre. On pourrait donc probablement concevoir des cas de tests dans lesquels ce programme ne répond plus au problème.

Dernier point, le cas de test où la moto commence à une vitesse très élevée. Dans ce cas, je me contente de la faire ralentir jusqu'à une vitesse suffisante pour le saut, ce qui permet de passer les derniers tests.

Le deuxième exercice était plus difficile. De mon côté, j'ai hésité entre deux méthodes :

- Partir d'une stratégie simple permettant de passer les premiers tests, puis la bidouiller au fil des cas de tests pour tous les passer. Ça peut fonctionner, on tient le temps d'exécution sans difficultés si on ne s'amuse pas à faire de calculs lourds (ce qui ne doit pas trop arriver avec cette méthode), mais ça peut vite finir en un code assez illisible (une sorte de soupe imbuvable de if/else/while) et quelques maux de tête.

- À chaque tour de jeu, il n'y a que six mouvements possibles (SPEED/SLOW/JUMP/UP/DOWN/WAIT) : on a un arbre de possibilités (chaque noeud ayant six fils, un par mouvement possible) que l'on va parcourir en profondeur (en limitant la profondeur d'exploration). Dans le cas présent, cette méthode semble envisageable car il n'y a que peu de choix possibles : la complexité étant en O(Nombre de choix ^ Profondeur de l'exploration), un nombre de choix élevé élimine cette méthode. L'avantage est qu'on a la garantie de toujours trouver la solution si elle existe pourvu qu'on ait une profondeur d'exploration suffisante, l'inconvénient étant le risque de ne pas tenir la contrainte de temps si on donne une profondeur d'exploration trop grande. Ainsi, si on rencontre un cas de test qui nécessite une profondeur d'exploration pour laquelle on ne tient pas la contrainte de temps, on risque d'être coincé.

Trouvant systématiquement des contre-exemples aux idées de stratégies simples qui me venaient en tête, j'ai choisi de m'orienter vers la seconde solution. Pour un parcours en profondeur, le plus simple est d'utiliser une fonction récursive. En utilisant une fonction récursive, on prend le risque d'un dépassement de pile, mais, dans le cas présent, ça ne risque pas d'arriver car la profondeur d'exploration doit être faible si on veut tenir les délais. On peut de toutes façons bidouiller pour changer la taille de la pile si besoin est.

Cette fonction récursive prendra pour argument l'état du jeu, retournant un choix ou SUCCES si un choix possible est trouvé, DEFAITE sinon et procédera ainsi :

- Si profondeur maximale atteinte, retourner SUCCES
- Pour chaque choix possible (SPEED/SLOW/JUMP/UP/DOWN/WAIT) :
  • Simuler le nouvel état de jeu avec le choix
  • Si le nouvel état correspond à une défaite, passer au choix suivant
  • Si le nouvel état correspond à une fin de piste (victoire), sortir de la fonction en retournant le choix effectué
  • Faire un appel récursif avec pour argument le nouvel état du jeu
-> Si le retour est un choix ou SUCCES, sortir de la fonction en retournant le choix que l'on considérait
-> Si le retour est DEFAITE, passer au choix suivant

- On a parcouru tous les choix sans jamais avoir trouvé de choix menant à une victoire ou à l'atteinte de la profondeur d'exploration maximale : on retourne DEFAITE

L'état global du jeu (position des motos, motos mortes/vivantes, vitesse du groupe) se décrit en très peu de variable. Lors de la simulation du nouvel état du jeu, on a deux choix :

- Simuler le nouvel état du jeu dans une copie de l'état du jeu, que l'on peut "jeter" après.

- Modifier l'état courant avec la simulation, puis, connaissant le mouvement que l'on a effectué, revenir en arrière.

La deuxième option prend peu de place en mémoire et ne copie jamais l'état du jeu, et est donc performante quand les états du jeu sont assez grands. La première prend plus de place et fait plus de copies, mais est beaucoup plus simple à coder (pas besoin de revenir en arrière après avoir simulé le nouvel état de jeu). Comme les états sont petits, j'ai choisi le premier choix. Dans la mesure où il va y avoir des copies fréquentes et où il y a un risque de ne pas tenir les contraintes de temps d'exécution, j'ai choisi de coder le programme en C++. En C++, en codant l'état du jeu dans une structure/classe avec des tableaux de table fixe, une simple assignation suffit à copier l'état du jeu de manière assez efficace vu que toutes les données sont contiguës en mémoire. En C#, si les structures sont elles aussi recopiées par les assignations, les tableaux sont alloués dynamiquement et la copie d'une structure contenant un tableau ne copiera que la référence vers ce tableau. Il faudrait donc écrire une fonction de clonage d'état de jeu qui, même si elle serait courte, serait probablement bien moins performante qu'une copie en C++ (nécessité de réallouer les tableaux). Il y a aussi la possibilité d'utiliser des blocs unsafe en C#, mais je n'avais aucune expérience sur ce sujet.
Voici finalement ma solution commentée :

#include <iostream>
#include <string>
#include <string.h>

using namespace std;

// Suite de #define au lieu d'une énumération car le compilateur m'a embêté sur des casts implicites d'entiers vers énumération
#define SPEED 0
#define WAIT 1
#define JUMP 2
#define SLOW 3
#define UP 4
#define DOWN 5

int M;
int V;
char R[4][1024];
int LEN[4];

// Structure décrivant l'état d'un jeu. Aucun membre alloué dynamiquement pour pouvoir la recopier entièrement par simple assignation
struct GameState
{
    int S;
    int X[4];
    int Y[4];
    bool A[4];
 
    // Simulation du nouvel état de jeu si on choisit d'effectuer l'action "action"
    GameState Update(int action)
    {
        GameState newState = *this; // La recopie
     
        // Point sur lequel j'ai perdu beaucoup de temps ici : j'avais souvent tendance à oublier les "newState." dans les modifications de variable. Technique pour éviter cela : utiliser plutôt un constructeur pour la mise à jour : GameState(GameState &orig, int action) {*this = orig; ...}
     
        if(action == SPEED)
            newState.S++;
        if(action == SLOW)
            newState.S--;
        if(newState.S < 0)
            newState.S = 0;
     
        for(int i=0; i<M; i++)
        {
            newState.X[i]+=newState.S;
        }
     
        char dy = 0;
        if(action == UP)
            dy = -1;
        if(action == DOWN)
            dy = 1;
        for(int i=0; i<M; i++)
        {
            newState.Y[i] += dy;
            if(newState.Y[i] >= 4)
                newState.Y[i] = 3;
            if(newState.Y[i] < 0)
                newState.Y[i] = 0;
        }
     
        // On regarde si des motos sont mortes en chemin
        if(action != JUMP)
        {
            for(int i=0; i<M; i++)
            {
                for(int x=X[i]+1; x<newState.X[i]; x++)
                {
                    if(R[newState.Y[i]][x])
                        newState.A[i] = false;
                    if(x < newState.X[i] && R[Y[i]][x])
                        newState.A[i] = false;
                }
            }
        }
     
        for(int i=0; i<M; i++)
        {
            if(R[newState.Y[i]][newState.X[i]])
                newState.A[i] = false;
        }
     
        return newState;
    }
 
    // Notre parcours en profondeur. SUCCES = WAIT dans ici. DEFAITE = -1. *this correspond à l'état du jeu, MaxDepth-depth à la profondeur d'exploration courante.
    int IsFeasible(int depth)
    {
        if(depth < 0)
            return WAIT;
         
        // A-t-on perdu ? Gagné ? Avec la description plus haut, ce bloc là se situerai normalement dans la boucle for plus bas
        int survivors = 0;
        int winners = 0;
        for(int i=0; i<M; i++)
            if(A[i])
            {
                survivors++;
                if(X[i] > LEN[Y[i]])
                    winners++;
            }
     
        if(survivors < V)
            return -1;
        if(winners >= V)
            return WAIT;

        // Parcours des choix possibles
        for(int a=0; a<=5; a++)
        {
   // Si on ne fait pas ce qui suit, l'algorithme peut très bien choisir de rester en permanence à ne rien faire. En effet, on est sûr de ne jamais perdre si on ne fait rien vu qu'on ne tient pas compte de la contrainte du nombre limite de tours.
            if(S == 0 && (a != SPEED))
                continue;
         
            GameState s = Update(a); // Simulation avec le choix considéré
         
            if(s.IsFeasible(depth-1) != -1)
            {
                s.Print();
                return a;
            }
        }
     
        return -1;
    }
 
    void Print()
    {
        fprintf(stderr, "New state: %d - ", S);
        for(int i=0; i<M; i++)
        {
            fprintf(stderr, "[%d,%d,%d]", X[i], Y[i], A[i]);
        }
        fprintf(stderr, "\n");
    }
};

#include <time.h> // Ajout de time.h pour les mesures de temps
int main()
{
    const char *acts[] = {"SPEED", "WAIT", "JUMP", "SLOW", "UP", "DOWN"};
 
    // Read init information from standard input, if any
    scanf("%d", &M);
    scanf("%d", &V);
    for(int i=0; i<4; i++)
    {
        scanf("%s", R[i]);
        LEN[i] = strlen(R[i]);
        fprintf(stderr, "Road %d: %d length\n", i, LEN[i]);
        for(int j=0; j<LEN[i]; j++)
        {
            R[i][j] = (R[i][j] == '0' ? 1 : 0); // 1 : hole, 0 : ok
        }
    }
 
    struct timespec start, end;
    while (1) {
     
        GameState s;
        scanf("%d", &s.S);
        for(int i=0; i<M; i++)
        {
            int a;
            scanf("%d %d %d", &s.X[i], &s.Y[i], &a);
            s.A[i] = (a == 1);
        }
     
        clock_gettime(CLOCK_MONOTONIC, &start);
        int a = s.IsFeasible(10); // Profondeur maximale : 10
        clock_gettime(CLOCK_MONOTONIC, &end);
        if(a == -1)
            printf("WTF?\n");
        else
            printf("%s\n", acts[a]);
     
        fprintf(stderr, "Took %d us\n", (end.tv_sec-start.tv_sec)*1000+(end.tv_nsec-start.tv_nsec)/1000);
    }

    return 0;
}

Au final, une profondeur d'exploration maximale de 10 suffisait. Je n'ai pas essayé de regarder avec moins pendant le concours ; cependant, après avoir testé en mode entraînement, une profondeur de 4 suffisait au minimum. Les contraintes de temps sont très largement tenues (quelques microsecondes pour le parcours en lui-même), ce qui montre qu'au final, dans ce cas, il ne fallait pas forcément s'inquiéter des performances. Le déboggage de code C++ étant plus délicat que du code Java/C#, il aurait probablement été plus rentable de s'attaquer au problème dans l'un de ces deux langages, quitte à coder la courte fonction de copie d'état de jeu.


Le debrief de NewboO :
(3e place sur le podium | France | PHP | 1:45:33)

1er exercice : Pas grand chose de plus à ajouter que l'algo expliqué sur le blog. Je m'attendais cependant à des cas où il faudrait insérer des attentes au milieu de la prise d'élan pour arriver pile au bord du gouffre avant de sauter, mais c'est resté sur le papier vu que tout les tests passaient sans cette considération.

2ème exercice : Pour l'anecdote, j'étais un peu crevé le soir de l'épreuve et j'ai choisi de bruteforcer uniquement par paresse (comme quoi, il vaut mieux parfois ne pas trop réfléchir). Il y avait cependant quelques subtilités qui permettaient d'obtenir une solution plus rapidement et sans avoir à se préoccuper de la profondeur, même si je ne les ai pas toutes incluses dans mon code final (les 150ms du premier tour étaient suffisantes, même en PHP). L'ordre idéal pour tester les actions était SPEED, JUMP, UP, DOWN, SLOW:
- Privilégier SPEED pour explorer d'abord les branches les plus courtes
- Privilégier JUMP parce que le test est rapide (une position par moto plutôt qu'une voire deux portions de route)
- Ne pas tester WAIT parce que JUMP donne toujours la même position finale
Au final je suis resté sur SPEED, UP, DOWN, WAIT, JUMP, SLOW pour des raisons esthétiques (parce que ça reste des motos, pas des cabris ^_^)

Le mot de la fin : Un grand merci à toute l'équipe CodinGame pour les exercices sympathiques qui sont proposés à chaque édition. J'ai découvert le site par hasard il y a 3 mois et je suis devenu fan.

------------


1 commentaire :