Bender, a depressed robot


The aim of this puzzle is, given a map, the starting position of Bender the robot and the effect on him of the items found on the map, to compute the moves he will do. It does not involve any interesting algorithm, only a lot of switch statements to handle all cases.

Difficulty: Medium · Skills: simulation, state machine, loop detection, grid navigation

What this puzzle tests in a coding interview

Bender, a depressed robot is a rule-heavy simulation on a grid: priorities, inverters, beer that lets him break walls, teleporters and path modifiers. Recruiters use it to test whether you can keep a clean state model and detect an infinite loop.

How to solve it, step by step

  1. Read the map, locating Bender's start and both teleporters.
  2. Keep Bender's state: position, direction, priority order, breaker mode and inverted mode.
  3. Each step, look at the next cell; if it is blocked by a wall or an unbreakable obstacle, try the directions in the current priority order.
  4. Move, then apply the effect of the new cell: change direction, toggle the inverter or beer, teleport, or break an X wall in breaker mode.
  5. Stop at the suicide booth and print the moves, or print LOOP when the move count exceeds a safe limit.

Time and memory complexity

Each step is O(1), and the run is capped by the loop limit, so time is bounded by that limit and memory is O(L x C) for the map plus the stored moves.

Traps to avoid

Tip for a timed test

A simple move cap of a few hundred steps per cell count is enough to detect loops in practice; spend your time on the rules, not on a perfect state hash.

C

I prefered allocating the 2-dimensionnal array (the map) dynamically, because it makes it easier to pass them to functions.

#include <stdlib.h>
#include <stdio.h>

struct Coords {
    int X;
    int Y;
};

// gathered the variables in a struct to simplify code
struct Infos {
    struct Coords c;
    // order in which bender tries the 4 directions, point on norder or rorder
    char* order;
    // 1 if bender is in breaker mode, 0 else
    int breaker;
    // S, E, W or N
    char direction;
    struct Coords teleporters[2];
};

char norder[4] = { 'S', 'E', 'N', 'W' };
char rorder[4] = { 'W', 'N', 'E', 'S' };

// array representing the sequence of moves taken by Bender
int nbMoves = 0;
char* moves[200];

// Returns the coordinates of the next Tile bender will move on to
struct Coords nextTile (struct Infos *bender){
    struct Coords res = { bender->c.X , bender->c.Y };
    switch (bender->direction) {
        case 'S':
            res.Y++; break;
        case 'W':
            res.X--; break;
        case 'E':
            res.X++; break;
        case 'N':
            res.Y--; break;
    }
    return res;
}

// Makes bender move on, update variables according to what is found on next tile
void go (struct Infos *bender, char** map){
    switch (bender->direction) {
        case 'N':
            moves[nbMoves] = "NORTH\n";
            bender->c.Y--;
            break;
        case 'S':
            moves[nbMoves] = "SOUTH\n";
            bender->c.Y++;
            break;
        case 'E':
            moves[nbMoves] = "EAST\n";
            bender->c.X++;
            break;
        case 'W':
            moves[nbMoves] = "WEST\n";
            bender->c.X--;
            break;
    }
    nbMoves++;
    switch (map[bender->c.Y][bender->c.X]) {
        case 'X':
            map[bender->c.Y][bender->c.X] = ' ';
            break;
        case 'B':
            bender->breaker = !bender->breaker;
            break;
        case 'I':
            bender->order = (bender->order == norder)?rorder:norder;
            break;
        case 'S':
        case 'N':
        case 'E':
        case 'W':
            bender->direction = map[bender->c.Y][bender->c.X];
            break;
        case 'T':
            teleport(bender);
            break;
    }
}

// computes the direction Bender will take according to order, breaker mode, etc
void changeDirection (struct Infos *bender, char** map){
    int i = 0;
    struct Coords t = nextTile(bender);
    while (map[t.Y][t.X] == '#' || (!bender->breaker && map[t.Y][t.X] == 'X')) {
            bender->direction = bender->order[i++];
            t = nextTile(bender);
    }
}

// teleports Bender from the teleporter it is on to the other
void teleport (struct Infos *bender){
    if (bender->c.X == bender->teleporters[0].X && 
        bender->c.Y == bender->teleporters[0].Y) 
    {
        bender->c.X = bender->teleporters[1].X;
        bender->c.Y = bender->teleporters[1].Y;
    }
    else {
        bender->c.X = bender->teleporters[0].X;
        bender->c.Y = bender->teleporters[0].Y;
    }
}

int main(int argc, char **argv)
{
    struct Infos bender;
 
    // Read input   
    int L, C;
    scanf("%d %d\n", &L, &C);
    char** map = malloc(L*sizeof(char*));
    int telep = 0;
    for (int i = 0; i < L; i++) {
        map[i] = malloc((C+1)*sizeof(char));
        gets(map[i]);
        for (int j = 0; j < C; j++) {
            if (map[i][j] == '@') {
                bender.c.X = j;
                bender.c.Y = i;
            }
            if (map[i][j] == 'T') {
                bender.teleporters[telep].X = j;
                bender.teleporters[telep++].Y = i;
            }
        }
    }
    
    bender.order = norder;
    bender.breaker = 0;
    bender.direction = 'S';

    while (map[bender.c.Y][bender.c.X] != '$' && nbMoves < 200) {
        struct Coords t = nextTile(&bender);
        switch(map[t.Y][t.X]) {
            case ' ':
            case '$':
            case 'E':
            case 'W':
            case 'S':
            case 'N':
            case 'B':
            case 'I':
            case 'T':
                go(&bender, map);
                break;
            case '#':
            case 'X':
                changeDirection(&bender, map);
                go(&bender, map);
                break;       
        }
    }
    
    if (nbMoves == 200)
        printf("LOOP\n");
    else
        for (int i = 0; i < nbMoves ; i++)
            printf(moves[i]);

    // frees memory
    for (int i = 0; i < L; i++)
        free(map[i]);
    free(map);

    return EXIT_SUCCESS;
}