"""数字黑洞 6174 —— Kaprekar 常数探索器。

任取一个四位数（各位不全相同），把各位数字从大到小和从小到大
各排成一个数，相减，重复这个过程，最多 7 步就会掉进 6174，
然后永远停在 6174。试试看吧。
"""


def kaprekar_step(n: int) -> int:
    digits = sorted(f"{n:04d}")
    asc = int("".join(digits))
    desc = int("".join(reversed(digits)))
    return desc - asc


def kaprekar_route(n: int) -> list[int]:
    route = [n]
    seen = {n}
    while True:
        nxt = kaprekar_step(route[-1])
        if nxt in seen:  # 防全同数字的 0000 陷阱
            break
        route.append(nxt)
        seen.add(nxt)
        if nxt == 6174:
            break
    return route


def longest() -> tuple[int, int]:
    """统计 1000~9999 中需要最多步数才落入 6174 的数。"""
    best_n, best_len = 0, 0
    for n in range(1000, 10000):
        if len(set(f"{n:04d}")) == 1:
            continue  # 1111 这类数没有黑洞可掉
        length = len(kaprekar_route(n)) - 1
        if length > best_len:
            best_n, best_len = n, length
    return best_n, best_len


if __name__ == "__main__":
    print("例：3524 的坠落路线")
    print("  ", " -> ".join(str(x) for x in kaprekar_route(3524)))
    best_n, best_len = longest()
    print(f"1000~9999 中坠入 6174 最慢的是 {best_n}，需要 {best_len} 步")
    print("数学上最多只需 7 步，你随便挑个数验证看看。")