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 degress 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: "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: "GG" Output: false Explanation: The robot moves north indefinitely.

Example 3:

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

Note:

  1. 1 <= instructions.length <= 100

  2. instructions[i] is in {'G', 'L', 'R'}

 class Solution {

       public boolean isRobotBounded(String ins) {
        int x = 0, y = 0, length = ins.length(), i = 0, dir[][] = {{0, 1}, {1, 0}, {0, -1}, { -1, 0}};
        for (int j = 0; j < length; ++j)
            if (ins.charAt(j) == 'R')
                i = (i + 1) % 4;
            else if (ins.charAt(j) == 'L')
                i = (i + 3) % 4;
            else {
                x += dir[i][0]; y += dir[i][1];
            }
        return x == 0 && y == 0 || i > 0;
    }
}

Here let's take following assumptions,

A robot is starting at (0,0) and faces north (i.e.,) (0,1) and after one sequence of instructions,

1) If a robot returns to (0,0), then it forms a circle.

2) If robot finishes with face not towards north, it will get back to the initial status in another one or three sequences.

(x,y) is a location of robot

dir[][] - direction a robot is facing

i = (i+1)%4 -> robot turns right

i = (i+3)%4 -> robot turns left

3) Check final status after all instructions.

 

 

Comments

Popular posts from this blog

First Unique Character in a String

Balanced Binary Tree

Majority Element

Sequential Digits