Robot Bounded In Circle

In this problem, we want to determine whether a robot, following a given sequence of instructions repeatedly, will move in a bounded circle.

Solution

To find if the robot is bounded by a circle, we need to observe if it eventually returns to the starting position or faces any other direction except north after executing the instructions once. If either of these conditions is met, it is guaranteed that repeating the instructions will keep the robot bounded in a circle.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def isRobotBounded(self, instructions: str) -> bool:
        # Define initial direction (0: north, 1: east, 2: south, 3: west)
        direction = 0

        # Define the changes in x and y coordinates for each direction
        moves = [(0, 1), (1, 0), (0, -1), (-1, 0)]

        # Initial position of the robot
        x, y = 0, 0

        # Loop through the instructions
        for instruction in instructions:
            if instruction == 'G':
                dx, dy = moves[direction]
                x += dx
                y += dy
            elif instruction == 'L':
                direction = (direction - 1) % 4
            elif instruction == 'R':
                direction = (direction + 1) % 4

        # If the robot returns to (0,0) or faces any other direction than north, it's bounded
        return (x, y) == (0, 0) or direction != 0

Explanation

• direction represents the current facing direction of the robot, with 0 for north, 1 for east, 2 for south, and 3 for west.
• moves is a list containing the changes in x and y coordinates corresponding to each direction.
• We iterate through the instructions and update the robot’s position and direction accordingly.
• Finally, we check if the robot has returned to the starting position (0, 0) or if it faces a direction other than north. If either condition is met, we return True, meaning the robot is bounded in a circle. Otherwise, we return False.

The time complexity of this solution is O(n), where n is the length of the instructions, and the space complexity is O(1).