Solution For Robot Bounded In Circle

Problem statement:

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.

Solution:

To solve this problem, we need to understand the movement of the robot and how it affects its location on the plane. The robot’s starting position is (0,0), and it always moves in a straight line to its new position based on the instructions “G”. When the robot turns left or right, its facing direction changes but its position remains the same.

Let’s consider the robot’s movement in terms of coordinates. We can use (x,y) to represent its position, and (dx, dy) to represent its facing direction. Initially, the robot is at (0,0) and facing north, so (dx, dy) = (0,1). When the robot turns left or right, we can update the facing direction as follows:

If the robot turns left, its new facing direction is (-dy, dx)
If the robot turns right, its new facing direction is (dy, -dx)

These formulas allow us to keep track of the robot’s position on the plane as it moves around.

Now, let’s consider the possibility of the robot getting stuck in a circle. If the robot returns to its starting position after some set of instructions, it will keep repeating the same set of instructions and will continue to return to its starting position. This means that if the robot moves in a complete circle, it will reach its starting position after moving 4 times (one complete rotation is 4 movements).

In order for the robot to be bounded in a circle, its facing direction must be the same as its starting direction after some set of instructions. If the facing direction is different, the robot will eventually move away from its starting position and will not return.

As we can see, the robot’s facing direction depends on the number of left and right turns it has made so far. If the number of left turns is the same as the number of right turns, the facing direction will be the same as the starting direction (north). If the difference between left turns and right turns is a multiple of 4, the facing direction will be the same as the starting direction after 4 rotations (north). If the difference between left turns and right turns is odd, the facing direction will be the opposite of the starting direction after 2 rotations (south).

Using these observations, we can write a simple algorithm to check if the robot is bounded in a circle:

Initialize the robot’s position to (0,0) and facing direction to (0,1).
Count the number of left turns and right turns made by the robot.
If the difference between left turns and right turns is a multiple of 4 or the number of left turns and right turns is equal, return true (robot is bounded in a circle).
If the difference between left turns and right turns is odd, return false (robot will not return to starting position).
Otherwise, the robot will eventually move away from starting position and will not return.

This algorithm requires O(n) time where n is the length of the instruction string, and O(1) space.

Python code for the solution:

class Solution:
def isRobotBounded(self, instructions: str) -> bool:
x, y, dx, dy = 0, 0, 0, 1 # initial position and facing direction
for i in instructions:
if i == ‘L’:
dx, dy = -dy, dx # update facing direction for left turn
elif i == ‘R’:
dx, dy = dy, -dx # update facing direction for right turn
else:
x, y = x+dx, y+dy # update position for straight move
return (dx, dy) != (0, 1) or (x, y) == (0, 0) # check if robot is bounded in a circle

Step by Step Implementation For Robot Bounded In Circle

class Solution {
    public boolean isRobotBounded(String instructions) {
        int[][] dirs={{0,1}, {1,0}, {0,-1}, {-1,0}}; //array of directions: right, up, left, down
        int x=0, y=0, i=0; //starting coordinates (0,0) and starting direction index
        for(char c : instructions.toCharArray()){
            if(c=='R') i=(i+1)%4; //change direction to the right
            else if(c=='L') i=(i+3)%4; //change direction to the left
            else{ //c is 'G'
                x+=dirs[i][0]; //move in direction specified by i
                y+=dirs[i][1];
            }
        }
        return x==0 && y==0 || i>0; //if robot returns to starting point or is not facing north
    }
}

def isRobotBounded(instructions):
    
    # set starting coordinates for the robot
    x, y, d = 0, 0, 0
    
    # loop through instructions
    for i in instructions:
        
        # if instruction is 'G', move the robot in the current direction
        if i == 'G':
            if d == 0:
                y += 1
            elif d == 1:
                x += 1
            elif d == 2:
                y -= 1
            else:
                x -= 1
                
        # if instruction is 'L', change the direction of the robot to the left
        elif i == 'L':
            d = (d + 3) % 4
            
        # if instruction is 'R', change the direction of the robot to the right
        else:
            d = (d + 1) % 4
            
    # check if robot is back to starting position        
    return (x == 0 and y == 0) or (d != 0)

var isRobotBounded = function(instructions) {
    // your code goes here
};

class Solution {
public:
    bool isRobotBounded(string instructions) {
        int x = 0, y = 0, i = 0, d[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        for (char &c : instructions) {
            if (c == 'R') i = (i + 1) % 4;
            if (c == 'L') i = (i + 3) % 4;
            x += d[i][0]; y += d[i][1];
        }
        return x == 0 && y == 0 || i > 0;
    }
};

using System; 
  
class GFG { 
      
// function to check if the robot 
// is in a circle or not 
static bool isRobotBounded(string instructions) 
{ 
      
    // Initialize starting point 
    // for robot as (0, 0) and 
    // direction as N North 
    int x = 0, y = 0; 
    int dir = 0; 
  
    // Traverse the instruction string 
    for (int i = 0; i < instructions.Length; i++) { 
              
        // Find current move 
        char ch = instructions[i]; 
              
        // If 'R', then change direction 
        if (ch == 'R') 
            dir = (dir + 1) % 4; 
              
        // If 'L', then change direction 
        else if (ch == 'L') 
            dir = (4 + dir - 1) % 4; 
              
        // If 'G', then perform a step 
        else { 
                  
            // If direction is North, then 
            // increment y 
            if (dir == 0) 
                y++; 
                  
            // If direction is East, then 
            // increment x 
            else if (dir == 1) 
                x++; 
                  
            // If direction is South, then 
            // decrement y 
            else if (dir == 2) 
                y--; 
                  
            // If direction is West, then 
            // decrement x 
            else if (dir == 3) 
                x--; 
        } 
    } 
      
    // If robot comes back to 
    // (0, 0), then it is in a circle 
    return (x == 0 && y == 0); 
} 
  
// Driver code 
public static void Main() 
{ 
    string instructions = "GGLLGG"; 
    if (isRobotBounded(instructions)) 
        Console.Write("True"); 
    else
        Console.Write("False"); 
} 
} 
  
// This code is contributed by Smitha Dinesh Semwal