Robot Bounded In Circle

medium math simulation

Problem

A robot starts at the origin facing north. It executes a string of instructions (G = go 1, L = turn left, R = turn right) repeatedly. Return true if its trajectory is bounded (stays in a circle).

Inputinstructions = "GGLLGG"

Outputtrue

After one cycle the robot returns to (0, 0). It will loop forever within a bounded region.

instructions (G / L / R)

def is_robot_bounded(instructions):
    x, y, dx, dy = 0, 0, 0, 1
    for c in instructions:
        if c == 'G':
            x, y = x + dx, y + dy
        elif c == 'L':
            dx, dy = -dy, dx
        else:
            dx, dy = dy, -dx
    return (x == 0 and y == 0) or (dx, dy) != (0, 1)

function isRobotBounded(instructions) {
  let x = 0, y = 0, dx = 0, dy = 1;
  for (const c of instructions) {
    if (c === 'G') { x += dx; y += dy; }
    else if (c === 'L') { [dx, dy] = [-dy, dx]; }
    else { [dx, dy] = [dy, -dx]; }
  }
  return (x === 0 && y === 0) || dx !== 0 || dy !== 1;
}

class Solution {
    public boolean isRobotBounded(String instructions) {
        int x = 0, y = 0, dx = 0, dy = 1;
        for (char c : instructions.toCharArray()) {
            if (c == 'G') { x += dx; y += dy; }
            else if (c == 'L') { int t = dx; dx = -dy; dy = t; }
            else { int t = dx; dx = dy; dy = -t; }
        }
        return (x == 0 && y == 0) || dx != 0 || dy != 1;
    }
}

bool isRobotBounded(string instructions) {
    int x = 0, y = 0, dx = 0, dy = 1;
    for (char c : instructions) {
        if (c == 'G') { x += dx; y += dy; }
        else if (c == 'L') { int t = dx; dx = -dy; dy = t; }
        else { int t = dx; dx = dy; dy = -t; }
    }
    return (x == 0 && y == 0) || dx != 0 || dy != 1;
}

Explanation

The clever insight is that we only need to simulate one round of the instructions, not run them forever. After a single pass we just look at where the robot ended up and which way it faces.

We track a position (x, y) and a heading (dx, dy), starting at the origin facing north (0, 1). 'G' moves forward by the heading, 'L' rotates the heading left, and 'R' rotates it right.

The robot stays bounded if either it returns to the origin, OR it is no longer facing north. If it ends back at (0, 0) it obviously loops. If it faces a different direction, then after 4 rounds the accumulated turning brings it back to start — so it still loops.

The only way to escape to infinity is to finish a round both away from the origin AND still facing north, because then every round drifts the same way forever.

Example: "GGLLGG" ends back at (0, 0), so it returns true — bounded.

Time: O(n) Space: O(1)