Codingame Solution: Bender - Episode 1

Original Problem

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

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