1041. Robot Bounded In Circle

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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’.

Solution

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class Solution {
    
    public boolean isRobotBounded(String instructions) {
         int[][] directions = new int[][] {
             {0,1}, // north
             {1,0}, // east
             {0,-1}, // south
             {-1,0} // west
         };
        
        int x = 0;
        int y = 0;
        int idx = 0;
        
        for (int i: instructions.toCharArray()) {
            if (i == 'L') {
                idx = (idx + 3) % 4;
            } else if (i == 'R') {
                idx = (idx + 1) % 4;
            } else {
                x += directions[idx][0];
                y += directions[idx][1];
            }
        }
        
        // after one cycle:
        // robot returns into initial position
        // or robot doesn't face north
        return (x == 0 && y == 0) || (idx != 0);
    }
    
    public boolean isRobotBounded2(String instructions) {
        char direction = 'G';
        int i = 0;
        int j = 0;
        int n = instructions.length();
        for (int k = 0; k < 4 * n; k++) {
            char c = instructions.charAt(k % n);
            if (c == 'G') {
                if (direction == 'G') {
                    i++;
                } else if (direction == 'L') {
                    j--;
                } else if (direction == 'D') {
                    i--;
                } else if (direction == 'R') {
                   j++;
                }
            } else if (c == 'L') {
                if (direction == 'G') {
                    direction = 'L';
                } else if (direction == 'L') {
                    direction = 'D';
                } else if (direction == 'D') {
                    direction = 'R';
                } else if (direction == 'R') {
                    direction = 'G';
                }
            } else if (c == 'R') {
                if (direction == 'G') {
                    direction = 'R';
                } else if (direction == 'R') {
                    direction = 'D';
                } else if (direction == 'D') {
                    direction = 'L';
                } else if (direction == 'L') {
                    direction = 'G';
                }
            }
        }
        return (i == 0 && j == 0);
    }
}

Solution#

Solution