cache: memoised edit distance behind a validated wrapper

Memoise a recursive edit distance, then put a real signature back on it.

def edit_distance(a: object, b: object) -> int: ...
def solve(pairs: list[list[object]]) -> list[object]: ...

solve receives a list of [a, b] pairs of arbitrary JSON values. For each, append the Levenshtein distance if both are strings, or the string "TypeError" if edit_distance rejects them. Pairs that do not have exactly two elements are also "TypeError".

Levenshtein distance is the minimum number of single-character insertions, deletions and substitutions to turn a into b. "kitten" to "sitting" is 3.

The recursion must be memoised. The naive recursion is exponential; one of the hidden cases uses two 40-plus character strings and will not finish without a cache.

The signature erasure is the lesson. Under mypy --strict, a function decorated with @cache accepts anything:

@cache
def fib(n: int) -> int: ...

fib("nope")     # passes --strict
fib(1, 2, 3)    # passes --strict
fib()           # passes --strict

Only the return type survives, because typeshed types the wrapper’s call as __call__(*args: Hashable, **kwargs: Hashable) -> _T. It is a typeshed limitation, not a mypy bug, so pyright is affected identically and no configuration fixes it. Decorating a widely-called helper with @cache therefore removes every one of its call sites from static checking, with no diff at any call site and no warning.

So: keep the cached function private, and export a public wrapper that validates. The wrapper is what makes a list argument raise a TypeError naming your function, instead of TypeError: unhashable type: 'list' thrown from inside functools.

Two other properties of @cache worth remembering while you write this: it is unbounded by design (fine for a closed domain, a leak for anything keyed on user input — use lru_cache(maxsize=N) there), and a cached mutable return is shared between every caller.