Problem Explanation

A robot is placed on an infinite grid with some obstacles and can receive three types of commands: move forward by a unit, turn left by 90 degrees, or turn right by 90 degrees. The robot starts at the point (0, 0) and faces north. If the robot tries to move onto an obstacle, it stays on the previous grid square but continues following the route. Our task is to return the square of the maximum Euclidean distance that the robot will be from the origin.

Examples

For instance, if we provide the commands [4,-1,3] with no obstacles, the robot would first move 4 units north to (0, 4), then turn right to face east, and finally move 3 units to the east to end up at point (3, 4). The square of the Euclidean distance from the origin (0, 0) would thus be 25.

In another scenario with the commands [4,-1,4,-2,4] and obstacles at point (2, 4), the robot would move 4 units north to (0, 4), turn right to face east, attempt to move 4 units but end up at (1, 4) due to the obstacle, then turn left to face north and finally move 4 units north ending up at (1, 8). The maximum Euclidean distance from the origin squared would be 65.

Solution Approach

The solution uses an unordered set to store the obstacles and uses a set of directions to dictate the movement of the robot. For every command, the robot adjusts its direction if the command is a turn, or moves forward checking for obstacles. After each move, the robot calculates the Euclidean distance from the origin, keeping track of the maximum distance seen so far.

To illustrate this, let's consider a scenario with the commands [4, -1, 3] and no obstacles.

1. The robot starts at point (0, 0) facing north.
2. The first command is 4, so the robot moves 4 units north to the point (0, 4).
3. The second command is -1, which prompts the robot to turn right and face east.
4. The final command is 3, causing the robot to move 3 units east arriving at the endpoint at (3, 4).
5. The maximum Euclidean distance from the origin squared is thus 25.

Solution

Python Solution

1
2python
3class Solution(object):
4    def robotSim(self, commands, obstacles):
5        direction = ((0, 1), (1, 0), (0, -1), (-1, 0))  # N, E, S, W
6        x = y = d = max_distance = 0
7        obstacles_set = set(map(tuple, obstacles))
8        for command in commands:
9            if command == -2: 
10                d = (d - 1) % 4
11            elif command == -1: 
12                d = (d + 1) % 4
13            else:  
14                for _ in range(command):
15                    next_x, next_y = x + direction[d][0], y + direction[d][1]
16                    if (next_x, next_y) in obstacles_set: 
17                        break
18                    x, y = next_x, next_y
19                max_distance = max(max_distance, x * x + y * y)
20        return max_distance

Java Solution

1
2java
3class Solution {
4    public int robotSim(int[] commands, int[][] obstacles) {
5        Set<String> obstacleSet = new HashSet<>();
6        for (int[] obstacle : obstacles) obstacleSet.add(obstacle[0] + " " + obstacle[1]);
7        int[][] direction = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};  // N, E, S, W
8        int x = 0, y = 0, d = 0, maxDistance = 0;
9        for (int command : commands) {
10            if (command == -2) d = (d + 3) % 4;
11            else if (command == -1) d = (d + 1) % 4;
12            else {
13                for (int i = 0; i < command; i++) {
14                    int next_x = x + direction[d][0], next_y = y + direction[d][1];
15                    if (obstacleSet.contains(next_x + " " + next_y)) break;
16                    x = next_x;
17                    y = next_y;
18                }
19                maxDistance = Math.max(maxDistance, x * x + y * y);
20            }
21        }
22        return maxDistance;
23    }
24}

JavaScript Solution

1
2javascript
3var robotSim = function(commands, obstacles) {
4    let direction = [[0, 1], [1, 0], [0, -1], [-1, 0]];  // N, E, S, W
5    let obstacleSet = new Set(obstacles.map(d => d[0] + " " + d[1]));
6    let x = 0, y = 0, d = 0, maxDistance = 0 ;
7    for (let command of commands) {
8        if (command == -2) d = (d + 3) % 4;
9        else if (command == -1) d = (d + 1) % 4;
10        else {
11            for (let i = 0; i < command; i++) {
12                let next_x = x + direction[d][0], next_y = y + direction[d][1];
13                if (obstacleSet.has(next_x + " " + next_y)) break;
14                x = next_x;
15                y = next_y;
16            }
17            maxDistance = Math.max(maxDistance, x * x + y * y);
18        }
19    }
20    return maxDistance;
21};

C++ Solution

1
2c++
3class Solution {
4public:
5    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
6        set<pair<int, int>> obstacleSet;
7        for(vector<int> obstacle : obstacles) obstacleSet.insert(make_pair(obstacle[0], obstacle[1]));
8        int direction[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};  // N, E, S, W
9        int x = 0, y = 0, d = 0, maxDistance = 0 ;
10        for(int command : commands) {
11            if (command == -2) d = (d + 3) % 4;
12            else if (command == -1) d = (d + 1) % 4;
13            else {
14                for (int i = 0; i < command; i++) {
15                    int next_x = x + direction[d][0], next_y = y + direction[d][1];
16                    if (obstacleSet.count(make_pair(next_x, next_y))) break;
17                    x = next_x;
18                    y = next_y;
19                }
20                maxDistance = max(maxDistance, x * x + y * y);
21            }
22        }
23        return maxDistance;
24    }
25};

C# Solution

1
2csharp
3public class Solution {
4    public int RobotSim(int[] commands, int[][] obstacles) {
5        HashSet<(int, int)> obstacleSet = new HashSet<(int, int)>();
6        foreach(int[] obstacle in obstacles) obstacleSet.Add((obstacle[0], obstacle[1]));
7        int[][] direction = new int[][] {new int[]{0, 1}, new int[]{1, 0}, new int[]{0, -1}, new int[]{-1, 0}};  // N, E, S, W
8        int x = 0, y = 0, d = 0, maxDistance = 0 ;
9        foreach(int command in commands) {
10            if (command == -2) d = (d + 3) % 4;
11            else if (command == -1) d = (d + 1) % 4;
12            else {
13                for (int i = 0; i < command; i++) {
14                    int next_x = x + direction[d][0], next_y = y + direction[d][1];
15                    if (obstacleSet.Contains((next_x, next_y))) break;
16                    x = next_x;
17                    y = next_y;
18                }
19                maxDistance = Math.Max(maxDistance, x * x + y * y);
20            }
21        }
22        return maxDistance;
23    }
24}

Note

In each solution, we iterate through all given commands and check if it's a movement command or a turn command. If it's a turn command then we just change direction else in case of movement command we move to that direction ensuring that we don't hit an obstacle. If we do hit an obstacle then we break the move loop and continue to the next command. After each move, we calculate the square of the Euclidean distance from the origin and update our maximum distance so far.# Conclusion

This problem is a good example of grid navigation with a set of commands. The robot uses turn commands to change direction and move commands to move along the grid. Obstacle avoidance is achieved by storing obstacles in a set and checking for their presence during each move.

The solutions in Python, Java, JavaScript, C++, and C# all follow a similar approach: they keep track of the robot's current position and direction, execute each command accordingly, and calculate the Euclidean distance after each move. The maximum distance achieved during the execution of commands is returned as the result.

This problem highlights important concepts such as navigating a grid, maintaining and altering state based on commands, handling constraints (obstacles), and computing distance between points on a plane.

It's worth noting that the use of an unordered set for obstacles allows for fast (constant time) checks for the presence of obstacles, enabling efficient navigation and obstacle avoidance. This is a good problem to practice if you want to better understand navigation and obstacle avoidance in a grid-like structure using different commands, or to get a stronger grasp on dealing with state changes and set operations.

Happy coding!