Walking Robot Simulation

Moderate
0/80
Average time to solve is 10m
5 upvotes
Asked in company
Google inc

Problem statement

A robot on an infinite XY-plane starts at point (0, 0) and faces north. The robot can receive one of three possible types of commands (given in the COMMANDS array/list):

1) -2: turn left 90 degrees,

2) -1: turn right 90 degrees, or

3) 1 <= ‘K’ <= 9: move forward K units.

Some of the grid squares are obstacles. The ‘ith’ obstacle is at grid point OBSTACLES[i] = (Xi, Yi).

If the robot would try to move onto them, the robot stays on the previous grid square instead (but still continues following the rest of the route.)

Return the maximum Euclidean distance that the robot will be from the origin squared (i.e. if the distance is 5, return 25).

Note :

North means +Y direction.
East means +X direction.
South means -Y direction.
West means -X direction.

For example:

N = 1, M = 0 
COMMANDS = [3], OBSTACLES = []


The final answer would be 9 since it moves 3 steps north.
Detailed explanation ( Input/output format, Notes, Images )

Input format :

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers ‘N’, ‘M’ Where ‘N’ is the number of COMMANDS and ‘M’ is the number of OBSTACLES.

The next line contains ‘N’ space-separated integers denoting the commands.

The next M lines contain two space-separated integers ‘X’ and ‘Y’, denoting the coordinates of obstacles.

Output format :

For each test case, return the distance the robot covers. The output of each test case will be printed in a separate line[0-based indexing].

Note:

You don't have to print anything, just implement the function.

Constraints:

1 <= T <= 5
1 <= N <= 10^3
1 <= M <= 10^3
-2 <= COMMANDS[i] <= 9
-3 * 10 ^ 3 <= OBSTACLES[i][j] <= 3 * 10 ^ 3

Time limit: 1 second

Sample Input 1 :

2
1 0
3
2 1
1 4
0 1

Sample Output 1 :

9
0

Explanation of the Sample Input 1:

For the first test case:


The final answer would be 9 since it moves 3 steps north.

For the second test case:


Since there is an Obstacle at (0,1) therefore the robot does not move and stays at the same position.

Sample Input 2 :

2
2 1
1 4
1 0
3 1
4 -1 3
1 1

Sample Output 2 :

25
25
Hint

Can we just simulate the path?

Approaches (1)
Simulation

The main idea is to just simulate the robot’s movement and return the final distance at the end.

 

  • Maintain two hashmaps ‘POSX’ and ‘POSY’ that store the x and y coordinates of the obstacles respectively.

 

  • Maintain ‘X’ and ‘Y’ variables which simulate the robot’s coordinates, initially, both are 0.

 

  • Maintain a variable ‘DIR’ that tells the direction in which the robot is facing:
    • 0 maps to North.
    • 1 maps to West.
    • 2 maps South.
    • 3 maps East.

 

  • If the COMMANDS[I] == -1 add 3 TO ‘DIR’ to indicate a right turn.

 

  • If the COMMANDS[I] == -2 add 1 to ‘DIR’ to indicate a left turn.

 

  • Return (X ^ 2 + Y ^ 2) as the euclid distance.
Time Complexity

O(N + M), where ‘N’ is the number of ‘COMMANDS’ and ‘M’ is the number of ‘OBSTACLES’.

 

Since we are traversing both COMMANDS and OBSTACLES once therefore O(N + M).

Space Complexity

O(M), where ‘M’ is the number of ‘OBSTACLES’.


Since we are using hashmaps to store the coordinates of obstacles, hence the net space complexity will be O(M).

Code Solution
(100% EXP penalty)
Walking Robot Simulation
Full screen
Console