Determine if robot path is bounded

A robot starts at (0, 0) facing North on an infinite grid. It executes a string s consisting of 'G' (move forward 1 unit), 'L' (turn left 90°), and 'R' (turn right 90°) once, then repeats s forever. Return true if the robot stays within a bounded circle; otherwise return false. Justify your reasoning, discuss edge cases, and provide code.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Determine if Robot Path Is Bounded

A robot starts at position (0, 0) on an infinite grid, initially facing North. It is given a string instructions consisting of three kinds of characters:

• 'G': move forward 1 unit in the current direction.
• 'L': turn 90 degrees to the left (counter-clockwise) without moving.
• 'R': turn 90 degrees to the right (clockwise) without moving.

The robot executes the entire string once, then repeats the same string forever. Return true if and only if there exists a circle of finite radius such that the robot never leaves it (i.e. its path is bounded); otherwise return false.

The crucial observation: simulate exactly ONE pass over instructions. After one pass, the robot is at some offset (x, y) and facing some direction. The path is bounded if and only if (a) it ends back at the origin (0, 0), OR (b) it does NOT end up facing North (its original direction). If it ends facing North but displaced from the origin, every cycle adds the same nonzero displacement and the robot drifts to infinity; if it ends facing any other direction, the cumulative rotation guarantees the net displacement cancels out within at most 4 cycles, keeping it within a bounded region.

Constraints

• 1 <= instructions.length <= 100 (the empty string is also handled and is trivially bounded)
• instructions consists only of the characters 'G', 'L', and 'R'
• Coordinates fit comfortably in standard integer types within the constraint bounds

Examples

Example 1

Input: ("GGLLGG",)
Output: True

Explanation: Pass: G->(0,1), G->(0,2), L (now West), L (now South), G->(0,1), G->(0,0). Ends at origin, so bounded -> True.

Example 2

Input: ("GG",)
Output: False

Explanation: No turns: robot moves straight North forever, displacement (0,2) per cycle while still facing North. Unbounded -> False.

Hints

1. You don't need to simulate forever — the behavior of all infinite repetitions is fully determined by ONE pass over the string. Track the final offset and final facing direction.
2. Represent the four headings as direction vectors in clockwise order: North (0,1), East (1,0), South (0,-1), West (-1,0). A right turn is index +1 mod 4; a left turn is index +3 mod 4 (equivalently -1 mod 4).
3. After one pass, the path is bounded iff the robot is back at the origin OR it is no longer facing North. If it faces North but is displaced, each cycle adds the same nonzero vector and it escapes to infinity. If it faces any other direction, the rotation makes the net 4-cycle displacement zero, so it stays bounded.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

A robot starts at (0, 0) facing North on an infinite grid. It executes a string s consisting of 'G' (move forward 1 unit), 'L' (turn left 90°), and 'R' (turn right 90°) once, then repeats s forever. Return true if the robot stays within a bounded circle; otherwise return false. Justify your reasoning, discuss edge cases, and provide code.

Recommended Approach

Model the states explicitly and use BFS for unweighted shortest paths, Dijkstra for weighted non-negative paths, or topological DP for DAGs. Track visited states at the right granularity so cycles do not cause repeated work.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

BFS is O(V + E) time and O(V) space for a standard graph. Expanded-state problems multiply those bounds by the number of state dimensions.

Edge Cases and Tests

Disconnected graph, source equals target, cycles, duplicate edges, unreachable target, and whether the answer counts nodes, edges, moves, or transfers.