Link: https://leetcode.com/problems/walking-robot-simulation/
Solution:
Topics: simulation
Intuition
This is not a very difficult problem, but it has some edge cases that must be considered. My first solution was a very bloated implementation, so If anything it’s a clean implementation challenge.
Implementation
def walking_robot(commands, obstacles):
obstacles = set([tuple(obs) for obs in obstacles])
dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
max_dist = 0
curr_dir = 0
x, y = 0, 0
for c in commands:
if c == -1:
curr_dir += 1
curr_dir %= 4
elif c == -2:
curr_dir -= 1
curr_dir %= 4
else:
a, b = dirs[curr_dir]
for _ in range(c):
if (x+a, y+b) in obstacles:
break
x += a
y += b
max_dist = max(max_dist, x*x + y*y)
return max_dist
#time: o(9n)
#memory: o(len(obstacles))Review 1
Fun problem! The key to remember for clean implementation in these euclidian simulation problems is to create a directions array that whose tuple represents one unit of movement in that direction if added to the current position.
For example:
Lets say we are starting at positon (0,0), how do we go up by one unit?
add (0, 1) to the position!
Therefore...
dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
up right left down
So if we need to move n steps down, add (-1, 0) to the current position n times!
Of course we don’t have to do it this way, but it gets bloated quick.