A robot starts at (0, 0) on an infinite grid, facing north (the +y direction). It runs a list of integer commands:
-2: turn left 90 degrees;-1: turn right 90 degrees;1to9: walk forward that many squares, one square at a time. If the next square holds an obstacle, the robot stays where it is and skips the rest of this command.
obstacles is a list of [x, y] squares. Write robot_sim(commands, obstacles) that returns the largest squared distance x*x + y*y from the origin the robot ever reaches (including 0 at the start).
1 <= len(commands) <= 10^4;0 <= len(obstacles) <= 10^4; obstacle coordinates are in[-3 * 10^4, 3 * 10^4].- An obstacle may sit at
(0, 0). The robot starts on it without trouble but can never step back onto it. - Scanning the obstacle list on every step is far too slow: aim for O(total steps + number of obstacles).
robot_sim([3, -1, 4], []) # 25 ends at (4, 3)
robot_sim([3, -1, 4], [[2, 3]]) # 10 blocked at (1, 3)
robot_sim([-2, -2, 5], [[0, -3]]) # 4 walks south, stops at (0, -2)
Show hint
put the obstacles in a set so each step is one O(1) lookup. For turning, store the four directions in clockwise order and keep an index into them.