Design robot path boundedness with repeats
Problem Description
You are tasked with designing an algorithm to simulate a robot's movement on a 2D grid and determine the boundedness of its path under infinite repetitions of its instruction set.
The robot starts at coordinates (0, 0) facing North. The grid contains a set of blocked cells (obstacles) that the robot cannot enter.
The robot executes a finite instruction string S composed of the following commands:
G: Move forward 1 unit. If the next cell in the current direction is blocked, the robot stays in its current position.L: Turn left 90 degrees.R: Turn right 90 degrees.- Digits
2through9: Repeat the immediately preceding command that many additional times. For example,G3means move forward a total of 3 steps (1 original + 2 additional), andR2means turn right a total of 2 times (1 original + 1 additional).
Your algorithm must perform two main tasks:
- After one complete execution of the instruction string
S, report the robot's final (x, y) coordinates and its final heading (North, East, South, or West). - Determine whether the robot's path is bounded if the instruction string
Sis repeated infinitely. A path is considered bounded if there exists a fixed square of side lengthBthat contains all visited positions under infinite repetitions. Returntrueif bounded,falseotherwise.
The design of your algorithm must avoid simulating an unbounded number of steps. You should also analyze its time and space complexity.
AI interview prep
Core dilemma
The central engineering conflict is determining the boundedness of an infinitely repeating path without performing infinite simulation. This requires identifying repeating states or patterns in the robot's movement and direction, especially when obstacles are present, which can alter expected trajectories and prevent simple geometric analysis.
3 tradeoffs and 3 stress tests locked
Interview prep
Unlock the interviewer X-Ray rubric, tradeoff matrix, stress tests, clarifying questions, and key concepts.
Design robot path boundedness with repeats
Problem Description
You are tasked with designing an algorithm to simulate a robot's movement on a 2D grid and determine the boundedness of its path under infinite repetitions of its instruction set.
The robot starts at coordinates (0, 0) facing North. The grid contains a set of blocked cells (obstacles) that the robot cannot enter.
The robot executes a finite instruction string S composed of the following commands:
G: Move forward 1 unit. If the next cell in the current direction is blocked, the robot stays in its current position.L: Turn left 90 degrees.R: Turn right 90 degrees.- Digits
2through9: Repeat the immediately preceding command that many additional times. For example,G3means move forward a total of 3 steps (1 original + 2 additional), andR2means turn right a total of 2 times (1 original + 1 additional).
Your algorithm must perform two main tasks:
- After one complete execution of the instruction string
S, report the robot's final (x, y) coordinates and its final heading (North, East, South, or West). - Determine whether the robot's path is bounded if the instruction string
Sis repeated infinitely. A path is considered bounded if there exists a fixed square of side lengthBthat contains all visited positions under infinite repetitions. Returntrueif bounded,falseotherwise.
The design of your algorithm must avoid simulating an unbounded number of steps. You should also analyze its time and space complexity.