Walking Robot Simulation in Python

Explore Solutions in Other Languages

Code Solution


class Solution:
    def robotSim(self, commands: list[int], obstacles: list[list[int]]) -> int:
        dirs = ((0, 1), (1, 0), (0, -1), (-1, 0))
        ans = 0
        d = 0  # 0 := north, 1 := east, 2 := south, 3 := west
        x = 0  # the start x
        y = 0  # the start y
        obstaclesSet = {(x, y) for x, y in obstacles}

        for command in commands:
            if command == -1:
                d = (d + 1) % 4
            elif command == -2:
                d = (d + 3) % 4
            else:
                for _ in range(command):
                    if (x + dirs[d][0], y + dirs[d][1]) in obstaclesSet:
                        break
                    x += dirs[d][0]
                    y += dirs[d][1]
            ans = max(ans, x * x + y * y)

        return ans

Problem Description

Welcome to the world of Walking Robot Simulation, where your robot is as confused as a cat in a dog park! Imagine a little robot that can move around in a 2D grid, but instead of following a simple path, it has a mind of its own. It can turn left, turn right, or move forward, but it also has to dodge obstacles like a ninja avoiding a surprise attack.

The robot starts at the origin (0, 0) and faces north. It can receive a series of commands:

Positive integers tell it how many steps to move forward.
A -1 command makes it turn right (90 degrees).
A -2 command makes it turn left (90 degrees).

But wait! There are obstacles! If the robot tries to move into an obstacle, it stops right there, like a kid who just spotted a spider. Your task is to calculate the maximum Euclidean distance squared from the origin that the robot can reach after executing all the commands.

Approach

The code uses a simple simulation approach:

It initializes the robot’s position and direction.
It processes each command:
- For turning commands, it updates the direction.
- For movement commands, it checks for obstacles and updates the position accordingly.
It keeps track of the maximum distance squared from the origin.

Time and Space Complexity

Time Complexity: O(N), where N is the number of commands. Each command is processed in constant time, and the inner loop runs at most the number of steps in the command.

Space Complexity: O(K), where K is the number of obstacles, as we store them in a set for quick lookup.

Real-World Example

Think of this robot as a toddler learning to walk in a crowded park. It can move forward, but if it encounters a tree (obstacle), it has to stop and change direction. The goal is to see how far it can wander off from the starting point before getting stuck or turned around.