A robot on an infinite XY-plane starts at point (0, 0) facing north. The robot can receive a sequence of these three possible types of commands:


	-2: Turn left 90 degrees.
	-1: Turn right 90 degrees.
	1 &lt;= k &lt;= 9: Move forward k units, one unit at a time.


Some of the grid squares are obstacles. The ith obstacle is at grid point obstacles[i] = (xi, yi). If the robot runs into an obstacle, then it will instead stay in its current location and move on to the next command.

Return the maximum Euclidean distance that the robot ever gets 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.


&nbsp;
Example 1:

Input: commands = [4,-1,3], obstacles = []
Output: 25
Explanation: The robot starts at (0, 0):
1. Move north 4 units to (0, 4).
2. Turn right.
3. Move east 3 units to (3, 4).
The furthest point the robot ever gets from the origin is (3, 4), which squared is 32 + 42 = 25 units away.


Example 2:

Input: commands = [4,-1,4,-2,4], obstacles = [[2,4]]
Output: 65
Explanation: The robot starts at (0, 0):
1. Move north 4 units to (0, 4).
2. Turn right.
3. Move east 1 unit and get blocked by the obstacle at (2, 4), robot is at (1, 4).
4. Turn left.
5. Move north 4 units to (1, 8).
The furthest point the robot ever gets from the origin is (1, 8), which squared is 12 + 82 = 65 units away.


Example 3:

Input: commands = [6,-1,-1,6], obstacles = []
Output: 36
Explanation: The robot starts at (0, 0):
1. Move north 6 units to (0, 6).
2. Turn right.
3. Turn right.
4. Move south 6 units to (0, 0).
The furthest point the robot ever gets from the origin is (0, 6), which squared is 62 = 36 units away.


&nbsp;
Constraints:


	1 &lt;= commands.length &lt;= 104
	commands[i] is either -2, -1, or an integer in the range [1, 9].
	0 &lt;= obstacles.length &lt;= 104
	-3 * 104 &lt;= xi, yi &lt;= 3 * 104
	The answer is guaranteed to be less than 231.


class Solution:
    def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
        obs = set(tuple(o) for o in obstacles)
        x = y = a = out = 0
        move = {0:(0,1), 90:(1,0), 180:(0,-1), 270:(-1,0)}
        for c in commands:
            if c == -1:
                a += 90
            elif c == -2:
                a -= 90
            else:
                direction = a % 360
                dx, dy = move[direction]
                for _ in range(c):
                    if (x + dx, y + dy) in obs:
                        break
                    x += dx
                    y += dy
                out = max(out, x**2 + y**2)
        return out
class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        int dir = 0; // states 0north-1east-2south-3west
        int farthestSofar = 0;

        int xloc = 0;
        int yloc = 0;

        Set<String> set = new HashSet<>();
        for (int[] obs : obstacles) {
            set.add(obs[0] + "," + obs[1]);
        }

        int steps;

        for(int i: commands){

            if( i == -1){//turn right 90
                dir++;
            }
            else if (i == -2){//turn left 90
                dir--;
            }
            else{//move forward value of i baring no obsticals
                dir = dir%4;
                if (dir== -1){
                    dir = 3;
                }
                else if(dir == -3){
                    dir = 1;
                }
                else if(dir == -2){
                    dir = 2;
                }
                // dir %4 = -1 -> 3
                // dir %4 = -2 -> 2
                // dir %4 = -3 -> 1
                if(dir == 0){
                    steps = 0;
                    while (steps < i && !set.contains((xloc) + "," + (yloc+1))) {
                    yloc++;
                    steps++;
                    }
                }
                else if (dir == 1){
                    steps = 0;
                    while (steps < i && !set.contains((xloc+1) + "," + (yloc))) {
                    xloc++;
                    steps++;
                    }
                }
                else if (dir == 2){
                    steps = 0;
                    while (steps < i && !set.contains((xloc) + "," + (yloc-1))) {
                    yloc--;
                    steps++;
                    }
                }
                else{ //case dir == 3
                    steps = 0;
                    while (steps < i && !set.contains((xloc-1) + "," + (yloc))) {
                    xloc--;
                    steps++;
                    }
                }
            }
            farthestSofar = Math.max(farthestSofar, xloc*xloc + yloc*yloc);
        }
        return farthestSofar;
    }
}
class Solution {
public:

    //N--> left(-2):W, right(-1):E
    //S--> left:E, right:W
    //E--> left:N, right:S
    //W--> left:S, right:N

    vector<vector<int>> change= { //for direction change
        {3,2},
        {2,3},
        {0,1},
        {1,0}
    };

    vector<vector<int>> sign = { //signs for x and y coordinates movement
        {0,1},//North
        {0,-1},//south
        {1,0},//east
        {-1,0}//west
    };

    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        set<vector<int>> s;
        for(int i = 0;i<obstacles.size();i++){
            s.insert(obstacles[i]);
        }
        int direction = 0;
        int ans = 0;
        int xi = 0,yi = 0;
        for(int i = 0;i<commands.size();i++){
            if(commands[i]<=9 && commands[i]>=1){
                int signx = sign[direction][0];
                int signy = sign[direction][1];
                while(commands[i]){
                    xi += signx;
                    yi += signy;
                    if(s.count({xi,yi})){
                        xi -= signx;
                        yi -= signy;
                        break;
                    }
                    commands[i]--;
                }
            }
            else{
                direction = change[direction][commands[i]+2];
            }
            ans = max(ans,xi*xi+yi*yi);
        }
        return ans;
    }
};
/**
 * @param {number[]} commands
 * @param {number[][]} obstacles
 * @return {number}
 */
var robotSim = function(commands, obstacles) {  
  let result = 0;
  let currentPosition = [0, 0];
  let currentDirection = 'top';
  const mySet = new Set();
  
  // This is to have a O(1) check instead of doing a linear scan
  obstacles.forEach(obs => {
    mySet.add(`${obs[0]},${obs[1]}`);
  }); // O(m)
  
  for (let i = 0; i < commands.length ; i++) { // O(n)
    const move = commands[i];
    if (move === -1) {
      if (currentDirection === 'top') {
        currentDirection = 'right';
      } else if (currentDirection === 'right') {
        currentDirection = 'down';
      } else if (currentDirection === 'down') {
        currentDirection = 'left';
      } else {
        currentDirection = 'top';
      }
    }
    
    if (move === -2) {
      if (currentDirection === 'top') {
        currentDirection = 'left';
      } else if (currentDirection === 'left') {
        currentDirection = 'down';
      } else if (currentDirection === 'down') {
        currentDirection = 'right';
      } else {
        currentDirection = 'top';
      }
    }
    
    if (move > 0) {
      for (let i = 0; i < move; i++) { O(move)
      const isY = (currentDirection === 'top' || currentDirection === 'down');
      const isPositive = (currentDirection === 'top' || currentDirection === 'right');
      
      const newPosition = [currentPosition[0] + (!isY ? isPositive? 1: -1 : 0), currentPosition[1] + (isY ? isPositive ? 1 : -1 : 0)];
      const positionString = `${newPosition[0]},${newPosition[1]}`;

      if (!mySet.has(positionString)) {
        currentPosition = newPosition;
        result = Math.max(result, (Math.pow(currentPosition[0], 2) + Math.pow(currentPosition[1], 2)));
      } else {
        break;
      }
    }
    }
  }
  return result;
};
Walking Robot Simulation