Problem Description

In the "Walking Robot Simulation" problem, you are given a sequence of commands for a robot and a list of obstacles on a 2D grid. The robot starts at position (0, 0) facing north (the positive Y direction).

The commands array contains integers:

• -2: Turn left 90 degrees
• -1: Turn right 90 degrees
• Any positive integer x: Move forward x units in the current direction, one unit at a time

The obstacles array contains coordinates [x, y] of grid points that the robot cannot move onto.

The goal is to simulate the robot's movement and return the maximum Euclidean distance squared (i.e., x*x + y*y) from the origin that the robot reaches at any point during the simulation.

Constraints:

• There may be zero or more obstacles.
• The robot cannot move onto a square with an obstacle; if the next square is blocked, the robot stops moving for that command.
• All commands must be followed in order.

Thought Process

At first glance, this problem seems to require simulating the robot's step-by-step movement, carefully updating its position and direction. A brute-force approach would directly implement the movement logic, checking after every step whether the next position is blocked by an obstacle.

However, since the robot can only move in four directions (north, east, south, west), and obstacles must be checked efficiently, we want to optimize the obstacle lookup. Using a list for obstacles would make each check O(N), which is too slow. Instead, storing obstacles in a set allows constant-time O(1) lookups.

The main challenge is:

• Correctly updating the robot's direction after each turn.
• Efficiently checking for obstacles at each step.
• Tracking the maximum distance squared from the origin.

Solution Approach

Here is a step-by-step breakdown of the solution:

1. Represent Directions:
   • Use two arrays, dx and dy, to represent the change in x and y for each direction (north, east, south, west).
   • Maintain a direction index (0-3) to keep track of the current facing direction.
2. Store Obstacles:
   • Convert the list of obstacles into a set of tuples or strings for O(1) lookup.
3. Simulate Commands:
   • For each command:
     • If -2: turn left (decrement direction, wrap around with modulo 4).
     • If -1: turn right (increment direction, wrap around with modulo 4).
     • If positive: move step by step in the current direction, checking for obstacles at each step. If an obstacle is encountered, stop moving for that command.
4. Track Maximum Distance:
   • After each successful move, calculate x*x + y*y and update the maximum found so far.

This approach ensures each movement and obstacle check is efficient, and the simulation follows the problem's rules precisely.

Example Walkthrough

Sample Input:
commands = [4, -1, 3]
obstacles = []

1. Start at (0,0) facing north.
2. Command 4: Move forward 4 units north to (0,1), (0,2), (0,3), (0,4). No obstacles, so move all 4 steps.
   Max distance squared so far: 0*0 + 4*4 = 16
3. Command -1: Turn right, now facing east.
4. Command 3: Move forward 3 units east to (1,4), (2,4), (3,4).
   Max distance squared at (3,4): 3*3 + 4*4 = 9 + 16 = 25

Final answer: 25

If there were obstacles, the robot would stop moving forward upon reaching a blocked square, but would continue with the next command.

Time and Space Complexity

Brute-force approach:

• If obstacles are stored in a list, checking for an obstacle at each step is O(M), where M is the number of obstacles. For K movement steps, this results in O(K*M) time.

• By storing obstacles in a set, each lookup is O(1). So for K movement steps, the simulation is O(K).
• Space complexity is O(M) for storing the obstacles.

The overall time complexity is O(K + M), where K is the total number of movement steps (sum of all positive commands), and M is the number of obstacles.

Summary

This problem is an exercise in simulating movement on a grid with direction changes and obstacles. The key insight is to use an efficient data structure (set) for obstacle lookup, allowing the simulation to run in linear time relative to the number of commands and obstacles. By carefully updating direction and position, and checking for obstacles at each step, we ensure correctness. Tracking the maximum distance squared at each step gives the required answer.

Code Implementation

class Solution:
    def robotSim(self, commands, obstacles):
        obstacle_set = set(map(tuple, obstacles))
        # Directions: North, East, South, West
        dx = [0, 1, 0, -1]
        dy = [1, 0, -1, 0]
        x = y = 0
        direction = 0  # 0=north, 1=east, 2=south, 3=west
        max_dist = 0

        for cmd in commands:
            if cmd == -2:
                direction = (direction + 3) % 4  # turn left
            elif cmd == -1:
                direction = (direction + 1) % 4  # turn right
            else:
                for _ in range(cmd):
                    nx, ny = x + dx[direction], y + dy[direction]
                    if (nx, ny) in obstacle_set:
                        break
                    x, y = nx, ny
                    max_dist = max(max_dist, x * x + y * y)
        return max_dist
      

class Solution {
public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        set<pair<int, int>> obstacle_set;
        for (auto& obs : obstacles)
            obstacle_set.insert({obs[0], obs[1]});
        // Directions: North, East, South, West
        int dx[4] = {0, 1, 0, -1};
        int dy[4] = {1, 0, -1, 0};
        int x = 0, y = 0, dir = 0, max_dist = 0;

        for (int cmd : commands) {
            if (cmd == -2) dir = (dir + 3) % 4;
            else if (cmd == -1) dir = (dir + 1) % 4;
            else {
                for (int i = 0; i < cmd; ++i) {
                    int nx = x + dx[dir], ny = y + dy[dir];
                    if (obstacle_set.count({nx, ny}))
                        break;
                    x = nx; y = ny;
                    max_dist = max(max_dist, x * x + y * y);
                }
            }
        }
        return max_dist;
    }
};
      

import java.util.*;

class Solution {
    public int robotSim(int[] commands, int[][] obstacles) {
        Set<String> obstacleSet = new HashSet<>();
        for (int[] obs : obstacles) {
            obstacleSet.add(obs[0] + "," + obs[1]);
        }
        // Directions: North, East, South, West
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};
        int x = 0, y = 0, dir = 0, maxDist = 0;

        for (int cmd : commands) {
            if (cmd == -2) {
                dir = (dir + 3) % 4;
            } else if (cmd == -1) {
                dir = (dir + 1) % 4;
            } else {
                for (int i = 0; i < cmd; ++i) {
                    int nx = x + dx[dir], ny = y + dy[dir];
                    if (obstacleSet.contains(nx + "," + ny)) break;
                    x = nx; y = ny;
                    maxDist = Math.max(maxDist, x * x + y * y);
                }
            }
        }
        return maxDist;
    }
}
      

var robotSim = function(commands, obstacles) {
    const obstacleSet = new Set();
    for (let obs of obstacles) {
        obstacleSet.add(obs[0] + ',' + obs[1]);
    }
    // Directions: North, East, South, West
    const dx = [0, 1, 0, -1];
    const dy = [1, 0, -1, 0];
    let x = 0, y = 0, dir = 0, maxDist = 0;

    for (let cmd of commands) {
        if (cmd === -2) {
            dir = (dir + 3) % 4;
        } else if (cmd === -1) {
            dir = (dir + 1) % 4;
        } else {
            for (let i = 0; i < cmd; ++i) {
                let nx = x + dx[dir], ny = y + dy[dir];
                if (obstacleSet.has(nx + ',' + ny)) break;
                x = nx; y = ny;
                maxDist = Math.max(maxDist, x * x + y * y);
            }
        }
    }
    return maxDist;
};