Coding Solution

Bender - Episode 1 – solution CodinGame en C

Moyensimulationstate machineloop detection2D gridMis à jour le
Réponse courte

On simule Bender déplacement par déplacement : on garde sa position, sa direction, le mode breaker et l'inversion des priorités, et quand la case devant lui est bloquée on essaie SOUTH, EAST, NORTH, WEST (ou l'inverse) dans l'ordre. Pour afficher LOOP de façon fiable, on enregistre chaque état (x, y, direction, breaker, inversé) rencontré et on s'arrête dès qu'un état se répète, en vidant cet historique à chaque mur cassable détruit puisque la carte a changé.

L'énoncé

Bender démarre sur la case '@' d'une carte d'au plus 100x100 cases, d'abord orienté vers le sud, et doit atteindre la cabine de suicide '$'. Les murs '#' l'arrêtent toujours, les murs 'X' l'arrêtent sauf en mode breaker, où il les pulvérise. Les lettres S, E, N, W imposent une nouvelle direction, 'B' bascule le mode breaker (bière), 'I' inverse son ordre de priorité, et les deux cases 'T' le téléportent l'une vers l'autre.

Chaque fois que la case devant lui est bloquée, il essaie les directions dans l'ordre de priorité (SOUTH, EAST, NORTH, WEST, ou WEST, NORTH, EAST, SOUTH une fois inversé) et prend la première libre. On affiche chacun de ses déplacements jusqu'à ce qu'il atteigne '$', ou le seul mot LOOP s'il doit errer indéfiniment.

La démarche, étape par étape

  1. Lire la carte et repérer les cases spécialesOn lit chaque rangée comme une ligne complète, car elles contiennent des espaces. On note la position de départ et les coordonnées des deux téléporteurs, et on remplace '@' par une case vide pour qu'il ne soit pas traité comme un obstacle plus tard.
  2. Choisir la direction du tourOn conserve la direction courante tant que la case suivante est libre. Ce n'est que lorsqu'elle est bloquée qu'on parcourt la liste de priorité depuis le début ; ce n'est pas une règle « tourner à droite », Bender repart toujours de SOUTH (ou de WEST en mode inversé).
  3. Avancer, puis appliquer l'effet de la caseOn avance d'une case, on journalise le déplacement, puis on réagit à la case d'arrivée : une lettre de direction fixe la direction, B et I basculent leurs indicateurs, T saute vers l'autre téléporteur en gardant la direction, et un X (atteignable seulement en mode breaker) devient une case vide.
  4. Détecter les boucles avec un ensemble d'étatsAvant chaque déplacement, on vérifie si le tuple (x, y, direction, breaker, inversé) a déjà été vu. Si oui, la simulation étant déterministe et la carte inchangée, il répétera la même chose à l'infini : on affiche LOOP et on s'arrête.
  5. Réinitialiser l'historique quand la carte changeCasser un mur X modifie la carte, donc un état répété après coup ne prouve plus une boucle. Vider l'ensemble des états visités à chaque mur détruit garde une détection exacte ; il y a au plus L·C murs, donc le travail total reste borné.

Complexité

TempsO(S·K)
MémoireO(L·C)

S = 16·L·C états possibles et K le nombre de murs X cassés plus un ; en pratique le chemin est court. La table des états visités compte 16 entrées par case (4 directions × breaker × inversé).

Code de la solution

Bender - Episode 1 – C

#include <stdio.h>
#include <string.h>

// direction indexes: 0 SOUTH, 1 EAST, 2 NORTH, 3 WEST (default priority order)
static const int DX[4] = { 0, 1, 0, -1 };
static const int DY[4] = { 1, 0, -1, 0 };
static const char *NAMES[4] = { "SOUTH", "EAST", "NORTH", "WEST" };

static char map[100][102];
// seen[y][x][dir][breaker][inverted]: state already visited since the last broken wall
static unsigned char seen[100][100][4][2][2];
// worst case: every state once between each of the (at most L*C) broken walls
static int moves[1000000];

