Robert Eisele
Engineer, Systems Architect and DBA

Codingame: Bender - Episode 1

Original Problem

The Goal

Bender is a depressed robot who heals his depression by partying and drinking alcohol. To save him from a life of debauchery, his creators have reprogrammed the control system with a more rudimentary intelligence. Unfortunately, he has lost his sense of humor and his former friends have now rejected him.

Bender is now all alone and is wandering through the streets of Futurama with the intention of ending it all in a suicide booth.

To intercept him and save him from almost certain death, the authorities have given you a mission: write a program that will make it possible to foresee the path that Bender follows. To do so, you are given the logic for the new intelligence with which Bender has been programmed as well as a map of the city.

Rules

The 9 rules of the new Bender system:

  1. Bender starts from the place indicated by the @ symbol on the map and heads SOUTH.
  2. Bender finishes his journey and dies when he reaches the suicide booth marked $.
  3. Obstacles that Bender may encounter are represented by # or X.
  4. When Bender encounters an obstacle, he changes directionusing the following priorities: SOUTH, EAST, NORTH and WEST. So he first tries to go SOUTH, if he cannot, then he will go EAST, if he still cannot, then he will go NORTH, and finally if he still cannot, then he will go WEST.
  5. Along the way, Bender may come across path modifiers that will instantaneously make him change direction. The S modifier will make him turn SOUTH from then on, E, to the EAST, N to the NORTH and W to the WEST.
  6. The circuit inverters (I on map) produce a magnetic field which will reverse the direction priorities that Bender should choose when encountering an obstacle. Priorities will become WEST, NORTH, EAST, SOUTH. If Bender returns to an inverter I, then priorities are reset to their original state (SOUTH, EAST, NORTH, WEST).
  7. Bender can also find a few beers along his path (B on the map) that will give him strength and put him in “Breaker” mode. Breaker mode allows Bender to destroy and automatically pass through the obstacles represented by the character X (only the obstacles X). When an obstacle is destroyed, it remains so permanently and Bender maintains his course of direction. If Bender is in Breaker mode and passes over a beer again, then he immediately goes out of Breaker mode. The beers remain in place after Bender has passed.
  8. 2 teleporters T may be present in the city. If Bender passes over a teleporter, then he is automatically teleported to the position of the other teleporter and he retains his direction and Breaker mode properties.
  9. Finally, the space characters are blank areas on the map (no special behavior other than those specified above).
Your program must display the sequence of moves taken by Bender according to the map provided as input.

The map is divided into lines (L) and columns (C). The contours of the map are always unbreakable # obstacles. The map always has a starting point @ and a suicide booth $.

If Bender cannot reach the suicide booth because he is indefinitely looping, then your program must only display LOOP.

Example

Let the map below:

######
#@E $#
# N #
#X #
######

In this example, Bender will follow this sequence of moves:

  • SOUTH (initial direction)
  • EAST (because of the obstacle X)
  • NORTH (change of direction caused by N)
  • EAST (change of direction caused by E)
  • EAST (current direction, until end point $)

Game Input

Input

Line 1: the number of lines L and columns C on the map, separated by a space.

The following L lines: a line of the length C representing a line on the map. A line can contain the characters #, X, @, $, S, E, N, W, B, I, T and space character.

Output
  • If Bender can reach $, then display the sequence of moves he has taken. One move per line: SOUTH for the South, EAST for the East, NORTH for the North and WEST for the west.
  • If Bender cannot reach $, then only display LOOP.
Constraints
4 ≤ C ≤ 100
4 ≤ L ≤ 100

Solution

The solution to this problem is just translating the given rules to a state machine, which outputs the appropriate action for each step. The hardest part on this problem is detecting endless loops, in other words the case when Bender will never find a solution. A pretty nice thing here is that the solution can be implemented compact with the right choice of the data structures. For that, we hold the state, including the current positon, heading and whether Bender found some beer or is inverted:

const State = {
  x: 0,
  y: 0,
  inverted: false,
  beerMode: false,
  direction: 'SOUTH'
};

Another global object is used for lookups for the directions to actual movements and vice versa:

