Walking Robot Simulation II

medium design simulation modular arithmetic

Problem

A width × height grid has the bottom-left cell at (0, 0) and the top-right at (width−1, height−1). A robot starts at (0, 0) facing East. On step(num) it tries to move forward one cell num times; if the next cell is out of bounds it turns 90° counterclockwise and retries that step. So the robot forever circles the perimeter. Implement getPos() (current [x, y]) and getDir() (one of "North", "East", "South", "West").

Key subtlety: once the robot has moved at all, whenever it lands back on (0, 0) it faces South, not East.

InputRobot(6, 3); step(2); step(2); getPos(); getDir()

Output[4, 0], "East"

Two steps East then two more reach (4, 0) along the bottom edge, still facing East.

width

height

operations (e.g. step 2, step 2, getPos, getDir)

class Robot:
    def __init__(self, width, height):
        self.w = width
        self.h = height
        self.perim = 2 * (width + height - 2)   # perimeter cell count
        self.pos = 0                            # steps walked along perimeter
        self.moved = False                      # has the robot ever moved?

    def step(self, num):
        self.moved = True
        self.pos = (self.pos + num) % self.perim

    def getPos(self):
        w, h, p = self.w, self.h, self.pos
        if p < w:                       # bottom edge: (0,0)->(w-1,0)
            return [p, 0]
        p -= (w - 1)
        if p < h:                       # right edge: (w-1,0)->(w-1,h-1)
            return [w - 1, p]
        p -= (h - 1)
        if p < w:                       # top edge: (w-1,h-1)->(0,h-1)
            return [w - 1 - p, h - 1]
        p -= (w - 1)
        return [0, h - 1 - p]           # left edge: (0,h-1)->(0,0)

    def getDir(self):
        w, h, p = self.w, self.h, self.pos
        if p == 0:                      # back at origin
            return "South" if self.moved else "East"
        if p < w:
            return "East"
        p -= (w - 1)
        if p < h:
            return "North"
        p -= (h - 1)
        if p < w:
            return "West"
        return "South"

class Robot {
  constructor(width, height) {
    this.w = width;
    this.h = height;
    this.perim = 2 * (width + height - 2); // perimeter cell count
    this.pos = 0;                          // steps walked along perimeter
    this.moved = false;                    // has the robot ever moved?
  }

  step(num) {
    this.moved = true;
    this.pos = (this.pos + num) % this.perim;
  }

  getPos() {
    const w = this.w, h = this.h;
    let p = this.pos;
    if (p < w) return [p, 0];             // bottom edge
    p -= (w - 1);
    if (p < h) return [w - 1, p];         // right edge
    p -= (h - 1);
    if (p < w) return [w - 1 - p, h - 1]; // top edge
    p -= (w - 1);
    return [0, h - 1 - p];                // left edge
  }

  getDir() {
    const w = this.w, h = this.h;
    let p = this.pos;
    if (p === 0) return this.moved ? "South" : "East";
    if (p < w) return "East";
    p -= (w - 1);
    if (p < h) return "North";
    p -= (h - 1);
    if (p < w) return "West";
    return "South";
  }
}

class Robot {
    int w, h, perim, pos;
    boolean moved;

    public Robot(int width, int height) {
        w = width;
        h = height;
        perim = 2 * (width + height - 2); // perimeter cell count
        pos = 0;                          // steps walked along perimeter
        moved = false;                    // has the robot ever moved?
    }

    public void step(int num) {
        moved = true;
        pos = (pos + num) % perim;
    }

    public int[] getPos() {
        int p = pos;
        if (p < w) return new int[]{p, 0};             // bottom edge
        p -= (w - 1);
        if (p < h) return new int[]{w - 1, p};         // right edge
        p -= (h - 1);
        if (p < w) return new int[]{w - 1 - p, h - 1}; // top edge
        p -= (w - 1);
        return new int[]{0, h - 1 - p};                // left edge
    }

    public String getDir() {
        int p = pos;
        if (p == 0) return moved ? "South" : "East";
        if (p < w) return "East";
        p -= (w - 1);
        if (p < h) return "North";
        p -= (h - 1);
        if (p < w) return "West";
        return "South";
    }
}

class Robot {
    int w, h, perim, pos = 0;
    bool moved = false;
public:
    Robot(int width, int height) {
        w = width;
        h = height;
        perim = 2 * (width + height - 2); // perimeter cell count
    }

    void step(int num) {
        moved = true;
        pos = (pos + num) % perim;
    }

    vector<int> getPos() {
        int p = pos;
        if (p < w) return {p, 0};             // bottom edge
        p -= (w - 1);
        if (p < h) return {w - 1, p};         // right edge
        p -= (h - 1);
        if (p < w) return {w - 1 - p, h - 1}; // top edge
        p -= (w - 1);
        return {0, h - 1 - p};                // left edge
    }

    string getDir() {
        int p = pos;
        if (p == 0) return moved ? "South" : "East";
        if (p < w) return "East";
        p -= (w - 1);
        if (p < h) return "North";
        p -= (h - 1);
        if (p < w) return "West";
        return "South";
    }
};

Explanation

The robot can only ever travel along the perimeter of the grid, because the moment a forward move would leave the grid it turns left and keeps hugging the wall. So instead of simulating each of the up to 10⁵ steps per call, we track a single number: pos, the distance walked clockwise-... actually counter-clockwise around that loop, taken modulo the perimeter length.

The perimeter has perim = 2 × (width + height − 2) cells. Each step(num) just does pos = (pos + num) % perim in O(1), no matter how large num is.

To answer getPos() we unfold pos along the four edges in order: bottom (East), right (North), top (West), left (South). We subtract each edge's length as we pass it and land on the correct cell. This is also O(1).

The one trap is direction at the origin. Before the robot has moved it faces East. But once it has moved and later returns to (0, 0) (so pos == 0), it has just finished the left edge heading down, so it faces South. The moved flag distinguishes the two cases.

For every other cell, the facing direction is fixed by which edge the cell sits on: bottom → East, right → North, top → West, left → South.

Time: O(1) per call Space: O(1)