"""
The decimal number, 585 = 1001001001_2 (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)
"""

import time


def timer(func):
    def wrapper(*args, **kwargs):
        start_time = time.time()
        result = func(*args, **kwargs)
        end_time = time.time()
        print(f"{func.__name__} took time: {end_time - start_time:.6f} seconds")
        return result

    return wrapper


def is_palindromic(num: int) -> bool:
    return str(num) == str(num)[::-1]


@timer
def main_simple(limit: int = 1000000) -> None:
    res = []
    for num in range(0, limit + 1):
        if is_palindromic(num):
            if is_palindromic(int(bin(num)[2:])):
                res.append(num)
    print(sum(res))


def palindromes_of_length(length: int) -> list[int]:
    """生成所有指定位数的回文数"""
    if length == 1:
        return list(range(10))

    result = []
    # 前半部分的起始和结束
    start = 10 ** ((length - 1) // 2)
    end = 10 ** ((length + 1) // 2)

    for half in range(start, end):
        s = str(half)
        if length % 2 == 0:
            # 偶数位：123 → 123321
            palindrome = s + s[::-1]
        else:
            # 奇数位：123 → 12321
            palindrome = s + s[-2::-1]
        result.append(int(palindrome))

    return result


@timer
def main_quick(limit: int = 1000000) -> None:
    res = []
    length = len(str(limit - 1))
    for num in range(1, length + 1):
        for palindrome in palindromes_of_length(num):
            if is_palindromic(int(bin(palindrome)[2:])):
                res.append(palindrome)
    print(sum(res))


if __name__ == "__main__":
    limit = 1000000
    main_simple(limit)
    main_quick(limit)