Robot Bounded In Circle - Leetcode Solution

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

1