We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Walking Robot Simulation

Difficulty: Medium

Problem Description

A robot on an infinite XY-plane starts at point (0, 0) facing north. The robot receives an array of integers commands, which represents a sequence of moves that it needs to execute. There are only three possible types of instructions the robot can receive:

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

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

Return the maximum squared Euclidean distance that the robot reaches at any point in its path (i.e. if the distance is 5, return 25).

Key Insights

  • The robot's movements are determined by the commands array, which includes movements and directional turns.
  • The robot's direction can be tracked using a simple array to represent the four cardinal directions.
  • Obstacles need to be stored in a set for O(1) lookup time to check if the robot's next move is blocked.
  • The maximum squared distance can be calculated from the robot's current coordinates after processing each command.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the commands array, as we process each command once. Space Complexity: O(m), where m is the number of obstacles, to store them in a set for quick access.

Solution

To solve this problem, we will use the following approach:

  1. Initialize the robot's position at (0, 0) and set its initial direction to north.
  2. Maintain a list of direction vectors corresponding to north, east, south, and west.
  3. Use a set to store obstacles for quick access.
  4. Iterate through the commands:
    • For -2, update the direction to turn left.
    • For -1, update the direction to turn right.
    • For k (1 to 9), move the robot forward k units unless blocked by an obstacle.
  5. After each move, calculate the squared distance from the origin and update the maximum squared distance if the current position exceeds it.
  6. Return the maximum squared distance encountered during the simulation.

Code Solutions

def robotSim(commands, obstacles):
    # Directions: North, East, South, West
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    x, y = 0, 0  # Initial position
    direction_index = 0  # Start facing North
    obstacle_set = set(map(tuple, obstacles))  # Convert obstacles to a set for O(1) lookup
    max_distance_sq = 0  # Maximum squared distance
    
    for cmd in commands:
        if cmd == -2:  # Turn left
            direction_index = (direction_index - 1) % 4
        elif cmd == -1:  # Turn right
            direction_index = (direction_index + 1) % 4
        else:  # Move forward cmd units
            for _ in range(cmd):
                next_x = x + directions[direction_index][0]
                next_y = y + directions[direction_index][1]
                if (next_x, next_y) not in obstacle_set:  # Check for obstacle
                    x, y = next_x, next_y  # Move to next position
                    max_distance_sq = max(max_distance_sq, x * x + y * y)  # Update max distance

    return max_distance_sq
← Back to All Questions