"""One solution. Try the exercise first."""


def edit_counts(ref: list[str], hyp: list[str]) -> tuple[int, int, int]:
    n, m = len(ref), len(hyp)
    cost = [[0] * (m + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        cost[i][0] = i
    for j in range(1, m + 1):
        cost[0][j] = j
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            same = ref[i - 1] == hyp[j - 1]
            cost[i][j] = min(
                cost[i - 1][j - 1] + (0 if same else 1),  # match or substitute
                cost[i - 1][j] + 1,                       # delete a reference word
                cost[i][j - 1] + 1,                       # insert a hypothesis word
            )

    # Walk back. On ties prefer match/substitute, then delete, then insert.
    sub = dele = ins = 0
    i, j = n, m
    while i > 0 or j > 0:
        if i > 0 and j > 0:
            same = ref[i - 1] == hyp[j - 1]
            if cost[i][j] == cost[i - 1][j - 1] + (0 if same else 1):
                sub += 0 if same else 1
                i, j = i - 1, j - 1
                continue
        if i > 0 and cost[i][j] == cost[i - 1][j] + 1:
            dele += 1
            i -= 1
        else:
            ins += 1
            j -= 1
    return sub, dele, ins


def wer(ref: str, hyp: str) -> float:
    r, h = ref.split(), hyp.split()
    sub, dele, ins = edit_counts(r, h)
    if not r:
        return 0.0 if not h else float("inf")
    return (sub + dele + ins) / len(r)


def corpus_wer(pairs: list[tuple[str, str]]) -> float:
    errors = words = 0
    for ref, hyp in pairs:
        r = ref.split()
        errors += sum(edit_counts(r, hyp.split()))
        words += len(r)
    return errors / words if words else 0.0