We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Robot Bounded In Circle

Difficulty: Medium

Problem Description

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), and "R" (turn 90 degrees to the right). The robot performs the instructions given in order and repeats them forever. Return true if there exists a circle in the plane such that the robot never leaves the circle.

Key Insights

  • The robot's movement is determined by its current direction and the given instructions.
  • The robot can change its direction with "L" and "R" instructions, which can lead to cyclical movement.
  • If after one complete set of instructions the robot is back at the origin or facing any direction other than north, it will be bounded in a circle.
  • The possible final directions after a series of turns can be categorized to determine if the robot will remain in a bounded area.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the instructions string, as we need to process each instruction once. Space Complexity: O(1), as we are using a fixed amount of space regardless of the input size.

Solution

To determine if the robot is bounded in a circle, we simulate its movements based on the instructions. The robot's position is tracked using coordinates (x, y) which start at (0, 0). The direction the robot faces can be represented as an index in a list of directions. Each instruction modifies either the position or the direction. After processing all instructions, we check if the robot is at the origin or not facing north. If either condition is true, the robot is bounded.

Code Solutions

def isRobotBounded(instructions: str) -> bool:
    # Directions are represented as (dx, dy) for North, East, South, West
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    x, y, direction = 0, 0, 0  # Starting at (0, 0) facing North

    for instruction in instructions:
        if instruction == 'G':
            x += directions[direction][0]
            y += directions[direction][1]
        elif instruction == 'L':
            direction = (direction - 1) % 4  # Turn left
        elif instruction == 'R':
            direction = (direction + 1) % 4  # Turn right

    # Check if the robot is at the origin or not facing North
    return (x == 0 and y == 0) or direction != 0
← Back to All Questions