Leetcode Daily Question 04/09/2024 - 874. Walking Robot Simulation

Problem Description:

A robot on an infinite XY-plane starts at point (0, 0) facing north. The robot can receive a sequence of these three possible types of commands: -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 ith obstacle is at grid point obstacles[i] = (xi, yi). If the robot runs into an obstacle, then it will instead stay in its current location and move on to the next command. Return the maximum Euclidean distance that the robot ever gets from the origin squared (i.e. if the distance is 5, return 25). Note: North means +Y direction. East means +X direction. South means -Y direction. West means -X direction. There can be obstacle in [0,0].

from typing import List
class Solution:
  def robotSim(self, commands: List[int], obstacles: List[List[int]]) -> int:
    directions = [(0,1),(1,0),(0,-1),(-1,0)]
    x, y = 0, 0
    max_dist = float('-inf')
    curr_dir = 0
    
    obstacles_set = frozenset(map(tuple, obstacles))
    
    for command in commands:
      if command == -1:
        curr_dir = (curr_dir + 1) % 4
      elif command == -2:
        curr_dir = (curr_dir + 3) % 4
      
      else:
      	dx, dy = directions[curr_dir]
        for _ in range(command):
          if (x + dx, y + dy) not in obstacles_set:
            x += dx
            y += dy
            max_dist = max(max_dist, x**2 + y**2)
          else:
            break
        
      
    return max_dist

Explanation:

The tricky part about this question is understanding how the obstacles work. If there is an obstacle at (0,0), we still continue to move forward by ignoring the current command to move.

We also need to make looking up obstacles efficient. To do this, we shall make obstacles into a hash-frozenset.

The difference between a set and frozenset is that frozenset is immutable.

Let's initialise these variables

def robotSim(commands, obstacles):
  directions = [(0,1),(1,0),(0,-1),(-1,0)] # These tuples represents North, East, South and West resp.
  curr_dir = 0 # This is the direction index, we use this to decide which direction we are in.
  x, y = 0, 0
  max_dist = float('-inf') # Our goal is to find the max dist x, y is from origin after every command.
  
  obstacle_set = frozenset(map(tuple,obstacles)) # Since list is not hashable, we first turn all obstacles 
  												 # from lists to tuples, then hash it, then make it into set.

Now we iterate through the commands.

If the command is -1, this means turn right. So we increment our curr_dir by 1 (clockwise rotation by pi/2).

If the command is -2, this means turn left. So we increment our curr_dir by 3 (anti-clockwise rotation by pi/2).

We also take modulo 4 to ensure our index stays within 0-3.

If the command is a positive integer, this means we move that many steps in that direction.

We do this by incrementing x, y in our direction one step at a time.

This allows us to check if the resulting coordinates is an obstacle or not. We also check our euclidean distance against max_dist everytime we move a step.

for command in commands:
  if command == -1:
    curr_dir = (curr_dir + 1) % 4
  elif command == -2:
    curr_dir = (curr_dir + 3) % 4
  else:
    dx, dy = directions[curr_dir]
    for _ in range(command):
      if (x + dx, y + dy) not in obstacle_set:
        x += dx
        y += dy
        max_dist = max(max_dist, x ** 2 + y ** 2)
      else:
        break
  
return max_dist

The time complexity is O(n+m) as we traverse through the entire commands array and the entire obstacles array to convert it into a hash-frozenset.

The space complexity is O(m) as we need store the obstacles in a separate hash-frozenset.

The full solution can be found near the top of the page.