Detect Repeated State Cycles in a Trajectory
Problem Statement
An agent revisiting the same environment state is likely looping. Given a trajectory of state hashes, find the length of the shortest cycle (distance between two equal states), or 0 if no state repeats.
Background
Scan the state sequence keeping the last index each state was seen. When a state recurs at index j having been seen at i, the cycle length is j - i. Return the minimum such length across the trajectory; 0 if all states are distinct.
Your Task
def shortest_cycle(states):
Return the shortest repeat distance, or 0.
Input Format
- states (list of hashable state ids).
Output Format
- A single int.
Sample
print(shortest_cycle(["a", "b", "c", "b"]))
Output:
2
Example:
print(shortest_cycle(["a", "b", "c", "b"]))
2
- Initialize a tracker for the last seen index of each state and set the best cycle length to 0, preparing to scan the sequence
["a", "b", "c", "b"]. - Process the first three states
"a","b", and"c"at indices 0, 1, and 2; since none have appeared before, record their indices in the tracker without updating the cycle length. - Encounter state
"b"again at index 3; look up its previous index (1) to calculate the distance 3−1=2. - Compare this distance (2) against the current best (0); since 2 is smaller than infinity (or the initial zero flag indicating no cycle found), update the best cycle length to 2.
- The final output is 2
Constraints:
- Cycle length is the index gap between consecutive equal states.
- Track the most recent index of each state.
- Return 0 if no state repeats.
1. Background Knowledge
In reinforcement learning and AI agent design, an agent loop repeatedly observes a state, selects an action, and transitions to a new state. A critical failure mode is the infinite loop, where the agent revisits a sequence of states without making progress. Detecting these cycles early allows the agent to break out, reset, or switch strategies.
The problem reduces to a classic sequence analysis task: given a list of hashable identifiers (state hashes), determine if any element appears more than once. If a state s appears at index i and again at index j (where j>i), the cycle length is the distance j−i. We are interested in the minimum such distance across all repeated states.
This is distinct from finding the longest cycle or detecting all cycles. We only care about the shortest repeat distance, which often indicates the tightest loop the agent is stuck in.
2. Algorithm Approach
The optimal approach uses a hash map (dictionary) to store the last seen index of each state. As you iterate through the trajectory:
- Check if the current state has been seen before.
- If yes, compute the distance from the last recorded index to the current index.
- Update the global minimum cycle length if this distance is smaller.
- Update the hash map to store the current index for this state (this is crucial for finding the shortest cycle, not just any cycle).
This is a single-pass linear scan with O(1) average-case lookups, making it efficient for long trajectories.
3. Step-by-Step Strategy
- Initialize a dictionary last_seen to map state hashes to their most recent index.
- Initialize a variable min_cycle to infinity (or a very large number).
- Iterate through the states list with index i:
- If states[i] is already in last_seen:
- Compute cycle_len = i - last_seen[states[i]].
- Update min_cycle = min(min_cycle, cycle_len).
- Update last_seen[states[i]] = i (always overwrite with the latest index).
- After the loop, if min_cycle is still infinity, return 0 (no repeats).
- Otherwise, return min_cycle.
Continue the full explanation
You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.
Editor locked
The code editor is locked for Pro problems. It is only available for free problems. Please upgrade to gain access to the code editor for all problems.