Walking Robot Simulation II Solution in C++

Explore More Solutions

Problem Description

Ah, the classic “Walking Robot Simulation II” problem! Imagine you have a robot that’s as lost as a tourist in a foreign country, trying to navigate a rectangular grid. The robot starts at the bottom-left corner, facing South, and it can only move along the perimeter of the grid. It’s like a toddler trying to walk in a straight line but constantly bumping into walls.

The robot can take a series of steps, and it needs to know its current position and direction after those steps. If only it had a GPS! But alas, it must rely on our coding skills to figure out where it is.

Code Solution


class Robot {
 public:
  Robot(int width, int height) {
    pos.push_back({{0, 0}, "South"});
    for (int i = 1; i < width; ++i)
      pos.push_back({{i, 0}, "East"});
    for (int j = 1; j < height; ++j)
      pos.push_back({{width - 1, j}, "North"});
    for (int i = width - 2; i >= 0; --i)
      pos.push_back({{i, height - 1}, "West"});
    for (int j = height - 2; j > 0; --j)
      pos.push_back({{0, j}, "South"});
  }

  void step(int num) {
    isOrigin = false;
    i = (i + num) % pos.size();
  }

  vector getPos() {
    return pos[i].first;
  }

  string getDir() {
    return isOrigin ? "East" : pos[i].second;
  }

 private:
  bool isOrigin = true;
  int i = 0;
  vector, string>> pos;
};

Approach

The approach taken in this solution is quite straightforward. The robot’s path is pre-calculated and stored in a vector of positions and directions. When the robot takes a step, it simply updates its index in the vector, wrapping around if it exceeds the number of positions. This way, the robot can efficiently determine its current position and direction without recalculating its path every time.

Time and Space Complexity

Type	Complexity
Time Complexity	O(1) for the `step` and `getPos` methods
Space Complexity	O(n) for storing the positions and directions in the vector

Real-World Example

Think of this robot as a dog on a leash, trying to explore the perimeter of a park. It can only walk along the edges, and if it reaches the end of the path, it just turns around and continues its exploration. Just like that dog, our robot is limited to its path but can still enjoy the view!