{x}
blog image

Robot Bounded In Circle

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 <= 100
  • instructions[i] is 'G', 'L' or, 'R'.

Solution Explanation

This problem asks whether a robot, following a set of instructions, will eventually be bounded in a circle. The robot starts at (0,0) facing north and can move in four directions: North, South, East, and West. The instructions are "G" (go straight), "L" (turn left), and "R" (turn right).

The key insight is that the robot is bounded in a circle if and only if one of two conditions is met after executing the instructions once:

  1. The robot returns to its starting position (0,0).
  2. The robot does not end up facing North.

The solution efficiently checks these conditions without explicitly simulating the robot's entire path.

Approach

The code uses an array dist of size 4 to keep track of the distances traveled in each direction (North, East, South, West, represented by indices 0, 1, 2, 3 respectively). A variable k represents the current direction the robot is facing (0 for North, 1 for East, 2 for South, 3 for West).

The code iterates through the instructions:

  • 'G': Increment the distance traveled in the current direction (dist[k]).
  • 'L': Turn left by changing k to (k + 1) % 4.
  • 'R': Turn right by changing k to (k + 3) % 4. (Adding 3 is equivalent to subtracting 1 modulo 4)

After processing all instructions:

  • The robot is bounded if the distances in opposite directions are equal (dist[0] == dist[2] and dist[1] == dist[3]). This guarantees the robot will eventually return to (0,0).
  • Alternatively, if the final direction k is not 0 (North), then the robot is not moving infinitely in a straight line and therefore must eventually be bounded.

Time and Space Complexity Analysis

Time Complexity: O(n), where n is the length of the instructions string. The code iterates through the instructions once.

Space Complexity: O(1). The space used by dist and k is constant regardless of the input size.

Code Explanation (Python Example)

class Solution:
    def isRobotBounded(self, instructions: str) -> bool:
        k = 0  # Current direction (0: North, 1: East, 2: South, 3: West)
        dist = [0] * 4  # Distances traveled in each direction
 
        for c in instructions:
            if c == 'L':
                k = (k + 1) % 4  # Turn left
            elif c == 'R':
                k = (k + 3) % 4  # Turn right
            else:
                dist[k] += 1  # Move forward
 
        # Check if bounded
        return (dist[0] == dist[2] and dist[1] == dist[3]) or k != 0

The other language examples follow the same logic, just with syntax variations specific to each language. The core algorithm remains consistent across all implementations.