const Directions = {
  NORTH: {y: -1, x: 0},
  EAST: {y: 0, x: 1},
  SOUTH: {y: 1, x: 0},
  WEST: {y: 0, x: -1},
  toString: function(x, y) {

    for (var dir in Directions) {
      if (Directions[dir].x === x && Directions[dir].y === y)
        return dir;
    }
  }
};

We now read in the provided data into a 2d array, mark the start position in the state and remember the two portals:

const [Y, X] = readline().split(' ').map(Number);

const Map = new Array(Y);
const Ports = [];
var Visited = {};

for (let y = 0; y < Y; y++) {
  let row = readline();
  Map[y] = new Array(X);
  for (let x = 0; x < X; x++) {
    Map[y][x] = row[x];

    if (row[x] === '@') {
      State.x = x;
      State.y = y;
    } else if (row[x] === 'T') {
      Ports.push({y: y, x: x});
    }
  }
}

In a loop that runs until we find the $ symbol, we constantly check if the current position has a special meaning. That is, are we sitting on a portal, an inverting symbol or a direction changing symbol. If we do, we modify the current state - otherwise we save the current moving direction on a list. One thing we need to take care of are endless loops. We could count the number of iterations and break at a certain point. But the question is - where is this point in the general case. That's why I decided to push the states on a list per position and if we come back to a position with the exact same setup, we know we can't exit. To break early, I decided to wrap the solution into a closure:

(function() {

  const moves = [];

  while (Map[State.y][State.x] !== '$') {

    // Have we been here already?
    if (Visited[State.y + '-' + State.x] !== undefined) {
      // Find visit with the same setup
      for (var visit of Visited[State.y + '-' + State.x]) {
        if (visit.direction === State.direction && visit.inverted === State.inverted && visit.beerMode === State.beerMode) {
          print("LOOP");
          return;
        }
      }
    } else {
      Visited[State.y + '-' + State.x] = [];
    }

    // Mark position as visited
    Visited[State.y + '-' + State.x].push({
      inverted: State.inverted,
      direction: State.direction,
      beerMode: State.beerMode
    });

    switch (Map[State.y][State.x]) {
      case 'N':
        State.direction = "NORTH";
        break;

      case 'E':
        State.direction = "EAST";
        break;

      case 'S':
        State.direction = "SOUTH";
        break;

      case 'W':
        State.direction = "WEST";
        break;

      case 'I':
        State.inverted = !State.inverted;
        break;

      case 'B':
        State.beerMode = !State.beerMode;
        break;

      case 'T':
        var which = +(State.x === Ports[0].x && State.y === Ports[0].y);
        State.x = Ports[which].x;
        State.y = Ports[which].y;
    }
    moves.push(getMove());
  }

  for (var move of moves) {
    print(move);
  }
})();

What's missing is the function getMove(), which decided where to go, based on the current state. If Bender got some beer and encounters a normal obstacle, he needs to crush this position. If we change the map, we also remove the visit history. If Bender encounters an obstacle, which is not destructible, we need to change the course. It then depends on the inverted flag, in what direction we need to probe first. We then take the first direction that works and change the position on the state finally:

function getMove() {

  var cur = Directions[State.direction];
  if (Map[State.y + cur.y][State.x + cur.x] === 'X' && State.beerMode) {
    Map[State.y + cur.y][State.x + cur.x] = ' ';
    Visited = {};
  } else if (Map[State.y + cur.y][State.x + cur.x] === 'X' && !State.beerMode || Map[State.y + cur.y][State.x + cur.x] === '#') {

    var directions;
    if (State.inverted)
      directions = [Directions.WEST, Directions.NORTH, Directions.EAST, Directions.SOUTH];
    else
      directions = [Directions.SOUTH, Directions.EAST, Directions.NORTH, Directions.WEST];

    for (var direction of directions) {
      switch (Map[State.y + direction.y][State.x + direction.x]) {
        case 'X':
        case '#':
          break;
        default:
          State.x+= direction.x;
          State.y+= direction.y;
          State.direction = Directions.toString(direction.x, direction.y);
          return State.direction;
      }
    }
  }

  State.x+= cur.x;
  State.y+= cur.y;
  return Directions.toString(cur.x, cur.y);
}

Go to overview