"""
If we take 47, reverse and add, 47 + 74 = 121, which is palindromic.

Not all numbers produce palindromes so quickly. For example,
    349 + 943 = 1292
    1292 + 2921 = 4213
    4213 + 3124 = 7337
That is, 349 took three iterations to arrive at a palindrome.

Although no one has proved it yet, it is thought that some numbers, like 196,
never produce a palindrome. A number that never forms a palindrome through the
reverse and add process is called a Lychrel number. Due to the theoretical nature
of these numbers, and for the purpose of this problem, we shall assume that
a number is Lychrel until proven otherwise. In addition you are given that for
every number below ten-thousand, it will either (i) become a palindrome
in less than fifty iterations, or, (ii) no one, with all the computing power that exists,
has managed so far to map it to a palindrome. In fact, 10677 is the first number to
be shown to require over fifty iterations before producing a palindrome:
    4668731596684224866951378664 (53 iterations, 28-digits).

Surprisingly, there are palindromic numbers that are themselves Lychrel numbers;
the first example is 4994.

How many Lychrel numbers are there below ten-thousand?

NOTE: Wording was modified slightly on 24 April 2007 to emphasise the theoretical nature of Lychrel numbers.
"""

import time
from functools import wraps
from typing import Any, Callable, TypeVar

from bitarray import bitarray

F = TypeVar("F", bound=Callable[..., Any])


def benchmark(repeat: int = 1) -> Callable[[F], F]:
    """
    重复运行目标函数并计算平均耗时。

    平均耗时会被存储在 wrapper.avg_time 和 wrapper.total_time 中，
    同时会打印到控制台。函数的返回值不受影响。
    """
    if repeat < 1:
        raise ValueError("repeat 必须 >= 1")

    def decorator(func: F) -> F:
        @wraps(func)
        def wrapper(*args: Any, **kwargs: Any) -> Any:
            total = 0.0
            result = None

            for _ in range(repeat):
                start = time.perf_counter()
                result = func(*args, **kwargs)
                end = time.perf_counter()
                total += end - start

            wrapper.avg_time = total / repeat  # type: ignore[attr-defined]
            wrapper.total_time = total  # type: ignore[attr-defined]

            print(
                f"[Benchmark] {func.__name__} | 重复 {repeat} 次 | "
                f"平均: {wrapper.avg_time:.6f}s | 总计: {wrapper.total_time:.6f}s"  # type: ignore[attr-defined]
            )
            return result

        # 初始化属性，避免调用前访问报错
        wrapper.avg_time = 0.0  # type: ignore[attr-defined]
        wrapper.total_time = 0.0  # type: ignore[attr-defined]
        return wrapper  # type: ignore[return-value]

    return decorator


def reverse_int(n: int) -> int:
    return int(str(n)[::-1])


@benchmark(repeat=15)
def count_lychrel_numbers(limit: int = 10000, max_iter: int = 50) -> int:
    is_not_lychrel = bitarray(limit + 1)
    is_not_lychrel.setall(0)
    is_not_lychrel[0] = 1

    for i in range(1, limit + 1):
        if is_not_lychrel[i]:
            continue

        n = i
        chain = [n]

        for _ in range(max_iter):
            n += reverse_int(n)

            # 检查是否形成回文
            if n == reverse_int(n):
                for num in chain:
                    if num > limit:
                        break
                    is_not_lychrel[num] = 1
                break

            chain.append(n)

    return is_not_lychrel.count(0)


if __name__ == "__main__":
    result = count_lychrel_numbers(10000)
    print(f"Number of Lychrel numbers below 10,000: {result}")