Walking Robot Simulation II

Medium
2077.

Walking Robot Simulation II

MediumSimulationDesign

Walking Robot Simulation II is a medium coding problem on simulation.

A robot moves on a width × height grid whose cells run from (0, 0) at the bottom-left to (width - 1, height - 1) at the top-right. It starts at (0, 0) facing "East".

To take one step, the robot tries to move one cell forward in the direction it faces. If that cell is outside the grid, it instead turns 90 degrees counterclockwise and tries again, until the move succeeds.

Write the class Robot:

  • Robot(int width, int height) places the robot at (0, 0) facing East.
  • void step(int num) makes the robot take num steps.
  • int[] getPos() returns its cell as [x, y].
  • String getDir() returns the direction it faces: "North", "East", "South" or "West".

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input
["Robot","step","step","getPos","getDir","step","step","step","getPos","getDir"] [[6,3],[2],[2],[],[],[2],[1],[4],[],[]]
Output
[null,null,null,[4,0],"East",null,null,null,[1,2],"West"]
Explanation
On a 6 × 3 grid the robot walks east to (4,0), still facing East. Two more steps take it to the corner (5,0) and, after turning, up to (5,1); one step reaches (5,2), and four more turn it West along the top row to (1,2).

Example 2

Input
["Robot","getDir","step","getPos","getDir"] [[2,2],[],[8],[],[]]
Output
[null,"East",null,[0,0],"South"]
Explanation
On a 2 × 2 grid the perimeter is 4 cells, so 8 steps are two full laps back to (0,0) — but having arrived from (0,1), the robot now faces South.

Constraints

  • 2 <= width, height <= 100
  • 1 <= num <= 10^5
  • At most 10^4 calls are made to step, getPos and getDir in total
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} width
 * @param {number} height
 */
var Robot = function(width, height) {
    
};

/**
 * @param {number} num
 * @return {void}
 */
Robot.prototype.step = function(num) {
    
};

/**
 * @return {number[]}
 */
Robot.prototype.getPos = function() {
    
};

/**
 * @return {string}
 */
Robot.prototype.getDir = function() {
    
};

Sign in to run your own test cases

Sign in

Walking Robot Simulation II — Solution in Python, Java & C++

Walking Robot Simulation II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Walking Robot Simulation II is a medium coding problem on simulation.

  • Difficulty: Medium
  • Topics: Simulation
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

A robot moves on a width × height grid whose cells run from (0, 0) at the bottom-left to (width - 1, height - 1) at the top-right. It starts at (0, 0) facing "East".

To take one step, the robot tries to move one cell forward in the direction it faces. If that cell is outside the grid, it instead turns 90 degrees counterclockwise and tries again, until the move succeeds.

Write the class Robot:

  • Robot(int width, int height) places the robot at (0, 0) facing East.
  • void step(int num) makes the robot take num steps.
  • int[] getPos() returns its cell as [x, y].
  • String getDir() returns the direction it faces: "North", "East", "South" or "West".

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["Robot","step","step","getPos","getDir","step","step","step","getPos","getDir"]
[[6,3],[2],[2],[],[],[2],[1],[4],[],[]]
Output: [null,null,null,[4,0],"East",null,null,null,[1,2],"West"]
Explanation: On a 6 × 3 grid the robot walks east to (4,0), still facing East. Two more steps take it to the corner (5,0) and, after turning, up to (5,1); one step reaches (5,2), and four more turn it West along the top row to (1,2).

Example 2

Input: ["Robot","getDir","step","getPos","getDir"]
[[2,2],[],[8],[],[]]
Output: [null,"East",null,[0,0],"South"]
Explanation: On a 2 × 2 grid the perimeter is 4 cells, so 8 steps are two full laps back to (0,0) — but having arrived from (0,1), the robot now faces South.

Constraints

  • 2 <= width, height <= 100
  • 1 <= num <= 10^5
  • At most 10^4 calls are made to step, getPos and getDir in total

Hints for Walking Robot Simulation II

  1. Hint 1

    After the first step the robot never leaves the border of the grid: it walks the perimeter counterclockwise forever.

  2. Hint 2

    The perimeter has P = 2·(width + height) - 4 cells, so only num mod P matters for the position. Keep the robot's index along the perimeter instead of simulating.

  3. Hint 3

    Map the index back to a cell and a direction: the bottom row faces East, the right column North, the top row West, the left column South. The one exception is index 0, the start cell: before any move it faces East, but once the robot has moved and returned there it faces South.

How to solve Walking Robot Simulation II

The robot only ever circles the border, so its state is a position i along the perimeter of length P = 2(w + h) - 4. A step of num is i = (i + num) mod P; reading the cell and the direction is arithmetic on i.

