📘

Route a Tool Name with Fuzzy Matching

Problem Statement

Models sometimes hallucinate a slightly wrong tool name (get_wether instead of get_weather). Route the requested name to the closest registered tool if it is within an edit-distance threshold.

Background

Compute the Levenshtein edit distance (insertions, deletions, substitutions, cost 1 each) between the requested name and every registered tool. Pick the tool with the smallest distance; if that distance is <= max_dist, route to it, else return None. Ties are broken by the tool that sorts first alphabetically.

Your Task

Implement:

def route_tool(name, tools, max_dist):

tools: list of registered tool-name strings.
Return the chosen tool name, or None if none is within max_dist.

Input Format

name (str), tools (list of str), max_dist (int).

Output Format

A tool-name string or None.

Sample

print(route_tool("get_wether", ["get_weather", "send_email"], 2))

Output:

get_weather

Example:

Input:

print(route_tool("get_wether", ["get_weather", "send_email"], 2))

Output:

get_weather

Reasoning:

Sort the registered tools alphabetically to ensure deterministic tie-breaking: ["get_weather", "send_email"].
Calculate the Levenshtein edit distance between the requested name "get_wether" and the first tool "get_weather": the single substitution of e to a at index 7 yields a distance of $d_1 = 1$ .
Calculate the edit distance between "get_wether" and the second tool "send_email": due to significant character differences and length mismatch, the distance is $d_2 = 9$ .
Identify the tool with the minimum distance: since $1 < 9$ , "get_weather" is selected as the candidate with $best\_d = 1$ .
Verify the threshold condition: the minimum distance $1$ is less than or equal to max_dist ( $2$ ), so the candidate is valid.
The final output is get_weather

Constraints:

Standard Levenshtein distance (unit costs).
Smallest distance wins; ties broken alphabetically.
Return None if the best distance exceeds max_dist.

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

1. Background Knowledge

Levenshtein distance (edit distance) measures the minimum number of single-character operations—insertions, deletions, or substitutions—required to transform one string into another. Each operation has a uniform cost of 1. For example, transforming get_wether into get_weather requires one insertion (the second t), yielding a distance of 1. This metric is widely used in spell-checking, DNA sequence alignment, and, as in this problem, fuzzy matching of identifiers.

The classic dynamic programming formulation builds a 2D table $dp[i][j]$ representing the edit distance between the first $i$ characters of string $A$ and the first $j$ characters of string $B$ . The recurrence is:

dp[i][j] = \min \begin{cases} dp[i-1][j] + 1 & \text{(deletion)} \\ dp[i][j-1] + 1 & \text{(insertion)} \\ dp[i-1][j-1] + (A[i] \neq B[j]) & \text{(substitution or match)} \end{cases}

Base cases are $dp[i] = i$ and $dp[j] = j$ , reflecting that converting a string of length $i$ to the empty string requires $i$ deletions.

In the context of tool routing for AI agents, models may hallucinate slightly misspelled function names. A fuzzy-matching layer acts as a safety net: if the requested name is "close enough" (within a threshold) to a registered tool, the system routes the call to the correct tool rather than failing outright.

2. Algorithm Approach

The problem decomposes into two sub-problems:

Compute edit distance between the requested name and each candidate tool name using the DP table described above.
Select the best match by finding the tool with the minimum distance, subject to the constraint that the distance must be $\leq \text{max\_dist}$ . Ties are broken alphabetically (lexicographic order).

A straightforward approach iterates over every tool, computes its distance to the requested name, and tracks the best candidate. No advanced data structures (like BK-trees) are necessary for typical tool-list sizes.

3. Step-by-Step Strategy

Implement a helper function edit_distance(s1, s2) that returns the Levenshtein distance between two strings using the DP table.
Initialize a table of size $(\text{len}(s1)+1) \times (\text{len}(s2)+1)$ .
Fill base cases along the first row and column.
Fill the rest using the recurrence relation above.
Return the value at $dp[\text{len}(s1)][\text{len}(s2)]$ .

👑

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.

solution.py

Python 3.13

Test Results

0/0

Run code to see test results.