# 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