Approach

  1. Keep i = 0 and a flag moved = false. step(num): i = (i + num) % P, moved = true.
  2. If i < w: the cell is (i, 0), facing East — except i == 0 after a move, which faces South.
  3. Else if i < w + h - 1: cell (w - 1, i - (w - 1)), facing North.
  4. Else if i < 2w + h - 2: cell (w - 1 - (i - (w - 1) - (h - 1)), h - 1), facing West.
  5. Otherwise: cell (0, h - 1 - (i - 2(w - 1) - (h - 1))), facing South.

Why it works

From (0, 0) facing East, the turn-when-blocked rule walks the bottom row east, the right column north, the top row west and the left column south, then repeats — so the sequence of cells is the perimeter in counterclockwise order and is periodic with period P. The robot faces the direction of its last move, and it only turns when the next move is blocked, so on arrival at a corner it still faces the side it came along; that is why each corner belongs to the earlier side in the mapping, and why (0, 0) faces South once it has been reached by a move.

Complexity

  • Time — O(1) per call
  • Space — O(1)

Pitfalls

  • Simulating num steps one by one is O(num) a call — up to 10^9 steps in total.
  • num a multiple of P leaves the position unchanged but can change the direction at (0, 0) from East to South.
  • The robot turns only when blocked, so at a corner it still faces the direction it arrived in.

Reference solution

Python

class Robot:

    def __init__(self, width: int, height: int):
        self.w, self.h = width, height
        self.per = 2 * (width + height) - 4  # the robot only circles the border
        self.i = 0
        self.moved = False

    def step(self, num: int) -> None:
        self.i = (self.i + num) % self.per
        self.moved = True

    def _state(self):
        w, h, i = self.w, self.h, self.i
        if i < w:
            return [i, 0], ("South" if i == 0 and self.moved else "East")
        if i < w + h - 1:
            return [w - 1, i - (w - 1)], "North"
        if i < 2 * w + h - 2:
            return [w - 1 - (i - (w - 1) - (h - 1)), h - 1], "West"
        return [0, h - 1 - (i - 2 * (w - 1) - (h - 1))], "South"

    def getPos(self) -> List[int]:
        return self._state()[0]

    def getDir(self) -> str:
        return self._state()[1]

Java

class Robot {
    private int w, h, per, i = 0; // the robot only circles the border
    private boolean moved = false;

    public Robot(int width, int height) {
        w = width;
        h = height;
        per = 2 * (width + height) - 4;
    }

    public void step(int num) {
        i = (i + num) % per;
        moved = true;
    }

    public int[] getPos() {
        if (i < w) return new int[]{i, 0};
        if (i < w + h - 1) return new int[]{w - 1, i - (w - 1)};
        if (i < 2 * w + h - 2) return new int[]{w - 1 - (i - (w - 1) - (h - 1)), h - 1};
        return new int[]{0, h - 1 - (i - 2 * (w - 1) - (h - 1))};
    }

    public String getDir() {
        if (i < w) return i == 0 && moved ? "South" : "East";
        if (i < w + h - 1) return "North";
        if (i < 2 * w + h - 2) return "West";
        return "South";
    }
}

C++

class Robot {
    int w, h, per, i = 0; // the robot only circles the border
    bool moved = false;
public:
    Robot(int width, int height) : w(width), h(height), per(2 * (width + height) - 4) {}

    void step(int num) {
        i = (i + num) % per;
        moved = true;
    }

    vector<int> getPos() {
        if (i < w) return {i, 0};
        if (i < w + h - 1) return {w - 1, i - (w - 1)};
        if (i < 2 * w + h - 2) return {w - 1 - (i - (w - 1) - (h - 1)), h - 1};
        return {0, h - 1 - (i - 2 * (w - 1) - (h - 1))};
    }

    string getDir() {
        if (i < w) return i == 0 && moved ? "South" : "East";
        if (i < w + h - 1) return "North";
        if (i < 2 * w + h - 2) return "West";
        return "South";
    }
};

JavaScript

var Robot = function(width, height) {
    this.w = width;
    this.h = height;
    this.per = 2 * (width + height) - 4; // the robot only circles the border
    this.i = 0;
    this.moved = false;
};

Robot.prototype.step = function(num) {
    this.i = (this.i + num) % this.per;
    this.moved = true;
};

Robot.prototype.state = function() {
    var w = this.w, h = this.h, i = this.i;
    if (i < w) return [[i, 0], i === 0 && this.moved ? "South" : "East"];
    if (i < w + h - 1) return [[w - 1, i - (w - 1)], "North"];
    if (i < 2 * w + h - 2) return [[w - 1 - (i - (w - 1) - (h - 1)), h - 1], "West"];
    return [[0, h - 1 - (i - 2 * (w - 1) - (h - 1))], "South"];
};

Robot.prototype.getPos = function() {
    return this.state()[0];
};

Robot.prototype.getDir = function() {
    return this.state()[1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 137 simulation problems · the whole catalogue