static int dirOf(char c)
{
    switch (c) {
        case 'S': return 0;
        case 'E': return 1;
        case 'N': return 2;
        case 'W': return 3;
    }
    return -1;
}

static int blocked(int x, int y, int breaker)
{
    char c = map[y][x];
    return c == '#' || (c == 'X' && !breaker);
}

int main()
{
    int L, C;
    if (scanf("%d %d", &L, &C) != 2) return 0;
    fgetc(stdin); // consume end of line

    int x = 0, y = 0, tx[2], ty[2], nt = 0;
    for (int i = 0; i < L; i++) {
        fgets(map[i], sizeof map[i], stdin); // rows may contain spaces
        for (int j = 0; j < C; j++) {
            if (map[i][j] == '@') { x = j; y = i; map[i][j] = ' '; }
            if (map[i][j] == 'T') { tx[nt] = j; ty[nt] = i; nt++; }
        }
    }

    int dir = 0, breaker = 0, inverted = 0, n = 0;
    while (map[y][x] != '$') {
        if (seen[y][x][dir][breaker][inverted]) {
            puts("LOOP");
            return 0;
        }
        seen[y][x][dir][breaker][inverted] = 1;

        // facing an obstacle: try the 4 directions in priority order
        if (blocked(x + DX[dir], y + DY[dir], breaker)) {
            for (int k = 0; k < 4; k++) {
                int d = inverted ? 3 - k : k;
                if (!blocked(x + DX[d], y + DY[d], breaker)) { dir = d; break; }
            }
        }

        x += DX[dir];
        y += DY[dir];
        moves[n++] = dir;

        char c = map[y][x];
        if (c == 'X') {               // only reachable in breaker mode
            map[y][x] = ' ';
            memset(seen, 0, sizeof seen); // the map changed, old states are no longer loops
        } else if (c == 'B') {
            breaker = !breaker;
        } else if (c == 'I') {
            inverted = !inverted;
        } else if (c == 'T') {
            int other = (x == tx[0] && y == ty[0]) ? 1 : 0;
            x = tx[other];
            y = ty[other];
        } else if (dirOf(c) >= 0) {
            dir = dirOf(c);
        }
    }

    for (int i = 0; i < n; i++)
        puts(NAMES[moves[i]]);
    return 0;
}

Erreurs fréquentes

Pour aller plus loin

La raison pour laquelle l'ensemble d'états doit contenir les indicateurs breaker et inversé, mais pas l'historique des déplacements, est que Bender est un automate fini déterministe sur une carte fixe : son action suivante ne dépend que de (position, direction, breaker, inversé) et de l'ensemble courant des murs X. Dès qu'un de ces tuples se répète avec les mêmes murs, l'avenir est une copie du passé. Comme les murs X ne peuvent que disparaître, jamais réapparaître, ils jouent le rôle d'un compteur monotone : vider l'ensemble des visités après chaque casse est sans risque, et la simulation termine à coup sûr en au plus (nombre de X + 1) × 16·L·C étapes. C'est une preuve, pas une heuristique, et c'est pourquoi cette méthode passe tous les validateurs quelle que soit la taille de la carte.

Questions fréquentes

Pourquoi ma solution Bender passe les tests mais échoue aux validateurs avec LOOP ?

En général parce que LOOP est décidé par une limite de coups ou par le simple retour sur une case. Il faut inclure la direction, le mode breaker et l'inversion des priorités dans l'état, et le réinitialiser quand un mur casse.

La case '@' bloque-t-elle Bender par la suite ?

Non, c'est un sol ordinaire une fois qu'il l'a quittée. On la remplace par un espace au moment de la lecture pour que le test d'obstacle ne la traite pas à part.

Bender peut-il casser les murs '#' en mode breaker ?

Non. Le mode breaker n'agit que sur les cases 'X' ; '#' déclenche toujours la recherche par priorité.

Puzzles similaires

★ 5,0 · 16 avis · 928 utilisateurs Ajouter à Chrome