Robot Bounded In Circle Solution Amazon OA 2021

Robot Bounded In Circle Solution

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.

Also See: Amazon OA Online Assessment 2021 Questions and Answers

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:

Program C++:

class Solution {
public:
    int dx[4]{0, 0, -1, 1};
    int dy[4]{1, -1, 0, 0};
    
    int turnLeft(int d) {
        if (d == 0) return 2;
        if (d == 2) return 1;
        if (d == 1) return 3;
        return 0;
    }
    
    int turnRight(int d) {
        if (d == 0) return 3;
        if (d == 3) return 1;
        if (d == 1) return 2;
        return 0;
    }
    
    bool isRobotBounded(string instructions) {
         int x, y, direct;
         x = y = direct = 0;
        instructions += instructions + instructions + instructions;
         for(auto c : instructions)
             if (c == 'L') 
                 direct = turnLeft(direct);
             else if (c == 'R') 
                 direct = turnRight(direct);
             else {
                 x += dx[direct];
                 y += dy[direct];
             }
          if (x == 0 && y == 0) return true;
          return false;
    }
};

Program Java:

class Solution {
    public boolean isRobotBounded(String instructions) {
        // init position
        int[] pos = new int[]{0, 0};
        
        // directions north, east, south, west 
        int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        
        int face = 0;
        char[] ins = instructions.toCharArray();
       
        for(char c: ins) {
            if(c == 'L') {
                face = face == 0 ? 3 : face - 1;
            }
            else if(c == 'R') {
                face = face == 3 ? 0 : face + 1;
            }
            else {
                pos[0] = pos[0] + dirs[face][0];
                pos[1] = pos[1] + dirs[face][1];
            }
        }
        return (face != 0 || (pos[0] == 0 && pos[1] == 0));
    }
}

Program Python:

class Solution:
    def isRobotBounded(self, instructions: str) -> bool:     
        
        offset_dict_L = {}

        offset_dict_L[(0,1)] = (-1,0)
        offset_dict_L[(0,-1)] = (1,0)
        offset_dict_L[(1,0)] = (0,1)
        offset_dict_L[(-1,0)] = (0,-1)

        offset_dict_R = {}

        offset_dict_R[(0,1)] = (1,0)
        offset_dict_R[(0,-1)] = (-1,0)
        offset_dict_R[(1,0)] = (0,-1)
        offset_dict_R[(-1,0)] = (0,1)

        cx = 0
        cy = 0

        c_offset = (0,1)

        for i in instructions:

            if(i == 'G'):
                cx += c_offset[0]
                cy += c_offset[1]
            elif(i == 'L'):
                c_offset = offset_dict_L.get(c_offset)
            elif(i == 'R'):
                c_offset = offset_dict_R.get(c_offset)


        if(cx == 0 and cy == 0):
            return True
        elif(c_offset == (0,1)):
            return False
        else:
            return True

Also See: AMCAT Study Materials, Preparation Guide

Also See: Microsoft Online Assessment Questions and Solution

Amazon Online Assessment Test Questions:

Leave a Comment