Blogs Hub

by Sumit Chourasia | Oct 05, 2020 | Category :coding | Tags : algorithm data-structure easy greedy leetcode

Walking Robot Simulation - Greedy - Easy - LeetCode

Walking Robot Simulation - Greedy - Easy - LeetCode

A robot on an infinite grid starts at point (0, 0) and faces north.  The robot can receive one of three possible types of commands:

-2: turn left 90 degrees
-1: turn right 90 degrees
1 <= x <= 9: move forward x units
Some of the grid squares are obstacles. 

The i-th obstacle is at grid point (obstacles[i][0], obstacles[i][1])

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 square of the maximum Euclidean distance that the robot will be from the origin.

 

Example 1:

Input: commands = [4,-1,3], obstacles = []
Output: 25
Explanation: robot will go to (3, 4)
Example 2:

Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
Output: 65
Explanation: robot will be stuck at (1, 4) before turning left and going to (1, 8)
 

Note:

0 <= commands.length <= 10000
0 <= obstacles.length <= 10000
-30000 <= obstacle[i][0] <= 30000
-30000 <= obstacle[i][1] <= 30000
The answer is guaranteed to be less than 2 ^ 31.

public class Solution {
    char face = 'N';
    public int RobotSim(int[] commands, int[][] obstacles) {        
        int x =0;
        int y = 0;
        int maxDistance = 0;
        var set = new HashSet<string>();
        for(int i=0;i<obstacles.Length;i++){
            set.Add(GetKey(obstacles[i][0],obstacles[i][1]));
        }
        
        for(int i=0;i<commands.Length;i++){
            if(commands[i]==-2){
                TurnLeft();
            }
            else if(commands[i]==-1){
                TurnRight();
            }
            else{
                for(int j=1;j<=commands[i];j++){
                    int tx = x + GetValue('x');
                    int ty = y + GetValue('y');
                    if(set.Contains(GetKey(tx,ty))){
                        break;
                    }
                    x = tx;
                    y = ty;
                }
            }
            maxDistance = Math.Max(maxDistance, x*x+y*y);
        }
        
        return maxDistance;
    }
    
    private string GetKey(int x, int y){
        return x+" "+y;
    }
    
    private int GetValue(char ch){
        if(ch=='x'){
            if(face=='E'){
                return 1;
            }
            else if(face == 'W'){
                return -1;
            }
        }
        else if(ch=='y'){
            if(face=='N'){
                return 1;
            }
            else if(face == 'S'){
                return -1;
            }
        }
        return 0;
    }
    
    private void TurnLeft(){
        switch(face){
            case 'E':
                face = 'N';
                break;
            case 'W':
                face = 'S';
                break;
            case 'N':
                face = 'W';
                break;
            case 'S':
                face = 'E';
                break;
        }
    }
    
    private void TurnRight(){
        switch(face){
            case 'E':
                face = 'S';
                break;
            case 'W':
                face = 'N';
                break;
            case 'N':
                face = 'E';
                break;
            case 'S':
                face = 'W';
                break;
        }
    }
}

Time Complexity: O(n*m)

Space Complexity: O(n)

Where n is the number of inputs and m is the length of steps