1041. Robot Bounded In Circle
Description
On an infinite plane, a robot initially stands at (0, 0) and faces north. Note that:
- The north direction is the positive direction of the y-axis.
- The south direction is the negative direction of the y-axis.
- The east direction is the positive direction of the x-axis.
- The west direction is the negative direction of the x-axis.
The robot can receive one of three instructions:
"G": go straight 1 unit."L": turn 90 degrees to the left (i.e., anti-clockwise direction)."R": turn 90 degrees to the right (i.e., clockwise direction).
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 is initially at (0, 0) facing the north direction. "G": move one step. Position: (0, 1). Direction: North. "G": move one step. Position: (0, 2). Direction: North. "L": turn 90 degrees anti-clockwise. Position: (0, 2). Direction: West. "L": turn 90 degrees anti-clockwise. Position: (0, 2). Direction: South. "G": move one step. Position: (0, 1). Direction: South. "G": move one step. Position: (0, 0). Direction: South. Repeating the instructions, the robot goes into the cycle: (0, 0) --> (0, 1) --> (0, 2) --> (0, 1) --> (0, 0). Based on that, we return true.
Example 2:
Input: instructions = "GG" Output: false Explanation: The robot is initially at (0, 0) facing the north direction. "G": move one step. Position: (0, 1). Direction: North. "G": move one step. Position: (0, 2). Direction: North. Repeating the instructions, keeps advancing in the north direction and does not go into cycles. Based on that, we return false.
Example 3:
Input: instructions = "GL" Output: true Explanation: The robot is initially at (0, 0) facing the north direction. "G": move one step. Position: (0, 1). Direction: North. "L": turn 90 degrees anti-clockwise. Position: (0, 1). Direction: West. "G": move one step. Position: (-1, 1). Direction: West. "L": turn 90 degrees anti-clockwise. Position: (-1, 1). Direction: South. "G": move one step. Position: (-1, 0). Direction: South. "L": turn 90 degrees anti-clockwise. Position: (-1, 0). Direction: East. "G": move one step. Position: (0, 0). Direction: East. "L": turn 90 degrees anti-clockwise. Position: (0, 0). Direction: North. Repeating the instructions, the robot goes into the cycle: (0, 0) --> (0, 1) --> (-1, 1) --> (-1, 0) --> (0, 0). Based on that, we return true.
Constraints:
1 <= instructions.length <= 100instructions[i]is'G','L'or,'R'.
Solutions
Solution 1: Simulation
We can simulate the robot's movement. Use a variable $k$ to represent the robot's direction, initialized to $0$, which means the robot is facing north. The variable $k$ can take values in the range $[0, 3]$, representing the robot facing north, west, south, and east, respectively. Additionally, we use an array $dist$ of length $4$ to record the distance the robot travels in the four directions, initialized to $[0, 0, 0, 0]$.
Traverse the instruction string $\textit{instructions}$. If the current instruction is 'L', the robot turns west, i.e., $k = (k + 1) \bmod 4$; if the instruction is 'R', the robot turns east, i.e., $k = (k + 3) \bmod 4$; otherwise, the robot moves one step in the current direction, i.e., $dist[k]++$.
If the given instruction string $\textit{instructions}$ is executed once and the robot returns to the origin, i.e., $dist[0] = dist[2]$ and $dist[1] = dist[3]$, then the robot will definitely enter a loop. This is because no matter how many times the instructions are repeated, the robot always returns to the origin, so it must enter a loop.
If the given instruction string $\textit{instructions}$ is executed once and the robot does not return to the origin, suppose the robot is at $(x, y)$ and its direction is $k$.
If $k=0$, i.e., the robot is facing north, then after executing the instructions a second time, the coordinate change is $(x, y)$; after executing the instructions a third time, the coordinate change is still $(x, y)$... Accumulating these changes, the robot will eventually reach $(n \times x, n \times y)$, where $n$ is a positive integer. Since the robot does not return to the origin, i.e., $x \neq 0$ or $y \neq 0$, it follows that $n \times x \neq 0$ or $n \times y \neq 0$, so the robot will not enter a loop;
If $k=1$, i.e., the robot is facing west, then after executing the instructions a second time, the coordinate change is $(-y, x)$; after executing the instructions a third time, the coordinate change is $(-x, -y)$; after executing the instructions a fourth time, the coordinate change is $(y, -x)$. Accumulating these coordinate changes, we find that the robot will eventually return to the origin $(0, 0)$;
If $k=2$, i.e., the robot is facing south, then after executing the instructions a second time, the coordinate change is $(-x, -y)$. Accumulating these two coordinate changes, we find that the robot will eventually return to the origin $(0, 0)$;
If $k=3$, i.e., the robot is facing east, then after executing the instructions a second time, the coordinate change is $(y, -x)$; after executing the instructions a third time, the coordinate change is $(-x, -y)$; after executing the instructions a fourth time, the coordinate change is $(-y, x)$. Accumulating these coordinate changes, we find that the robot will eventually return to the origin $(0, 0)$.
In conclusion, if the given instruction string $\textit{instructions}$ is executed once and the robot returns to the origin, or if the robot's direction is different from the initial direction, then the robot will definitely enter a loop.
The time complexity is $O(n)$, and the space complexity is $O(1)$, where $n$ is the length of the instruction string $\textit{instructions}$.
Python3
class Solution:
def isRobotBounded(self, instructions: str) -> bool:
k = 0
dist = [0] * 4
for c in instructions:
if c == 'L':
k = (k + 1) % 4
elif c == 'R':
k = (k + 3) % 4
else:
dist[k] += 1
return (dist[0] == dist[2] and dist[1] == dist[3]) or k != 0
Java
class Solution {
public boolean isRobotBounded(String instructions) {
int k = 0;
int[] dist = new int[4];
for (int i = 0; i < instructions.length(); ++i) {
char c = instructions.charAt(i);
if (c == 'L') {
k = (k + 1) % 4;
} else if (c == 'R') {
k = (k + 3) % 4;
} else {
++dist[k];
}
}
return (dist[0] == dist[2] && dist[1] == dist[3]) || (k != 0);
}
}
C++
class Solution {
public:
bool isRobotBounded(string instructions) {
int dist[4]{};
int k = 0;
for (char& c : instructions) {
if (c == 'L') {
k = (k + 1) % 4;
} else if (c == 'R') {
k = (k + 3) % 4;
} else {
++dist[k];
}
}
return (dist[0] == dist[2] && dist[1] == dist[3]) || k;
}
};
Go
func isRobotBounded(instructions string) bool {
dist := [4]int{}
k := 0
for _, c := range instructions {
if c == 'L' {
k = (k + 1) % 4
} else if c == 'R' {
k = (k + 3) % 4
} else {
dist[k]++
}
}
return (dist[0] == dist[2] && dist[1] == dist[3]) || k != 0
}
TypeScript
function isRobotBounded(instructions: string): boolean {
const dist: number[] = new Array(4).fill(0);
let k = 0;
for (const c of instructions) {
if (c === 'L') {
k = (k + 1) % 4;
} else if (c === 'R') {
k = (k + 3) % 4;
} else {
++dist[k];
}
}
return (dist[0] === dist[2] && dist[1] === dist[3]) || k !== 0;
}