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 takenumsteps.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 <= 1001 <= num <= 10^5At most 10^4 calls are made to step, getPos and getDir in total
Hints for Walking Robot Simulation II
Hint 1
After the first step the robot never leaves the border of the grid: it walks the perimeter counterclockwise forever.
Hint 2
The perimeter has
P = 2·(width + height) - 4cells, so onlynum mod Pmatters for the position. Keep the robot's index along the perimeter instead of simulating.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
- Keep
i = 0and a flagmoved = false.step(num):i = (i + num) % P,moved = true. - If
i < w: the cell is(i, 0), facing East — excepti == 0after a move, which faces South. - Else if
i < w + h - 1: cell(w - 1, i - (w - 1)), facing North. - Else if
i < 2w + h - 2: cell(w - 1 - (i - (w - 1) - (h - 1)), h - 1), facing West. - 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
numsteps one by one is O(num) a call — up to 10^9 steps in total. numa multiple ofPleaves 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.