function getCommands(field, power) {
  var myField = new Field(field);
  var robby = new Robot(myField.startPoint, power, Directions.NORTH, []);
  myField.prettyPrint();

  var winnerRobots = [];
  var explored = new PathSet();
  var frontier = new PathSet();

  // initial frontier value
  frontier.add(robby.getState(), robby);

 while(frontier.states.length) {
    var fs = frontier.states.shift();
    consume(fs);
  }

  function consume(fs) { // fs for frontier state
    // 1 transfer to explored
    explored.add(fs.state, fs.robot);
    // 2 check solution
    if(fs.state.isPointEqual(myField.targetPoint)) {
      winnerRobots.push(fs.robot);
      return;
    }
    // 3 check power level
    if(fs.robot.power === 0) {
      return;
    }
    // 4 discover options, add to frontier if new
    var options = fs.robot.discoverOptions(myField);
    options.forEach(function(opt) {
      var resultState = fs.robot.predictState(opt, myField);
      if(!frontier.exists(resultState) && !explored.exists(resultState)) {
        var roboSpawn = fs.robot.clone();
        roboSpawn.executeCommand(opt, myField);
        frontier.add(resultState, roboSpawn);
      }
    });

  }

  console.log('The winners are:');
  console.log(winnerRobots);
  if(!winnerRobots.length) {
    return [];
  }
  return winnerRobots.sort((r1, r2) => r2.power - r1.power)[0].commandLog;
}

var Commands = {
  "TURN_RIGHT": "r", // turn right by 90°
  "TURN_LEFT": "l", // turn left by 90°
  "MOVE_FORWARDS": "f" // move one field forwards into current direction
};

var Fields = {
  "WALKABLE": ".", // Robby may walk on this
  "BLOCKED": "#", // Robby must not walk on this
  "START": "S", // Robby is starting here, he may also walk here
  "TARGET": "T" // The target cell, Robby has to reach
};

var Directions = {
  "NORTH": 0,
  "EAST": 1,
  "SOUTH": 2,
  "WEST": 3
}

function State(x, y, d) {
  this.x = x;
  this.y = y;
  this.d = d;
}

State.prototype = {
  isEqual: function(otherState) {
    return this.x === otherState.x && this.y === otherState.y && this.d === otherState.d;
  },
  isPointEqual: function(point) {
    return this.x === point.x && this.y === point.y;
  }
}

function PathSet(states) {
  this.states = states || [];
}

PathSet.prototype = {
  add: function(state, robot) {
    if(!this.exists(state)) {
      this.states.push({state: state, robot: robot});
    }
  },
  exists: function(state) {
    return this.states.filter((s) => {
      return state.isEqual(s.state);
    }).length;
  }
}

function Field(field) {
  this.size = Math.sqrt(field.length);
  this.square = [];
  for(var i = 0; i < this.size; i++) {
    this.square.push([]);
    for(var j = 0; j < this.size; j++) {
      this.square[i][j] = field[this.size * i + j];
      if(this.square[i][j] === Fields.START) {
        this.startPoint = { x: i, y: j }
      }
      if(this.square[i][j] === Fields.TARGET) {
        this.targetPoint = { x: i, y: j }
      }
    }
  }
}

Field.prototype = {
  prettyPrint: function() {
    console.log('\n');
    for(var i = 0; i < this.size; i++) {
      console.log(this.square[i].join(' '));
      console.log('\n');
    }
    console.log('\n');
  }

}

function Robot(startPoint, power, direction, commandLog) {
  this.x = startPoint.x;
  this.y = startPoint.y;
  this.power = power;
  this.direction = direction;
  this.commandLog = [...commandLog];
}

Robot.prototype = {
  turnRight: function() {
    this.direction++;
    if(this.direction > Directions.WEST) {
      this.direction = Directions.NORTH;
    }
    this.power--;
    this.commandLog.push(Commands.TURN_RIGHT);
  },
  turnLeft: function() {
    this.direction--;
    if(this.direction < Directions.NORTH) {
      this.direction = Directions.WEST;
    }
    this.power--;
    this.commandLog.push(Commands.TURN_LEFT);
  },
  moveForward: function(field) {
    if(this.canWalk(field)) {
      var np = this.getNextPoint(field);
      this.x = np.x;
      this.y = np.y;
      this.power--;
      this.commandLog.push(Commands.MOVE_FORWARDS);
    }
  },
  canWalk: function(field) {
    var np = this.getNextPoint();
    var outOfSquare = np.x < 0 || np.y < 0 || np.x >= field.size || np.y>= field.size;
    if(outOfSquare) {
      return false;
    }
    var isBlocked = (field.square[np.x][np.y] === Fields.BLOCKED);
    return !isBlocked;
  },
  getNextPoint: function() {
    var p = {};
    if(this.direction === Directions.NORTH) {
      p.x = this.x - 1;
      p.y = this.y;
    }
    else if(this.direction === Directions.EAST) {
      p.x = this.x;
      p.y = this.y + 1;
    }
    else if(this.direction === Directions.SOUTH) {
      p.x = this.x + 1;
      p.y = this.y;
    }
    else if(this.direction === Directions.WEST) {
      p.x = this.x;
      p.y = this.y - 1;
    }
    return p;
  },
  getState: function() {
    return new State(this.x, this.y, this.direction);
  },
  discoverOptions: function(field) {
    var options = [Commands.TURN_LEFT, Commands.TURN_RIGHT];
    if(this.canWalk(field)) {
      options.unshift(Commands.MOVE_FORWARDS);
    }
    return options;
  },
  predictState: function(command, field) {
    var clone = this.clone();
    if(command === Commands.TURN_LEFT) {
      clone.turnLeft();
    }
    else if(command === Commands.TURN_RIGHT) {
      clone.turnRight();
    }
    else if(command === Commands.MOVE_FORWARDS) {
      clone.moveForward(field);
    }
    return clone.getState();
  },
  executeCommand: function(command, field) {
    if(command === Commands.TURN_LEFT) {
      this.turnLeft();
    }
    else if(command === Commands.TURN_RIGHT) {
      this.turnRight();
    }
    else if(command === Commands.MOVE_FORWARDS) {
      this.moveForward(field);
    }
  },
  clone: function() {
    return new Robot({ x: this.x, y: this.y }, this.power, this.direction, this.commandLog);
  }
}