Project Euler: крупнейший палиндромный продукт с двумя 3-значными числами

Question

Я получаю 580085, почему это неправильно? И есть ли другой способ проверить, является ли число палиндромом?

def reverse(str, aux=''):
    count = len(str)
    while count > 0:
        aux += str[count-1]
        count -= 1
    return aux

def palindrome(num):
    j = str(num)
    if j == reverse(j):
        return 1
    else:
        return 0

i = 999
found = 0
while i > 99 and not found:
    j = 999
    while j > 99 and not found:
        if palindrome(i * j):
            found = 1
            print(i * j)
        else:
            j -= 1
    if not found:
        i -= 1

Мой пост в основном кодовый, но мне больше нечего сказать.

Answer 1

Заняло некоторое время и изучил проблему. Я попытался использовать обратный подход (начиная с чисел палиндрома и найти их делители (если есть)). Использование Py354 на Win10.

code.py:

import time
from math import sqrt


def reverse(str, aux=''):
    count = len(str)
    while count > 0:
        aux += str[count-1]
        count -= 1
    return aux


def palindrome(num):
    j = str(num)
    if j == reverse(j):
        return 1
    else:
        return 0


def question_makhfi_0():
    ret = 0
    i = 999
    found = 0
    while i > 99 and not found:
        j = 999
        while j > 99 and not found:
            if palindrome(i * j):
                found = 1
                ret = i * j
            else:
                j -= 1
        if not found:
            i -= 1
    return ret, i, j


def answer_makhfi_0():
    i = 999
    _max = 0
    while i > 99:
        j = 999
        while j > 99:
            num = i * j
            if palindrome(num):
                if num > _max:
                    _max = num
                    factor0, factor1 = i, j
            j -= 1
        i -= 1
    return _max, factor0, factor1


"""
def answer_makhfi__0_improved_0():
    i = j = 999
    prod = i * j
    step = 0
    while prod > 100000:
        if step % 2:
            i -= 1
        else:
            j -= 1
        prod = i * j
        prod_str = str(prod)
        if prod_str == prod_str[::-1]:
            return prod
        step += 1
"""


def answer_cfati_0():
    pal = 999999
    while pal >= 900009:
        if pal % 10 == 9:
            pal_str = str(pal)
            if pal_str == pal_str[::-1]:
                pal_sqrt = sqrt(pal)
                for factor0 in range(101, int(pal_sqrt) + 1):
                    if pal % factor0 == 0:
                        factor1 = int(pal / factor0)
                        if 100 <= factor1 <= 999:
                            return pal, factor0, factor1
        pal -= 10
    #return pal


def time_func(f, *args):
    t0 = time.time()
    res = f(*args)
    t1 = time.time()
    return t1 - t0, res


if __name__ == "__main__":
    for func in [question_makhfi_0, answer_makhfi_0, answer_cfati_0]:
        print("\nStarting: {}".format(func.__name__))
        #print(func.__name__)
        res = time_func(func)
        print("  Time: {:.6f}\n  Result: {}".format(*res))

Примечания:

• Превратил ваш код в функции (делая все необходимые корректировки и опуская все, что связано с производительностью)
• Добавлена ​​дополнительная функция, которая измеряет время выполнения
• answer_makhfi_0:
  • заменены max от _max чтобы избежать дублирования встроенных имен
  • добавил return заявление в конце (в любом случае, крайне неэффективно)
• answer_cfati_0:
  • Код предполагает наличие номера палиндрома в [900009, 999999] диапазон, который может быть выражен как произведение из 2 (3 цифр) чисел. Справедливо предположить, что это (тесты подтверждают это). Однако, если вы стремитесь к пуленепробиваемому коду, эта форма не сделает этого, мне придется немного его скорректировать (это будет с точки зрения производительности)
  • Он использует все виды математических / логических "горячих клавиш", чтобы избежать ненужных вычислений (я думаю, что код может быть улучшен в этом направлении).

Выход:

"e\Work\Dev\Stackru\q47999634>"e:\Work\Dev\VEnvs\py35x64_test\Scripts\python.exe" code.py

Starting: question_makhfi_0
  Time: 0.008551
  Result: (580085, 995, 583)

Starting: answer_makhfi_0
  Time: 1.457818
  Result: (906609, 993, 913)

Starting: answer_cfati_0
  Time: 0.012599
  Result: (906609, 913, 993)

Согласно выводу, различия между исходным и новым кодом (для одного прогона, как раз меняется):

• Самый большой номер палиндрома: 906609 - 906609
• Время для расчета: 1.457818 - 0.012599

@ EDIT0:

• Благодаря вашему комментарию я обнаружил (критическую) логическую ошибку (и несколько мелких) в моем коде: она возвращала 998899 (781 * 1279). После их исправления производительность снизилась на порядок, но все равно быстро
• Модифицированные функции, которые также возвращают факторы (для проверки)

Answer 2

Новый код:

def reverse(str, aux=''):
    count = len(str)
    while count > 0:
        aux += str[count-1]
        count -= 1
    return aux

def palindrome(num):
    j = str(num)
    if j == reverse(j):
        return 1
    else:
        return 0

i = 999
max = 0
while i > 99:
    j = 999
    while j > 99:
        num = i * j
        if palindrome(num):
            if num > max:
                max = num
                print(max)
        j -= 1
    i -= 1