On an infinite plane, a robot initially stands at (0, 0) and faces north. The robot can receive one of three instructions:
"G": go straight 1 unit;
"L": turn 90 degrees to the left;
"R": turn 90 degrees to the right.
The robot performs the instructions given in order, and repeats them forever.
Return true if and only if there exists a circle in the plane such that the robot never leaves the circle.
Example 1:
**Input:** instructions = "GGLLGG"
**Output:** true
**Explanation:** The robot moves from (0,0) to (0,2), turns 180 degrees, and then returns to (0,0).
When repeating these instructions, the robot remains in the circle of radius 2 centered at the origin.
Example 2:
**Input:** instructions = "GG"
**Output:** false
**Explanation:** The robot moves north indefinitely.
Mostly a brain teaser: return true if after executing instuctions, 1) back to stating point; 2) not facing up. See proof below.
class Solution {
public boolean isRobotBounded(String instructions) {
int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
int x = 0, y = 0;
int d = 0; // d means facing direction, dirs[0] means if we meet a "G", then x += 0 and y += 1
for (int i = 0; i < instructions.length(); i++) {
char c = instructions.charAt(i);
if (c == 'R') {
// Find next direction, represented as index in array dirs.
d = (d + 1) % 4;
} else if (c == 'L') {
d = (d + 3) % 4; // turn left == turn right 3 times
} else {
x += dirs[d][0];
y += dirs[d][1];
}
}
return x == 0 && y == 0 || d != 0;
}
}
// O(N) time, O(1) space
Try to prove with math representation:
Let's say the robot starts with facing up. It moves [dx, dy] by executing the instructions once.
If the robot starts with facing
right, it moves [dy, -dx];
left, it moves [-dy, dx];
down, it moves [-dx, -dy]
If the robot faces right (clockwise 90 degree) after executing the instructions once,
the direction sequence of executing the instructions repeatedly will be up -> right -> down -> left -> up
The resulting move is [dx, dy] + [dy, -dx] + [-dx, -dy] + [-dy, dx] = [0, 0] (back to the original starting point)
All other possible direction sequences:
up -> left -> down -> right -> up. The resulting move is [dx, dy] + [-dy, dx] + [-dx, -dy] + [dy, -dx] = [0, 0]
up -> down -> up. The resulting move is [dx, dy] + [-dx, -dy] = [0, 0]
up -> up. The resulting move is [dx, dy]