109. 飞镖(Darts)

"""Project Euler 109 - Darts."""

from __future__ import annotations

from itertools import combinations_with_replacement
from time import perf_counter

TARGET_LIMIT = 100
SAMPLE_SCORE = 6
SAMPLE_WAYS = 11


def build_all_scoring_darts() -> list[tuple[str, int]]:
    """Return all non-miss dart results with labels and scores."""
    darts: list[tuple[str, int]] = []
    darts.extend((f"S{n}", n) for n in range(1, 21))
    darts.append(("S25", 25))
    darts.extend((f"D{n}", 2 * n) for n in range(1, 21))
    darts.append(("D25", 50))
    darts.extend((f"T{n}", 3 * n) for n in range(1, 21))
    return darts


def build_finishing_doubles() -> list[tuple[str, int]]:
    """Return all valid finishing doubles with labels and scores."""
    doubles: list[tuple[str, int]] = [(f"D{n}", 2 * n) for n in range(1, 21)]
    doubles.append(("D25", 50))
    return doubles


def count_checkout_ways_by_score(max_score: int) -> list[int]:
    """Count distinct checkout ways for every score up to `max_score`."""
    all_darts = build_all_scoring_darts()
    finishing_doubles = build_finishing_doubles()
    ways = [0] * (max_score + 1)

    for _, finish_score in finishing_doubles:
        if finish_score <= max_score:
            ways[finish_score] += 1

        for _, first_score in all_darts:
            total = first_score + finish_score
            if total <= max_score:
                ways[total] += 1

        for (_, first_score), (_, second_score) in combinations_with_replacement(all_darts, 2):
            total = first_score + second_score + finish_score
            if total <= max_score:
                ways[total] += 1

    return ways


def count_checkout_below(limit: int) -> int:
    """Return the number of distinct checkout ways for scores below `limit`."""
    if limit <= 0:
        return 0
    ways = count_checkout_ways_by_score(limit - 1)
    return sum(ways)


def run_solve_once(limit: int = TARGET_LIMIT) -> tuple[int, float]:
    """Compute the answer and elapsed seconds for one run."""
    start = perf_counter()
    answer = count_checkout_below(limit)
    elapsed = perf_counter() - start
    return answer, elapsed


def main() -> None:
    """Run validations and print the Project Euler 109 answer."""
    ways = count_checkout_ways_by_score(SAMPLE_SCORE)
    assert ways[SAMPLE_SCORE] == SAMPLE_WAYS, (
        f"Sample mismatch: got {ways[SAMPLE_SCORE]}, expected {SAMPLE_WAYS}"
    )

    answer, elapsed = run_solve_once(TARGET_LIMIT)
    print(f"checkouts_below_{TARGET_LIMIT} = {answer}")
    print(f"solve_elapsed_seconds = {elapsed:.6f}")


if __name__ == "__main__":
    main()