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.

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]