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.
Example 3:
Input: instructions = "GL" Output: true Explanation: The robot moves from (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ...
Constraints:
1 <= instructions.length <= 100instructions[i]is'G','L'or,'R'.
Solution:
The robot’s trajectory attractor is a set of trajectories toward which a system tends to evolve. The question may sound a bit theoretical – is this attractor is limited or not. In other words, if there exists a circle in the plane such that the robot never leaves the circle.
| Diverging Trajectory | Limit Cycle Trajectory |
|---|---|
 |  |
Figure 1. Diverging Trajectory vs Limit Cycle Trajectory.
Why is it interesting to know? There is a bunch of practical problems related to topology, networks planning, and password brute-forcing. For all these problems, the first thing to understand is do we work within a limited space or the behavior of our system could drastically diverge at some point?
| Diverging Trajectory | Limit Cycle Trajectory |
|---|---|
 |  |
Figure 2. Diverging Trajectory vs Limit Cycle Trajectory.
Draw some trajectories
Here is a Jupiter notebook used to draw all figures in this article. Do not hesitate to play with it in local or on the online platforms. Drawing different trajectories might help to notice some patterns.
Approach 1: One Pass
Intuition
This solution is based on two facts about the limit cycle trajectory.
- After at most 4 cycles, the limit cycle trajectory returns to the initial point
x = 0, y = 0. That is related to the fact that 4 directions (north, east, south, west) define the repeated cycles’ plane symmetry [proof].
| Ex. 1: Trajectory 1 | Ex. 2: Trajectory 2 |
|---|---|
 |  |
Figure 3. After 4 cycles the limit cycle trajectory returns to the initial point x = 0, y = 0.
- We do not need to run 4 cycles to identify the limit cycle trajectory. One cycle is enough. There could be two situations here.
- First, if the robot returns to the initial point after one cycle, that’s the limit cycle trajectory.
- Second, if the robot doesn’t face north at the end of the first cycle, that’s the limit cycle trajectory. Once again, that’s the consequence of the plane symmetry for the repeated cycles [proof].
| Ex. 1: Trajectory 1 | Ex. 2: Trajectory 2 |
|---|---|
 |  |
Figure 4. If at the end of one cycle the robot doesn’t face north, that’s the limit cycle trajectory.
Algorithm
- Let’s use numbers from 0 to 3 to mark the directions:
north = 0,east = 1,south = 2,west = 3. In the arraydirectionswe could store corresponding coordinates changes, i.e.directions[0]is to go north,directions[1]is to go east,directions[2]is to go south, anddirections[3]is to go west. - The initial robot position is in the center
x = y = 0, facing northidx = 0. - Now everything is ready to iterate over the instructions.
- If the current instruction is
R, i.e. to turn on the right, the next direction isidx = (idx + 1) % 4. Modulo here is needed to deal with the situation – facing west,idx = 3, turn to the right to face north,idx = 0. - If the current instruction is
L, i.e. to turn on the left, the next direction could written in a symmetric wayidx = (idx - 1) % 4. That means we have to deal with negative indices. A more simple way is to notice that 1 turn to the left = 3 turns to the right:idx = (idx + 3) % 4. - If the current instruction is to move, we simply update the coordinates:
x += directions[idx][0],y += directions[idx][1].
- If the current instruction is
- After one cycle we have everything to decide. It’s a limit cycle trajectory if the robot is back to the center:
x = y = 0or if the robot doesn’t face north:idx != 0.
Java:
class Solution {
public boolean isRobotBounded(String instructions) {
// north = 0, east = 1, south = 2, west = 3
int[][] directions = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
// Initial position is in the center
int x = 0, y = 0;
// facing north
int idx = 0;
for (char i : instructions.toCharArray()) {
if (i == 'L')
idx = (idx + 3) % 4;
else if (i == 'R')
idx = (idx + 1) % 4;
else {
x += directions[idx][0];
y += directions[idx][1];
}
}
// after one cycle:
// robot returns into initial position
// or robot doesn't face north
return (x == 0 && y == 0) || (idx != 0);
}
}Python3
class Solution:
def isRobotBounded(self, instructions: str) -> bool:
# north = 0, east = 1, south = 2, west = 3
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
# Initial position is in the center
x = y = 0
# facing north
idx = 0
for i in instructions:
if i == "L":
idx = (idx + 3) % 4
elif i == "R":
idx = (idx + 1) % 4
else:
x += directions[idx][0]
y += directions[idx][1]
# after one cycle:
# robot returns into initial position
# or robot doesn't face north
return (x == 0 and y == 0) or idx != 0Appendix: Mathematical Proof
Let’s provide a strict mathematical proof.
If the robot doesn’t face north at the end of the first cycle, then that’s the limit cycle trajectory.
First, let’s check which direction the robot faces after 4 cycles.
Let’s use numbers from 0 to 3 to mark the directions: north = 0, east = 1, south = 2, west = 3. After one cycle the robot is facing direction k != 0.
After 4 cycles, the robot faces direction (k * 4) % 4 = 0, i.e. after 4 cycles, the robot is always facing north.
Second, let’s find the robot coordinates after 4 cycles.
The robot initial coordinates are x = y = 0. After one cycle, the new coordinates are x_1 = x + \Delta xx1=x+Δx, y_1 = y + \Delta yy1=y+Δy, where both \Delta xΔx and \Delta yΔy could be positive or negative.
Let’s consider four situations.
- After one cycle, the robot faces north.
Then here is what we have after 4 cycles:
x_4 = x + \Delta x + \Delta x – \Delta x + \Delta x = x + 4 \Delta xx4=x+Δx+Δx−Δx+Δx=x+4Δx
y_4 = y + \Delta y + \Delta y + \Delta y + \Delta y = y + 4 \Delta yy4=y+Δy+Δy+Δy+Δy=y+4Δy
- After one cycle, the robot faces east.
Then here is what we have after 4 cycles:
x_4 = x + \Delta x + \Delta y – \Delta x – \Delta y = xx4=x+Δx+Δy−Δx−Δy=x
y_4 = y + \Delta y – \Delta x – \Delta y + \Delta x = yy4=y+Δy−Δx−Δy+Δx=y
- After one cycle, the robot faces south.
Then here is what we have after 4 cycles:
x_4 = x + \Delta x – \Delta x + \Delta x – \Delta x = xx4=x+Δx−Δx+Δx−Δx=x
y_4 = y + \Delta y – \Delta y + \Delta y – \Delta y = yy4=y+Δy−Δy+Δy−Δy=y
- After one cycle, the robot faces west.
Then here is what we have after 4 cycles:
x_4 = x + \Delta x – \Delta y – \Delta x + \Delta y = xx4=x+Δx−Δy−Δx+Δy=x
y_4 = y + \Delta y + \Delta x – \Delta y – \Delta x = yy4=y+Δy+Δx−Δy−Δx=y
Hence, if the robot doesn’t face north at the end of the first cycle, then after 4 cycles, the robot is back to the initial coordinates and faces north.
The following statement is a straight consequence.
After at most 4 cycles, the limit cycle trajectory returns to the initial point.
the solution in the discussion that helps to understand
# Solution 1: O(n) time complexity and o(1) space complexity
class Solution:
def isRobotBounded(self, instructions: str) -> bool:
# initial poition
x = y = 0
# intially facing north
direction = 0
# 0 = north, 1 = east, 2 = south, 3 = west
# With a move (G) in any direction, you will go 1 unit.
# So you need to add 1 unit with x or y depending on
# which direction you are going. For example,
# if you go north from (x,y), then new position would be
# (x, y+1) which is you get by x = x+0, y = y+1.
# Now think about how you can get new position for other direction
# So creating a dictionary with directions as keys and the
# amount we need to add with x and y while we go for 1 unit
# as value.
possible_moves = {0: [0,1], 1: [1,0], 2: [0,-1], 3: [-1,0]}
# Now the idea is if after executing the instructions, if you
# get your final position at (0,0) or if you are not facing north
# direction, that means you will be in circle. Not facing north
# direction means, as you can repeat the instructions, if you are
# not facing north after 1st execution of the instructions, just
# repeat 3 more times of the same instructions, you will see
# yourself at the origin. Think about with 'GL' or 'GR'
# instructions as an example. With instruction 'GLGR', you
# can't be back at origin, no matter how many times you repeat.
for instruction in instructions:
# turing left means, you will get the same direction
# if you turn right 3 times. modulo beacuse we have
# only 4 directions to consider.
if instruction == 'L':
direction = (direction + 3)% 4
elif instruction == 'R':
direction = (direction + 1)% 4
# If we see 'G' means we need to go 1 unit and
# change x or y value according to the direction
# we are going. By this we will get new position.
else:
x = x + possible_moves[direction][0]
y = y + possible_moves[direction][1]
# Finally, if you get your final position at (0,0) or if you
# are not facing north direction, that means you will be
# in circle.
return (x==0 and y ==0) or direction !=0class Solution(object):
def isRobotBounded(self, instructions):
# north = 0, east = 1, south = 2, west = 3
directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]
# Initial position is in the center
x = y = 0
# facing north
idx = 0
for i in instructions:
if i == "L":
idx = (idx + 3) % 4
elif i == "R":
idx = (idx + 1) % 4
else:
x += directions[idx][0]
y += directions[idx][1]
# after one cycle:
# robot returns into initial position
# or robot doesn't face north
return (x == 0 and y == 0) or idx != 0