algoadvance

The problem is taken from LeetCode (Problem 874: Walking Robot Simulation). Here is the complete problem statement:

A robot is walking in a 2-dimensional grid starting from the origin point (0, 0). The robot can be controlled using commands represented by an integer array. Each command can be:

  1. A positive integer x which means the robot moves forward x units.
  2. A value -1 which means the robot turns 90 degrees to the right.
  3. A value -2 which means the robot turns 90 degrees to the left.

Additionally, there are obstacles located on the grid that the robot must avoid. The obstacles are represented as a list of pairs of integers where each pair represents the coordinates of an obstacle (ox, oy).

The task is to find the maximum Euclidean distance squared from the origin that the robot can reach after executing all the commands.

Clarifying Questions

  1. What are the initial direction and position of the robot?
    • The robot starts at the origin (0, 0) facing north.
  2. How are obstacles specified?
    • Obstacles are given as a list of tuples, where each tuple represents the coordinates (x, y) of an obstacle.
  3. Are the grid dimensions predefined or infinite?
    • We can assume the grid is infinite.
  4. Does the robot stop moving if it encounters an obstacle?
    • Yes, the robot stops before hitting an obstacle and waits for the next command.

Strategy

Given the problem, we can break it down into the following steps:

  1. Initialization:
    • Start at position (0, 0) with the initial direction as “north”.
  2. Movement & Direction Handling:
    • Use a dictionary or list to manage the direction transitions.
    • Implement turn commands (-1 and -2) to alter the direction.
    • Handle move commands (positive integers) to update the position, considering obstacles.
  3. Calculating Distance:
    • Keep track of the maximum Euclidean distance squared to avoid computing square roots.

Code

Here’s the complete implementation of the solution in Python:

def robotSim(commands, obstacles):
    # Initial position and direction (north)
    x, y = 0, 0
    # Directions: north, east, south, west
    directions = [ (0, 1), (1, 0), (0, -1), (-1, 0) ]
    current_direction = 0
    
    # Convert obstacles to a set of tuples for faster access
    obstacles = set(map(tuple, obstacles))
    
    max_distance = 0
    
    for command in commands:
        if command == -1:
            # Turn right
            current_direction = (current_direction + 1) % 4
        elif command == -2:
            # Turn left
            current_direction = (current_direction - 1) % 4
        else:
            # Move forward 'command' steps
            dx, dy = directions[current_direction]
            for _ in range(command):
                # Calculate the next position
                next_x, next_y = x + dx, y + dy
                # Check if the next position is an obstacle
                if (next_x, next_y) in obstacles:
                    break
                # Update the position
                x, y = next_x, next_y
                # Update the maximum distance
                max_distance = max(max_distance, x*x + y*y)
                
    return max_distance

# Example usage
commands = [4, -1, 3]
obstacles = []
print(robotSim(commands, obstacles))  # Output: 25

commands = [4, -1, 4, -2, 4]
obstacles = [[2, 4]]
print(robotSim(commands, obstacles))  # Output: 65

Time Complexity

Thus, the overall time complexity is:

This implementation ensures efficiency and effectively handles the problem constraints.

Try our interview co-pilot at AlgoAdvance.com