# 1041. Robot Bounded In Circle

<https://leetcode.com/problems/robot-bounded-in-circle>

## 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;
* `"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.

**Example 1:**

```
**Input:** instructions = "GGLLGG"
**Output:** true
**Explanation:** The robot moves from (0,0) to (0,2), turns 180 degrees, and then returns to (0,0).
When repeating these instructions, the robot remains in the circle of radius 2 centered at the origin.
```

**Example 2:**

```
**Input:** instructions = "GG"
**Output:** false
**Explanation:** The robot moves north indefinitely.
```

**Example 3:**

```
**Input:** instructions = "GL"
**Output:** true
**Explanation:** The robot moves from (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ...
```

**Constraints:**

* `1 <= instructions.length <= 100`
* `instructions[i]` is `'G'`, `'L'` or, `'R'`.

## ac

Mostly a brain teaser: return true if after executing instuctions, 1) back to stating point; 2) not facing up. See proof below.

```java
class Solution {
    public boolean isRobotBounded(String instructions) {
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        int x = 0, y = 0;
        int d = 0; // d means facing direction, dirs[0] means if we meet a "G", then x += 0 and y += 1
        
        for (int i = 0; i < instructions.length(); i++) {
            char c = instructions.charAt(i);
            if (c == 'R') {
                // Find next direction, represented as index in array dirs. 
                d = (d + 1) % 4;
            } else if (c == 'L') {
                d = (d + 3) % 4; // turn left == turn right 3 times
            } else {
                x += dirs[d][0];
                y += dirs[d][1];
            }
        }
        
        return x == 0 && y == 0 || d != 0;
    }
}

// O(N) time, O(1) space
```

Solution explain: <https://leetcode.com/problems/robot-bounded-in-circle/discuss/290856/JavaC%2B%2BPython-Let-Chopper-Help-Explain>

Proof:

```
Try to prove with math representation:
Let's say the robot starts with facing up. It moves [dx, dy] by executing the instructions once.
If the robot starts with facing
right, it moves [dy, -dx];
left, it moves [-dy, dx];
down, it moves [-dx, -dy]

If the robot faces right (clockwise 90 degree) after executing the instructions once,
the direction sequence of executing the instructions repeatedly will be up -> right -> down -> left -> up
The resulting move is [dx, dy] + [dy, -dx] + [-dx, -dy] + [-dy, dx] = [0, 0] (back to the original starting point)

All other possible direction sequences:
up -> left -> down -> right -> up. The resulting move is [dx, dy] + [-dy, dx] + [-dx, -dy] + [dy, -dx] = [0, 0]
up -> down -> up. The resulting move is [dx, dy] + [-dx, -dy] = [0, 0]
up -> up. The resulting move is [dx, dy]
```