Find target using robot movement API
Overview
This question evaluates a candidate's ability to design exploration and state-space search strategies for a robot operating in an unknown, partially blocked 2D grid using a constrained movement and sensing API, testing competency in traversal algorithms, state management, and handling limited observability.
You control a robot in an unknown 2D grid. The grid layout and boundaries are unknown, and you cannot access the map directly. Some cells are blocked (walls), others are open.
Robot API
You can only interact with the environment through these methods:
-
bool move()- Moves the robot forward by 1 cell in the direction it is currently facing.
-
Returns
trueif the move succeeds; returnsfalseif the cell in front is blocked (robot stays in place).
-
void turnLeft()/void turnRight()- Rotates the robot 90 degrees in place.
-
bool isTarget()-
Returns
trueif the robot is currently standing on the target cell.
-
Returns
The robot starts at an unknown start cell (treat it as the origin) facing an unknown but fixed initial direction.
Task
Implement a procedure that finds the target and stops as soon as the robot reaches it.
- You must not rely on any external map/grid representation.
- You must ensure the robot can correctly explore without getting stuck in loops.
- If the target is reachable from the start, your algorithm should eventually reach it.
Output / Interface
Describe or implement a function such as:
-
bool findTarget(Robot& robot)
that returns true if it reaches the target (and stops searching immediately), otherwise false if the target is not reachable after exploring all reachable cells.