874. Walking Robot Simulation
Model: qwen2.5-coder:14b
Topics: Greedy
FAANG asked: 0
Acceptance rate: 36.7%
Problem Breakdown
The problem involves simulating the movement of a robot on an infinite XY-plane starting at (0, 0) facing north. The robot receives commands that can either turn left or right by 90 degrees or move forward a certain number of units. Some grid squares are obstacles, and if the robot tries to move onto them, it stays on the previous grid square but continues following the rest of the route. The goal is to return the maximum Euclidean distance squared from the origin that the robot achieves during its journey.
Inputs:
commands: A list of integers where each integer represents a command.-2: Turn left by 90 degrees.-1: Turn right by 90 degrees.1 <= k <= 9: Move forwardkunits.
obstacles: A list of lists, where each sublist contains the coordinates of an obstacle.
Outputs:
- An integer representing the maximum Euclidean distance squared from the origin that the robot achieves during its journey.
Implicit Constraints and Edge Cases:
- The robot starts at (0, 0) facing north.
- The plane is infinite, so there are no boundaries to consider.
- Obstacles can be anywhere on the plane, including directly in front of the robot’s starting position.
- If there are no commands, the robot does not move, and the distance remains 0.
- If there are no obstacles, the robot moves freely according to the commands.
Intuition
A brute-force approach would involve simulating each command step by step, checking for obstacles at each unit of movement. This approach is feasible given the constraints but can be optimized by precomputing the directions and using a set to store obstacles for quick lookup.
The key insight is to use a direction array to manage the robot’s orientation and a set to store obstacle positions for O(1) lookups. By iterating through the commands, updating the robot’s position based on its current direction, and checking for obstacles, we can efficiently determine the maximum distance squared from the origin.
Approach
- Direction Array: Use an array to represent the four possible directions (north, east, south, west). Each direction is represented by a tuple of changes in x and y coordinates.
- Obstacle Set: Convert the list of obstacles into a set for O(1) lookups when checking if the robot’s next position is blocked.
- Simulate Commands:
- For each command, update the robot’s orientation based on whether it turns left or right.
- If the command is to move forward, attempt to move the robot one unit at a time in its current direction, stopping if an obstacle is encountered.
- Track the maximum distance squared from the origin during the simulation.
Complexity Analysis
- Time Complexity: O(n + m), where n is the number of commands and m is the number of obstacles. This is because each command is processed once, and checking for obstacles in the set takes constant time.
- Space Complexity: O(m) for storing the obstacles in a set.
Solution
class Solution:
def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
# Directions: north, east, south, west
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
# Convert obstacles list to a set for O(1) lookups
obstacle_set = set(map(tuple, obstacles))
# Initial position and direction index (facing north)
x, y = 0, 0
direction_index = 0
max_distance_squared = 0
for command in commands:
if command == -2: # Turn left
direction_index = (direction_index - 1) % 4
elif command == -1: # Turn right
direction_index = (direction_index + 1) % 4
else: # Move forward k units
dx, dy = directions[direction_index]
for _ in range(command):
next_x, next_y = x + dx, y + dy
if (next_x, next_y) not in obstacle_set:
x, y = next_x, next_y
else:
break
# Update the maximum distance squared from the origin
max_distance_squared = max(max_distance_squared, x * x + y * y)
return max_distance_squared
Edge Cases Handled
- No Commands: The robot remains at (0, 0), and the distance is 0.
- No Obstacles: The robot moves freely according to the commands.
- Obstacle Directly in Front: The robot stops moving forward when it encounters an obstacle.
- Multiple Obstacles: The robot checks each potential move against all obstacles.
- Large Commands: The robot can handle large values of
kas long as they are within the constraints.