Нужно ускорить поиск палиндрома

Question

Программа проверяет, является ли число палиндромом, и если нет, то подбирает ближайший палиндром, больший начального числа. Чувствую себя идиотом, что делаю это перебором, но иначе мне было не придумать.

num = str(input())
end=False
while end is False:
    if num == num[::-1]:
      print(f'{num}')
      end = True
    else:
      num = str(int(num)+1)
      print(num)
      end = False

Answer 1

Давайте попробуем так:

Выделяем первую половину и вторую половину, перевёртываем вторую.

Если первая половина больше, то делаем вторую равной перевёрнутой первой .

Иначе увеличиваем первую половину (вместе со средней цифрой для нечётной длины) на единицу, делаем вторую равной перевёрнутой первой (без средней цифры)

Answer 2

number = input()

if number == number[::-1]:
    print(number)
else:
    delta = 1 if len(number) % 2 else 0
    central_number = number[len(number)//2] if delta else ''
    first_part = number[:len(number)//2]
    second_part = first_part[::-1]
    number = first_part + central_number + second_part
    print(number)

нет смысла оборачивать input в str, так как input и без того возвращает str-object, а вот мое решение без всякого перебора

Answer 3

Мой ответ не далеко ушел от ответа MBo.

Делим строку на три части: лево, середина, право. Середина может быть пустой. Первый кандидат строится как конкатенация "лево", "середина", задом_наперед("лево"). Если он больше чем исходное число либо равен ему, задача решена.

Если нет, то добавляем единицу к конкатенации ("лево", "середина") и из неё строим новый палиндром.

s = input()                              # '12345'
n = int(s)                               # 12345

half = len(s) // 2                       # 2
left = s[:half]                          # '12'
mid = s[half:len(s) - half]              # '3'

m = int(left + mid + left[::-1])         # int('12' + '3' + '21')
if m < n:                                
    left_mid = str(int(left + mid) + 1)  # str(int('12' + '3') + 1)
    left = left_mid[:half]               # '12'
    m = int(left_mid + left[::-1])       # int('124' + '21')

print(m)

$ echo 1 | python next_palindrome.py 
1

$ echo 1234 | python next_palindrome.py 
1331

$ echo 4321 | python next_palindrome.py 
4334

$ echo 12345 | python next_palindrome.py 
12421

$ echo 54321 | python next_palindrome.py 
54345

$ echo 12943 | python next_palindrome.py 
13031

Answer 4

по рецепту MBo:

n = input('> ')
l = len(n)//2
a, b, c = n[:l], n[l:-l], n[-l:]

if a and int(a[::-1]) < int(c):  
    a = str(int(a)+(b=='9')) if b else str(int(a)+1)
    b = str((int(b)+1)%10) if b else ''
c = a[::-1] if a else c
    
p = a + b + c
print(f'{p = }')

UPD

Спасибо @StanislavVolodarskiy за замеченную ошибку в коде из-за которой неправильно обрабатывались числа с 9 в середине и однозначные числа. Теперь все вроде работает как надо, но код стал довольно корявым))

БЛОГ НА HUSL

Нужно ускорить поиск палиндрома

Ответы (4 шт):