We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Walking Robot Simulation II

Number: 2178

Difficulty: Medium

Paid? No

Companies: Google, Block

Problem Description

We are given a grid defined by a width and a height. A robot initially starts at (0, 0) facing East. For every instruction, the robot is asked to move a given number of steps. At every step, it first attempts to move one cell forward in the direction it is currently facing; if that move would take it out-of-bounds, the robot instead turns 90 degrees counterclockwise (to the next cardinal direction) and then retries the move. We must implement a Robot class with methods to move the robot and to return its current position and facing direction.

Key Insights

  • The robot always travels along the perimeter of the grid.
  • The total number of unique moves before the robot repeats its path is the cycle length: 2*(width + height - 2).
  • Instead of simulating every step for a potentially huge number of moves, we can take the number of steps modulo the cycle length.
  • A key edge case is when the remainder is 0 (and the robot has moved at least once): this implies the robot completed a full cycle. In this case, the position will be (0,0) but the final direction is not “East” (the initial direction) but rather the direction obtained at the end of a full perimeter walk, which is “South”.

Space and Time Complexity

Time Complexity: O(1) per query request, since each call only requires simulating up to four segments. Space Complexity: O(1) since we only store a few integer and string values.

Solution

The approach is to precompute the cycle length, which is the perimeter of the grid excluding the repeating corner (i.e. 2*(width + height - 2)). We maintain a running counter of total steps moved. When step(num) is called, we update this counter and work modulo the cycle. When retrieving the current position and direction, we simulate the robot’s move along the four segments:

  1. Move East for (width - 1) steps.
  2. Move North for (height - 1) steps.
  3. Move West for (width - 1) steps.
  4. Move South for (height - 1) steps. For the effective number of steps r (after modulo) we simulate each segment in sequence until r is exhausted. Special handling is required when r is 0 (and at least one move has been made): we set r equal to the cycle length so that we correctly compute the final direction (“South”) rather than the initial state.

Data structures used are simple integer variables and conditional checks, and the simulation directly computes the final state in constant time.

Code Solutions

Below are the code solutions in Python, JavaScript, C++, and Java. Each snippet is annotated with inline comments for clarity.

class Robot:
    def __init__(self, width: int, height: int):
        # Initialize grid dimensions.
        self.width = width
        self.height = height
        # Total steps taken so far.
        self.total_steps = 0
        # Pre-compute the cycle length (perimeter path length).
        self.cycle = 2 * (width + height - 2)
    
    def step(self, num: int) -> None:
        # Increment the total steps by the given number.
        self.total_steps += num

    def getPos(self) -> [int]:
        # If no steps have been taken, we are at the starting position.
        if self.total_steps == 0:
            return [0, 0]
        
        # Calculate effective remaining steps in the current cycle.
        r = self.total_steps % self.cycle
        # Special handling: If r is 0 (and the robot has moved),
        # then the robot has completed an entire cycle.
        if r == 0:
            r = self.cycle
        
        # Compute boundaries for each direction segment.
        eastLen = self.width - 1
        northLen = self.height - 1
        westLen = self.width - 1
        southLen = self.height - 1
        
        # Initialize position.
        x, y = 0, 0
        
        # Simulate moving east.
        if r <= eastLen:
            x += r
            return [x, y]
        # Complete east segment.
        x = self.width - 1
        r -= eastLen
        
        # Simulate moving north.
        if r <= northLen:
            y += r
            return [x, y]
        # Complete north segment.
        y = self.height - 1
        r -= northLen
        
        # Simulate moving west.
        if r <= westLen:
            x -= r
            return [x, y]
        # Complete west segment.
        x = 0
        r -= westLen
        
        # The remaining r must be in the south segment.
        y -= r
        return [x, y]

    def getDir(self) -> str:
        # If no steps have been taken, still facing East.
        if self.total_steps == 0:
            return "East"
        
        # Calculate effective steps in the current cycle.
        r = self.total_steps % self.cycle
        if r == 0:
            r = self.cycle
        
        eastLen = self.width - 1
        northLen = self.height - 1
        westLen = self.width - 1
        southLen = self.height - 1
        
        # Determine the current facing direction based on the remainder.
        if r <= eastLen:
            # Currently moving east.
            return "East"
        r -= eastLen
        
        if r <= northLen:
            return "North"
        r -= northLen
        
        if r <= westLen:
            return "West"
        # Remaining steps put the robot in the south segment.
        return "South"

# Example usage:
# robot = Robot(6, 3)
# robot.step(2)
# robot.step(2)
# print(robot.getPos())  # Expected output: [4, 0]
# print(robot.getDir())  # Expected output: "East"
← Back to All Questions