Leetcode: Robot Bounded In Circle

 This question is asked very commonly in the Goldman Sachs Interview. It is as follows: 

On an infinite plane, a robot initially stands at (0,0) and faces north. The robot can receive one of three instructions

"G" goes straight for one unit, "L" turns 90 degrees to the left, and "R" turns 90 degrees to the right. The robot repeats these instruction forever and return true if there is a circle such that the robot never reaches the circle.

Here are the examples of some solutions the algorithm should yield.

Input: "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.

Input: "GG"

Output: false

Explanation: 

The robot moves north indefinitely.

Input: "GL"

Output: true

Explanation: 

The robot moves from (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> ...

Let's take some steps into solving this algorithm.

A trajectory attractor is a set of trajectories in which a system tends to evolve. If an attractor is imited, this means that a robot never leaves the circle.

We wants to see if the trajectory successfully loops back. 

There are 2 conditions that registers as the limit cycle trajectory. If the robot doesn't face north, then it'll also eventually reach a cycle. I will write the strict mathematical proof down below. 

Lets say the following:

North = 0

East = 1

South = 2

West = 3

and after one cycle the direction d != 0 and after 4 cycles the robot faces (k * 4) % 4 cycles which is - cycles, which means that the robot will be facing north confirming that there is a possible cycle that the robot is travelling through.

After one cycle the robot coordinates are (x + Δx, y + Δy).

If the robot faces north after one cycle, then 

y = y + Δy + Δy + Δy + Δy and x = x + Δx + Δx + Δx + Δx

If the robot faces east after one cycle, then 

y = y + Δy - Δx - Δy + Δx and x = x + Δx + Δy - Δx - Δy 

If the robot faces south after one cycle, then 

y = y + Δy - Δy + Δy - Δy and x = x + Δx - Δx + Δx - Δx

If the robot faces west after one cycle, then 

y = y + Δy + Δx - Δy - Δx and x = x + Δx - Δy - Δx + Δy

All three of the latest ones ends up in coordinates (x,y) which is therefore a proof of the first proposition. The implementation thus is pretty simple after this.

class Solution {

    public boolean isRobotBounded(String instructions) {

        int[][] directions = new int[][]{{0, 1}, {1,0}, {0, -1}, {-1, 0}};

        int x = 0;

        int y = 0;

        int idx = 0;

        for(char 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];

            }

        }

        return(x == 0 && y == 0) || (idx != 0);

    }

}