Coding Solution

Bender - Episode 1 – CodinGame solution in C

Mediumsimulationstate machineloop detection2D gridUpdated
Short answer

Simulate Bender one move at a time: keep his position, direction, breaker mode and inverted priorities, and when the tile ahead is blocked try SOUTH, EAST, NORTH, WEST (or the reverse) in order. To print LOOP reliably, record every (x, y, direction, breaker, inverted) state you have been in and stop when one repeats, clearing that record each time a breakable wall is destroyed because the map has changed.

The problem

Bender starts on the '@' cell of a map of at most 100x100 cells, initially heading south, and must reach the suicide booth '$'. Walls '#' always stop him, 'X' walls stop him unless he is in breaker mode, in which case he smashes them. Letters S, E, N, W force a new direction, 'B' toggles breaker mode (beer), 'I' reverses his priority order, and the two 'T' cells teleport him to each other.

Whenever the cell in front of him is blocked, he tries directions in priority order (SOUTH, EAST, NORTH, WEST, or WEST, NORTH, EAST, SOUTH once inverted) and takes the first free one. You print every move he makes until he reaches '$', or the single word LOOP if he would wander forever.

Approach, step by step

  1. Parse the map and locate special cellsRead each row as a full line because rows contain spaces. Record the start position and both teleporter coordinates, and replace '@' with an empty cell so it is not treated as an obstacle later.
  2. Decide the direction for this turnKeep the current direction while the next cell is free. Only when it is blocked do you walk through the priority list from the start; this is not a 'turn right' rule, Bender always restarts from SOUTH (or WEST when inverted).
  3. Move, then apply the tile effectAdvance one cell, log the move, then react to the tile you landed on: path letter sets the direction, B and I toggle flags, T jumps to the other teleporter keeping the direction, and an X (only reachable in breaker mode) becomes empty space.
  4. Detect loops with a state setBefore each move, check whether the tuple (x, y, direction, breaker, inverted) has already been seen. If it has, the simulation is deterministic and the map is unchanged, so he will repeat forever: print LOOP and stop.
  5. Reset the history when the map changesBreaking an X wall changes the map, so a repeated state after that is not proof of a loop. Clearing the visited set each time a wall is destroyed keeps detection exact; there are at most L·C walls, so the total work stays bounded.

Complexity

TimeO(S·K)
SpaceO(L·C)

S = 16·L·C possible states and K the number of X walls broken plus one; in practice the path is short. The visited table has 16 entries per cell (4 directions × breaker × inverted).

Solution code

Bug fixed in this version: C: LOOP is detected by stopping after 200 moves, but a 100x100 map can require far more than 200 legitimate moves; a 20x40 snake map with a 317-move path was tested and the original prints LOOP instead of the path. If '$' is reached exactly on move 200 it also prints LOOP. Secondary issues: teleport() is called before it is declared (an implicit declaration, a hard error on recent GCC), and gets() no longer exists in C11. The replacement uses exact state-based loop detection and fgets.

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;
}

Common mistakes

Going further

The reason the state set must include the breaker and inverted flags, but not the move history, is that Bender is a deterministic finite automaton over a fixed map: his next action depends only on (position, direction, breaker, inverted) and the current set of X walls. So the moment one of these tuples repeats with the same walls, the future is a copy of the past. Since X walls can only disappear, never reappear, the walls act as a monotonic counter: clearing the visited set after each break is safe, and the simulation is guaranteed to terminate after at most (number of X + 1) × 16·L·C steps. That is a proof, not a heuristic, and it is why this method passes every validator whatever the map size.

FAQ

Why does my Bender solution pass tests but fail validators with LOOP?

Usually because LOOP is decided by a move limit or by revisiting a cell alone. Include direction, breaker mode and inverted priorities in the state, and reset it when a wall breaks.

Does the '@' cell block Bender later?

No, it is ordinary floor once he leaves it. Replace it with a space when parsing so your obstacle check does not treat it specially.

Can Bender break '#' walls in breaker mode?

No. Breaker mode only affects 'X' cells; '#' always triggers the priority search.

Similar puzzles

★ 5.0 · 16 reviews · 928 users Add to Chrome