project euler problem 145 https projecteuler netproblem145 vineet rao maxim smolskiy problem statement some positive integers n have the property that the sum n reversen consists entirely of odd decimal digits for instance 36 63 99 and 409 904 1313 we will call such numbers reversible so 36 63 409 and 904 are reversible leading zeroes are not allowed in either n or reversen there are 120 reversible numbers below onethousand how many reversible numbers are there below onebillion 109 count the number of reversible numbers of given length iterate over possible digits considering parity of current sum remainder slowreversiblenumbers1 0 0 1 0 slowreversiblenumbers2 0 0 2 2 20 slowreversiblenumbers3 0 0 3 3 100 to evaluate the solution use solution slowsolution3 120 slowsolution6 18720 slowsolution7 68720 count the number of reversible numbers of given length iterate over possible digits considering parity of current sum remainder reversiblenumbers1 0 0 1 0 reversiblenumbers2 0 0 2 2 20 reversiblenumbers3 0 0 3 3 100 there exist no reversible 1 5 9 13 ie 4k1 digit numbers to evaluate the solution use solution solution3 120 solution6 18720 solution7 68720 benchmarks running performance benchmarks slowsolution 292 9300301000003 solution 54 90970860000016 for i in range1 15 printfi reversiblenumbersi 0 0i i count the number of reversible numbers of given length iterate over possible digits considering parity of current sum remainder slow_reversible_numbers 1 0 0 1 0 slow_reversible_numbers 2 0 0 2 2 20 slow_reversible_numbers 3 0 0 3 3 100 to evaluate the solution use solution slow_solution 3 120 slow_solution 6 18720 slow_solution 7 68720 count the number of reversible numbers of given length iterate over possible digits considering parity of current sum remainder reversible_numbers 1 0 0 1 0 reversible_numbers 2 0 0 2 2 20 reversible_numbers 3 0 0 3 3 100 there exist no reversible 1 5 9 13 ie 4k 1 digit numbers to evaluate the solution use solution solution 3 120 solution 6 18720 solution 7 68720 benchmarks running performance benchmarks slow_solution 292 9300301000003 solution 54 90970860000016 for i in range 1 15 print f i reversible_numbers i 0 0 i i
EVEN_DIGITS = [0, 2, 4, 6, 8]
ODD_DIGITS = [1, 3, 5, 7, 9]


def slow_reversible_numbers(
    remaining_length: int, remainder: int, digits: list[int], length: int
) -> int:
    
    if remaining_length == 0:
        if digits[0] == 0 or digits[-1] == 0:
            return 0

        for i in range(length // 2 - 1, -1, -1):
            remainder += digits[i] + digits[length - i - 1]

            if remainder % 2 == 0:
                return 0

            remainder //= 10

        return 1

    if remaining_length == 1:
        if remainder % 2 == 0:
            return 0

        result = 0
        for digit in range(10):
            digits[length // 2] = digit
            result += slow_reversible_numbers(
                0, (remainder + 2 * digit) // 10, digits, length
            )
        return result

    result = 0
    for digit1 in range(10):
        digits[(length + remaining_length) // 2 - 1] = digit1

        if (remainder + digit1) % 2 == 0:
            other_parity_digits = ODD_DIGITS
        else:
            other_parity_digits = EVEN_DIGITS

        for digit2 in other_parity_digits:
            digits[(length - remaining_length) // 2] = digit2
            result += slow_reversible_numbers(
                remaining_length - 2,
                (remainder + digit1 + digit2) // 10,
                digits,
                length,
            )
    return result


def slow_solution(max_power: int = 9) -> int:
    
    result = 0
    for length in range(1, max_power + 1):
        result += slow_reversible_numbers(length, 0, [0] * length, length)
    return result


def reversible_numbers(
    remaining_length: int, remainder: int, digits: list[int], length: int
) -> int:
    
    
    if (length - 1) % 4 == 0:
        return 0

    return slow_reversible_numbers(length, 0, [0] * length, length)


def solution(max_power: int = 9) -> int:
    
    result = 0
    for length in range(1, max_power + 1):
        result += reversible_numbers(length, 0, [0] * length, length)
    return result


def benchmark() -> None:
    
    
    
    

    from timeit import timeit

    print("Running performance benchmarks...")

    print(f"slow_solution : {timeit('slow_solution()', globals=globals(), number=10)}")
    print(f"solution      : {timeit('solution()', globals=globals(), number=10)}")


if __name__ == "__main__":
    print(f"Solution : {solution()}")
    benchmark()