Finding the next palindrome number

Question

I wrote a piece of code that generates the next palindromic number and that works fine. However I feel like my code isn't as efficient as it could be. Are there any tweaks that I could implement to make it run more efficiently?

Input format:

4 # No. of Test Cases
800
2133
103
6

Code I have currently:

def reverse(x):
 return int(str(x)[::-1])
 
def count(left, right):
 left_d = left % 10
 right_d = int(str(right)[0])
 
 if left < right:
 return 1
 elif left > right:
 return 0
 else:
 left //= 10
 right = int(str(right)[1:])
 return count(left, right)
def nextPal(x):
 length, rev = len(str(x)), reverse(x)
 if length == 1:
 return x + 1
 elif x == int("9" * length):
 return x + 2
 elif length % 2 != 0 and x == rev:
 digits = list(str(x))
 mid = len(digits) // 2
 digits[mid] = f"{int(digits[mid]) + 1}"
 return int("".join(digits))
 elif length % 2 == 0:
 x_str = str(x)
 left = int(x_str[:len(x_str) // 2])
 right = int(x_str[len(x_str) // 2:])
 
 left += count(left, right)
 
 return int(f"{left}{reverse(left)}")
 else:
 while rev != x:
 x += 1
 rev = reverse(x)
 
 return x
 
# Typically read from STDIN like 'python nextpal.py < data.txt'
cases = int(input())
for _ in range(cases):
 case = int(input())
 print(nextPal(case))

Output:

808
2222
111
7

• JosefZ: Is right that nextPal(9) returns 10?
• mhay10: It does but it should return 11.
• AJNeufeld: Another bug: nextPal(191) gives 1101. You need to work on getting the code correct before you work on efficiency.
• AJNeufeld: Yet another bug: nextPal(8008) returns 808!

Answer 1

This code has many bugs:

• nextPal(9) returns 10,
• nextPal(191) return 1101, and
• nextPal(8008) returns 808.

I will not point out how to fix these bugs. The Stack Overflow site is for help fixing code, not the Code Review site. Still, since you claimed the code "works fine", it seems you were not aware of these bugs, so the question is "on topic", and a review of the code is warranted.

Naming

PEP 8, the Style Guide for Python Code recommends function use snake_case names, not bumpyWords. As such, nextPal should be named next_pal, or even better, next_palindrome.

Unused code

This variables are assigned, but never used:

 left_d = left % 10
 right_d = int(str(right)[0])

Left Leaning Code

Both the count and nextPal functions use an if return elif return else return ladder. Since every if and elif block terminates in a return statement, there is no need for the else's; the elif could simply be if statements, and the final else: removed. This results in less indentation (in this case, only in the final else blocks), and is generally more readable.

Multiple assignment

This statement is doing two different things:

 length, rev = len(str(x)), reverse(x)

It is determining the number of digits of x, and it is reversing the digits of x. As completely different operations, combining them into a single statement is not appropriate. The reader has to mentally unpack the statement into two statements, grouping the first parts and second parts together. Moreover, the Python interpreter is doing extra work, creating the tuple and then unpacking the tuple ... extra work done for no reason. Simply use two statements:

 length = len(str(x))
 rev = reverse(x)

Efficiency & Hint

After all your special case checks, you finally fall back on a linear search for a palindrome:

 while rev != x:
 x += 1
 rev = reverse(x)

This is incredibly inefficient. For any whole number x, you can determine a palindrome near x by converting x to a string and replacing the last half of the digits with the reverse of the first half of the digits. For example, 12345 becomes 12321 and 123456 becomes 123321. In these cases, the generated value is actually the previous palindrome, not the next palindrome (left to student).