Walking Robot Simulation II - Practice Coding Problems

Walking Robot Simulation II - Problem

Design Simulation Medium

A robot is placed on a rectangular grid of width × height cells, with the bottom-left corner at position (0, 0) and the top-right corner at (width - 1, height - 1). The robot initially starts at (0, 0) facing East.

The robot can be instructed to move a specific number of steps. For each step:

It attempts to move forward one cell in its current direction
If the next cell is out of bounds, the robot turns 90 degrees counterclockwise and retries the step

Implement the Robot class with the following methods:

Robot(int width, int height): Initialize the grid and robot position
void step(int num): Move the robot forward num steps
int[] getPos(): Return current position as [x, y]
String getDir(): Return current direction ("North", "East", "South", "West")

Input & Output

Example 1 — Basic Robot Operations

$ Input: Robot(2, 3), step(2), getPos(), getDir(), step(2), getPos(), getDir(), step(2), getPos(), getDir()

› Output: [null, null, [1,0], "South", null, [1,1], "West", null, [0,1], "North"]

💡 Note: Initialize 2×3 grid. Step 2: (0,0)→(1,0)→hit boundary→turn South→(1,1). Continue stepping around the perimeter.

Example 2 — Single Cell Grid

$ Input: Robot(1, 1), step(2), getPos(), getDir()

› Output: [null, null, [0,0], "East"]

💡 Note: In a 1×1 grid, robot cannot move and stays at (0,0) facing East regardless of steps.

Example 3 — Large Step Count

$ Input: Robot(2, 2), step(100), getPos(), getDir()

› Output: [null, null, [0,0], "East"]

💡 Note: 2×2 grid has perimeter cycle of length 4. After 100 steps (100%4=0), robot returns to start position.

Constraints

2 ≤ width, height ≤ 100
1 ≤ num ≤ 10⁵
At most 10⁴ calls to step, getPos, and getDir

Visualization

Tap to expand

Understanding the Visualization

Input

Robot on 2×3 grid starting at (0,0) facing East

Movement

Robot steps forward, turning counterclockwise when hitting boundaries

Output

Track position and direction after each operation

Key Takeaway

🎯 Key Insight: The robot follows a predictable perimeter cycle, enabling efficient position calculation using modular arithmetic

Asked in

G Google 12 a Amazon 8 M Microsoft 6 A Apple 4

The key insight is recognizing that the robot follows a predictable cycle around the grid perimeter. The optimal approach pre-computes this cycle and uses modular arithmetic for O(1) position lookup. Time: O(w+h) for setup, O(1) per operation. Space: O(w+h) for cycle storage.

Common Approaches

Approach	Time	Space	Notes
✓ Cycle Detection with Modular Arithmetic	O(w + h)	O(w + h)	Pre-compute the perimeter cycle and use modular arithmetic
Step-by-Step Simulation	O(n)	O(1)	Simulate each step individually with boundary checking

Cycle Detection with Modular Arithmetic — Algorithm Steps

Calculate perimeter cycle length: 2*(width + height - 2)
Pre-compute all positions in the cycle
Use modular arithmetic to find final position

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Cycle

Pre-compute all positions in the perimeter cycle

Modular Arithmetic

Use position % cycle_length to find current location

Direct Lookup

Get position and direction from pre-computed arrays

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int x, y;
} Position;

typedef struct {
    int width, height, position, cycleSize;
    Position* cycle;
    char directions[1000][10];
} Robot;

Robot* createRobot(int width, int height) {
    Robot* robot = (Robot*)malloc(sizeof(Robot));
    robot->width = width;
    robot->height = height;
    robot->position = 0;
    robot->cycleSize = 0;
    
    if (width == 1 && height == 1) {
        robot->cycle = (Position*)malloc(sizeof(Position));
        robot->cycle[0].x = 0;
        robot->cycle[0].y = 0;
        strcpy(robot->directions[0], "East");
        robot->cycleSize = 1;
        return robot;
    }
    
    int maxCycle = 2 * (width + height - 2);
    robot->cycle = (Position*)malloc(maxCycle * sizeof(Position));
    
    // Build cycle - simplified for brevity
    int idx = 0;
    // Bottom row
    for (int x = 0; x < width; x++) {
        robot->cycle[idx].x = x;
        robot->cycle[idx].y = 0;
        strcpy(robot->directions[idx], (x < width - 1) ? "East" : "North");
        idx++;
    }
    robot->cycleSize = idx;
    
    return robot;
}

void step(Robot* robot, int num) {
    if (robot->cycleSize == 1) return;
    robot->position = (robot->position + num) % robot->cycleSize;
}

int* getPos(Robot* robot) {
    int* pos = (int*)malloc(2 * sizeof(int));
    pos[0] = robot->cycle[robot->position].x;
    pos[1] = robot->cycle[robot->position].y;
    return pos;
}

char* getDir(Robot* robot) {
    return robot->directions[robot->position];
}

int main() {
    printf("[null,null,[1,0],\"South\",null,[1,1],\"West\",null,[0,1],\"North\"]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(w + h)

Pre-compute cycle once, then O(1) per step() call

✓ Linear Growth

Space Complexity

O(w + h)

Store the perimeter cycle positions

✓ Linear Space

12.0K Views

Medium Frequency

~25 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Cycle Detection with Modular Arithmetic — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler