Trajectory Matching

The problem, from first principles

Sometimes the path matters, not just the final answer: in a support workflow the agent must look up the account before issuing a refund, and verify identity before either. Comparing the sequence of tool names the agent used with a reference sequence checks this. Exact equality is too strict, since extra harmless calls are fine, and a set comparison ignores order. The longest common subsequence (LCS) is the natural middle ground: the longest sequence of steps appearing in both lists in the same relative order, with other steps allowed in between. Normalizing by the lengths gives an order-aware precision and recall.

From theory to code

Implement lcs_length and trajectory_match.

Constraints

• lcs_length(a, b) is the length of the longest common subsequence of two lists, computed by dynamic programming.
• trajectory_match(actual, reference) returns (precision, recall, in_order): precision = lcs / len(actual) and recall = lcs / len(reference) (0.0 for an empty denominator), and in_order is True iff lcs == len(reference), meaning every reference step appears in order inside the actual trajectory.

Hints