Walking Robot Simulation Solution in C++

Explore More Solutions

Problem Description

Ah, the classic “Walking Robot Simulation” problem! Imagine you have a robot that’s as confused as a cat in a dog park. It can move around in a 2D grid, but it has a peculiar way of navigating. It follows a series of commands that tell it to move forward or turn left/right. But wait! There are obstacles in its path—like that annoying coffee table you keep stubbing your toe on. The challenge is to determine how far the robot can go from its starting point before it runs into something.

In simpler terms, you’re trying to figure out the maximum distance squared from the origin (0, 0) that the robot can reach while avoiding obstacles. It’s like trying to find the best route to the fridge without bumping into your roommate!

Code Solution


class Solution {
 public:
  int robotSim(vector& commands, vector>& obstacles) {
    constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int ans = 0;
    int d = 0;  // 0 := north, 1 := east, 2 := south, 3 := west
    int x = 0;  // the start x
    int y = 0;  // the start y
    unordered_set, PairHash> obstaclesSet;

    for (const vector& obstacle : obstacles) {
      const int x = obstacle[0];
      const int y = obstacle[1];
      obstaclesSet.insert({x, y});
    }

    for (const int command : commands) {
      if (command == -1) {
        d = (d + 1) % 4;
      } else if (command == -2) {
        d = (d + 3) % 4;
      } else {
        for (int step = 0; step < command; ++step) {
          if (obstaclesSet.contains({x + dirs[d][0], y + dirs[d][1]}))
            break;
          x += dirs[d][0];
          y += dirs[d][1];
        }
      }
      ans = max(ans, x * x + y * y);
    }

    return ans;
  }

 private:
  struct PairHash {
    size_t operator()(const pair& p) const {
      return p.first ^ p.second;
    }
  };
};

Approach

The approach taken in this solution is straightforward yet effective. The robot starts at the origin (0, 0) and faces north. It processes a list of commands that either instruct it to turn or move forward. The robot keeps track of its direction using an index that cycles through an array representing the four cardinal directions.

When the robot attempts to move, it checks if the next position is occupied by an obstacle. If it is, the robot stops moving in that direction. The maximum distance squared from the origin is updated after each command, ensuring that we capture the furthest point the robot can reach.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N + M), where N is the number of commands and M is the number of obstacles.
Space Complexity	O(M) for storing the obstacles in a hash set.

Real-World Example

Imagine you’re a robot trying to navigate your way through a crowded kitchen filled with obstacles like chairs, tables, and that one cat that always seems to be in the way. You have a set of commands to follow, but you need to avoid stepping on the cat (or the coffee table). This problem is akin to that scenario, where you need to calculate how far you can go without causing a disaster!