2069. Walking Robot Simulation II

Problem¶

Implement a robot that walks around the boundary of a rectangular grid. It starts at the bottom-left cell facing East, turns counterclockwise only when its next step would leave the grid, and reports its position and direction.

Robot(2, 2): start ([0, 0], "East") -> step(4) -> ([0, 0], "South")

class Robot:
    def __init__(self, width: int, height: int):
        pass

    def step(self, num: int) -> None:
        pass

    def getPos(self) -> list[int]:
        pass

    def getDir(self) -> str:
        pass

Key trick¶

The route is a cycle of length \(2(\text{width}+\text{height})-4\). Store the total steps modulo that length, plus whether the robot has ever moved: at the starting cell, those two states have different directions.

Trap¶

Turning when the robot arrives at a corner is too early. It turns only when attempting the next step. A complete lap returns it to the starting cell facing South, not East.

Why is it interesting?¶

The position is periodic, but the initial direction makes the same position represent two different states.

Python solution¶

class Robot:
    def __init__(self, width: int, height: int):
        self.width = width
        self.height = height
        self.perimeter = 2 * (width + height) - 4
        self.offset = 0
        self.moved = False

    def step(self, num: int) -> None:
        self.offset = (self.offset + num) % self.perimeter
        self.moved = True

    def getPos(self) -> list[int]:
        p = self.offset
        w, h = self.width, self.height

        if p < w:
            return [p, 0]

        p -= w - 1
        if p < h:
            return [w - 1, p]

        p -= h - 1
        if p < w:
            return [w - 1 - p, h - 1]

        p -= w - 1
        return [0, h - 1 - p]

    def getDir(self) -> str:
        p = self.offset
        w, h = self.width, self.height

        # Offset zero means either the untouched start or a completed lap.
        if p == 0:
            return "South" if self.moved else "East"
        if p <= w - 1:
            return "East"
        if p <= w + h - 2:
            return "North"
        if p <= 2 * w + h - 3:
            return "West"
        return "South"

Each method takes \(O(1)\) time; the robot uses \(O(1)\) space.

Comment on my solution¶

getDir returns abbreviations instead of the required full names.
The upper corners use width - 1 for their y-coordinate; they need height - 1.
_update_dir turns upon reaching a corner, rather than when the next step is blocked. It also resets the direction to East after a complete lap.
Simulating every step is unnecessary when the walk repeats around the perimeter.

# Wrong Answer: 0/142 testcases passed
# Input
# ["Robot","step","step","getPos","getDir","step","step","step","getPos","getDir"]
# [[6,3],[2],[2],[],[],[2],[1],[4],[],[]]
# Output: [null,null,null,[4,0],"E",null,null,null,[4,5],"W"]
# Expected: [null,null,null,[4,0],"East",null,null,null,[1,2],"West"]
class Robot:

    def __init__(self, width: int, height: int):
        self.width = width
        self.height = height
        self.pos = (0,0)
        self.moves = {"E": (1,0), "N": (0,1), "W":(-1,0), "S": (0,-1)}
        self.direction = "E"

    def _update_dir():
        if self.pos == (self.width - 1, 0):
            self.direction = "N"
        elif self.pos == (self.width - 1, self.width - 1):
            self.direction = "W"
        elif self.pos == (0, self.width - 1):
            self.direction = "S"
        elif self.pos == (0, 0):
            self.direction = "E"

    def step(self, num: int) -> None:
        for _ in range(num):
            self._update_dir()
            move = self.moves[self.direction]
            self.pos = (self.pos[0] + move[0], self.pos[1] + move[1])

    def getPos(self) -> list[int]:
        return list(self.pos)

    def getDir(self) -> str:
        return self.direction

# WRONG
# written after reading AI comments
# Time Limit Exceeded: 77/142 testcases passed
class Robot:

    def __init__(self, width: int, height: int):
        self.width = width
        self.height = height
        self.pos = (0,0)
        self.moves = {"E": (1,0), "N": (0,1), "W":(-1,0), "S": (0,-1)}
        self.direction = "E"

    def _update_dir(self):
        if self.pos == (self.width - 1, 0):
            self.direction = "N"
        elif self.pos == (self.width - 1, self.height - 1):
            self.direction = "W"
        elif self.pos == (0, self.height - 1):
            self.direction = "S"
        elif self.pos == (0, 0):
            self.direction = "E"

    def step(self, num: int) -> None:
        for _ in range(num):
            self._update_dir()
            move = self.moves[self.direction]
            self.pos = (self.pos[0] + move[0], self.pos[1] + move[1])

    def getPos(self) -> list[int]:
        return list(self.pos)

    def getDir(self) -> str:
        if self.direction == "E":
            return "East"
        elif self.direction == "N":
            return "North"
        elif self.direction == "W":
            return "West"
        elif self.direction == "S":
            return "South"