Detect Repeated State Cycles in a Trajectory

mediumPROAgent Loop Control & PlanningAI AgentsAI Agents 1

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:

Example

Input

print(shortest_cycle(["a", "b", "c", "b"]))

Output

Reasoning

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.

Learn this in

Workflow Patterns & LangGraph Stateful GraphsAgent Engineering Study Plan

More from AI Agents 1

Cheapest Cache TTL Meeting a Freshness SLAhard Bootstrap Confidence Interval Width for Eval Accuracymedium Route to the Cheapest Model Meeting Qualitymedium pass@k Estimatormedium Savings from a Semantic Cachemedium

Concept primerPREVIEW

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.

PRO

Continue the full explanation

You're reading the free preview. Unlock the complete walkthrough, the code editor, test runner and reference solution with Premium.

PRO

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.

solution.py

Python 3.13

Test results