Find the earliest supported software version

Question

## Scenario

A compatibility service exposes an expensive predicate `is_supported(version)`. Given a set of dotted numeric versions, return the earliest supported version. Version components must be compared numerically, so `"2.10.0"` is later than `"2.9.0"`.

## Interface

```python
def parse_version(version: str) -> tuple[int, ...]: ...

def find_earliest_supported_version(
    versions: list[str],
    is_supported,
) -> str | None: ...

def find_earliest_supported_version_hierarchical(
    versions: list[str],
    is_supported,
) -> tuple[str | None, int]: ...
```

## Part 1: general support patterns

- Parse every dot-separated component as a non-negative integer.
- Input versions may be unsorted and may have different component counts.
- `find_earliest_supported_version` must return the numerically earliest version for which the predicate is true, or `None`.
- Support may regress: a later version can be unsupported after an earlier supported version. Therefore, the general implementation must not assume monotonicity.
- Call `is_supported` no more than once per distinct version.

For this exercise, compare parsed tuples using Python tuple ordering. State how you would normalize trailing zeroes if `1.2` and `1.2.0` must be treated as identical.

## Part 2: hierarchical monotonic mode

For the hierarchical function only, assume support is monotonic in numeric version order: once a supported version is reached, all later listed versions are supported.

- Minimize predicate calls by searching major, minor, and patch groups.
- Cache every predicate result.
- Return the earliest supported version and the number of distinct predicate calls.
- If no version is supported, return `(None, probe_count)`.

## Follow-ups

1. The predicate occasionally times out or returns inconsistent results. Add a retry and confidence policy without corrupting the cache.
2. Resolve a graph of package constraints rather than probing one ordered list. Discuss cycle detection, satisfiability, and install order.
3. Multiple clients ask overlapping compatibility questions. Design a shared cache with invalidation when the compatibility rules change.