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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Walking Robot Simulation

Number: 906

Difficulty: Medium

Paid? No

Companies: Shopify, PhonePe, Jane Street

Problem Description

A robot moves on an infinite 2D grid following a series of commands. Commands can instruct the robot to turn 90 degrees left/right or to move forward a given number of steps. The grid also contains obstacles. If the robot encounters an obstacle during a move, it stops before the obstacle and continues with the next command. The goal is to compute the maximum squared Euclidean distance from the origin reached by the robot during its journey.

Key Insights

  • Use directional vectors (north, east, south, west) with an index for easy rotation.
  • Store obstacles in a set for O(1) lookup when checking if the next position is blocked.
  • Process each command; for move commands, simulate step-by-step movement checking for obstacles.
  • Update the answer as the maximum of x² + y² after each valid step.

Space and Time Complexity

Time Complexity: O(S) where S is the total number of steps taken (each command may involve up to 9 steps).
Space Complexity: O(O) where O is the number of obstacles stored in the hash set.

Solution

The solution uses a simulation approach:

  1. Initialize the starting point (0, 0) facing north.
  2. Represent directions using two arrays dx and dy. For example, with index 0 as north, dx = [0, 1, 0, -1] and dy = [1, 0, -1, 0].
  3. Convert the obstacles list into a set for quick lookup.
  4. Loop through each command: adjust the current direction for turning commands (-1 and -2) using modulus arithmetic.
  5. For forward movement commands, move one unit at a time. Before each step, check if the new position is an obstacle.
  6. Keep track of the maximum squared distance reached.
  7. Return the maximum squared distance after processing all commands.

Code Solutions

Below are code solutions in multiple languages with detailed comments.

# Define the function to simulate the robot's movement.
def robot_sim(commands, obstacles):
    # Convert list of obstacles to a set for O(1) lookups.
    obstacle_set = {(ox, oy) for ox, oy in obstacles}
    # Direction vectors for north, east, south, west.
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    x = y = 0  # Starting coordinates.
    direction = 0  # 0 corresponds to north.
    max_distance_sq = 0  # Track maximum squared distance.
    
    # Process each command in the commands list.
    for command in commands:
        if command == -2:  # Turn left 90 degrees.
            direction = (direction + 3) % 4
        elif command == -1:  # Turn right 90 degrees.
            direction = (direction + 1) % 4
        else:
            # Move forward command steps one unit at a time.
            for _ in range(command):
                next_x = x + dx[direction]
                next_y = y + dy[direction]
                # If next position is not an obstacle, update position.
                if (next_x, next_y) not in obstacle_set:
                    x, y = next_x, next_y
                    max_distance_sq = max(max_distance_sq, x * x + y * y)
                else:
                    # Obstacle encountered; stop moving for this command.
                    break
                    
    return max_distance_sq

# Example usage:
if __name__ == "__main__":
    print(robot_sim([4, -1, 3], []))  # Expected output: 25
← Back to All Questions