robot-room-cleaner.js

/* Robot Room Cleaner
 * 
 * [Hard] [AC:65.6% 27.9K of 42.6K]
 * [filetype:javascript]
 * 
 * Given a robot cleaner in a room modeled
 * as a grid.
 * 
 * Each cell in the grid can be empty or
 * blocked.
 * 
 * The robot cleaner with 4 given APIs can
 * move forward, turn left or turn right.
 * Each turn it made is 90 degrees.
 * 
 * When it tries to move into a blocked
 * cell, its bumper sensor detects the
 * obstacle and it stays on the current
 * cell.
 * 
 * Design an algorithm to clean the entire
 * room using only the 4 given APIs shown
 * below.
 * 
 * interface Robot {
 * 
 *   // returns true if next cell is open
 *   and robot moves into the cell.
 * 
 *   // returns false if next cell is
 *   obstacle and robot stays on the
 *   current cell.
 * 
 *   boolean move();
 * 
 *   // Robot will stay on the same cell
 *   after calling turnLeft/turnRight.
 * 
 *   // Each turn will be 90 degrees.
 * 
 *   void turnLeft();
 * 
 *   void turnRight();
 * 
 *   // Clean the current cell.
 * 
 *   void clean();
 * 
 * }
 * 
 * Example:
 * 
 * Input:
 * 
 * room = [
 * 
 *   [1,1,1,1,1,0,1,1],
 * 
 *   [1,1,1,1,1,0,1,1],
 * 
 *   [1,0,1,1,1,1,1,1],
 * 
 *   [0,0,0,1,0,0,0,0],
 * 
 *   [1,1,1,1,1,1,1,1]
 * 
 * ],
 * 
 * row = 1,
 * 
 * col = 3
 * 
 * Explanation:
 * 
 * All grids in the room are marked by
 * either 0 or 1.
 * 
 * 0 means the cell is blocked, while 1
 * means the cell is accessible.
 * 
 * The robot initially starts at the
 * position of row=1, col=3.
 * 
 * From the top left corner, its position
 * is one row below and three columns
 * right.
 * 
 * Notes:
 * 
 * The input is only given to initialize
 * the room and the robot's position
 * internally. You must solve this problem
 * "blindfolded". In other words, you must
 * control the robot using only the
 * mentioned 4 APIs, without knowing the
 * room layout and the initial robot's
 * position.
 * 
 * The robot's initial position will
 * always be in an accessible cell.
 * 
 * The initial direction of the robot will
 * be facing up.
 * 
 * All accessible cells are connected,
 * which means the all cells marked as 1
 * will be accessible by the robot.
 * 
 * Assume all four edges of the grid are
 * all surrounded by wall.
 * 
 * [End of Description] */
/**
 * // This is the robot's control interface.
 * // You should not implement it, or speculate about its implementation
 * function Robot() {
 *
 *     // Returns true if the cell in front is open and robot moves into the cell.
 *     // Returns false if the cell in front is blocked and robot stays in the current cell.
 *     @return {boolean}
 *     this.move = function() {
 *         ...
 *     };
 *
 *     // Robot will stay in the same cell after calling turnLeft/turnRight.
 *     // Each turn will be 90 degrees.
 *     @return {void}
 *     this.turnLeft = function() {
 *         ...
 *     };
 * 
 *     // Robot will stay in the same cell after calling turnLeft/turnRight.
 *     // Each turn will be 90 degrees.
 *     @return {void} 
 *     this.turnRight = function() {
 *         ...
 *     };
 *
 *     // Clean the current cell.
 *     @return {void}
 *     this.clean = function() {
 *         ...
 *     };
 * };
 */
/**
 *
 *   [1,1,1,1,1,0,1,1],
 *   [1,1,1,1,1,0,1,1],
 *   [1,0,1,1,1,1,1,1],
 *   [0,0,0,1,0,0,0,0],
 *   [1,1,1,1,1,1,1,1]
 * 
/**
 * @param {Robot} robot
 * @return {void}
 */
var cleanRoom = function(robot) {
  let dir = 0;

  const cleaned = {};
  const flipDir = d => (d + 2) % 4;
  const turnRight = () => { robot.turnRight(); dir = (dir + 1) % 4; };
  const setDir = (newDir) => { while (dir !== newDir) turnRight(); };

  const recurse = (x, y, moveDir) => {
    robot.clean();

    if (cleaned[x + " : " + y] === true) return;
    moveDir >= 0 && setDir(moveDir);

    if (moveDir >= 0 && !robot.move()) {
      return;
    } else {
      cleaned[x + " : " + y] = true;

      // visit all non-clean adjacent squares
      recurse(x, y - 1, 0);
      recurse(x + 1, y, 1);
      recurse(x, y + 1, 2);
      recurse(x - 1, y, 3);
    }
    
    // move back to our last square
    moveDir >= 0 && setDir(flipDir(moveDir));
    moveDir >= 0 && robot.move();
  };

  recurse(0, 0, -1);
};