Finding the next palindrome code

Question

I have been trying recently to develop a code finding the next palindrome from a certain number. For example, if the input is 800, the output should be 808, as 808 being the next palindrome from 800.

Here's my code. It's fully functional, but on my online judge I get a problem with the time of the execution. My method is not optimal. Any advice on this?

def reverseNumber(a):
 degreMax = findDegree(a)
 result = 0
 while a != 0:
 r = a % 10
 a = a // 10
 result = result + r*10**degreMax
 degreMax = degreMax - 1
 return result
def findDegree(a):
 degre = 0
 while a >= 10:
 a = a/10
 degre = degre + 1
 return degre
def isPalindrome(a):
 test = False
 if reverseNumber(a) == a:
 test = True
 return test
def nextPalindrome(a):
 while isPalindrome(a) == False:
 a = a + 1
 return a
nbTest = int(raw_input())
inputs = []
for i in range(0,nbTest):
 a = int(raw_input())
 inputs.append(a)
for i in range(0,len(inputs)):
 print nextPalindrome(inputs[i])

Answer 1

A bit of style

Before anything, let's rewrite/reorganise the code a bit to make it more pythonic but also easier to test.

Python has a style guide called PEP8. Among other things, you do not follow the naming and spacing conventions. You might find interesting to know that there are various tools to check your code (against PEP8 but also for various other things : pep8, pylint, pychecker, pyflakes and even tools to fix style automatically like autopep8.

Also, it is usual (and very useful) to use an if __name__ == '__main__': guard so that you have your definitions (classes, functions, constants, etc) on one hand and your actual program doing something on the other hand.

So far, your "improved" code looks like :

def reverse_number(a):
 degreMax = find_degree(a)
 result = 0
 while a != 0:
 r = a % 10
 a = a // 10
 result = result + r*10**degreMax
 degreMax = degreMax - 1
 return result
def find_degree(a):
 degre = 0
 while a >= 10:
 a = a/10
 degre = degre + 1
 return degre
def is_palindrome(a):
 test = False
 if reverse_number(a) == a:
 test = True
 return test
def next_palindrome(a):
 while not is_palindrome(a):
 a = a + 1
 return a
if __name__ == '__main__':
 nb_test = int(raw_input())
 inputs = []
 for i in range(0, nb_test):
 a = int(raw_input())
 inputs.append(a)
 # inputs = [5, 10, 303, 800]
 for i in range(0, len(inputs)):
 print next_palindrome(inputs[i])

So far, I haven't done anything relevant as far as performances are concerned and you might think I'm wasting your time here. I'm almost done.

More style

So far, I've done cosmetic changes. A few other changes can be performed to make your code more beautiful but also potentially faster (even if it is very subtle).

• Python has a divmod function which does exactly what you are trying to do in reverse_number.

• You don't need a temporary variable in is_palindrome.

• You don't need to provide first argument to range if you start at 0 and step is 1.

• You don't need temporary variable a in your main.

• In Python 2 (which is the version I am guessing you are using), range creates a list which might be more than what you want. If you just need something to iterate on, xrange is what you need (in most cases this is what you need and it's why it is the behavior for range in Python 3).

• It is the convention to name _ a variable whose variable is not used such as i in your code initialising the input list.

• Whenever you are using range and len to iterate over a container, you are most probably doing something wrong. Python provides you a way to iterate over something that can hardly be easier :

  for i in inputs:
   print next_palindrome(i)
  

It's easy/concise/hard to get wrong/fast.

• to create a list and fill it, instead of having a boring loop and append, Python has a very expressive way to do it : list comprehension. If you have never read about them, make yourself a favor and just google it. In your case, defining your inputs gets down to this :

   inputs = [int(raw_input()) for _ in xrange(nb_test)]
  

• you can use division assignment /= to write a /= 10 instead of a = a/10. Also (and this is more common), you can use += and -= in various places of your code.

• you don't even need to store inputs into an array, you can just compute and print answers as you do over inputs.

At this stage, your code looks like :

def reverse_number(a):
 degreMax = find_degree(a)
 result = 0
 while a != 0:
 a, r = divmod(a, 10)
 result = result + r*10**degreMax
 degreMax -= 1
 return result
def find_degree(a):
 degre = 0
 while a >= 10:
 a /= 10
 degre += 1
 return degre
def is_palindrome(a):
 return reverse_number(a) == a
def next_palindrome(a):
 while not is_palindrome(a):
 a += 1
 return a
if __name__ == '__main__':
 nb_test = int(raw_input())
 inputs = [int(raw_input()) for _ in xrange(nb_test)]
 # inputs = [5, 10, 303, 800]
 for i in inputs:
 print next_palindrome(i)

User interface

A last note before diving into performances. It might be convenient to tell the user what you are asking him. Otherwise, one might think your program is just computing stuff when it is just waiting for input.

nb_test = int(raw_input("Nb tests? "))
inputs = [int(raw_input("Test ? ")) for _ in xrange(nb_test)]

Mesuring performances

In order to improve performance, it is best to be able to measure it while ensuring correctness. This can be achieved through unit tests. Without being bothered with a full unit testing framework, you can just write things like :

def unit_tests():
 assert next_palindrome(5) == 5
 assert next_palindrome(10) == 11
 assert next_palindrome(80) == 88
 assert next_palindrome(12345678) == 12355321
 assert next_palindrome(1234567890) == 1234664321
 assert next_palindrome(12345678901) == 12345754321
 # assert next_palindrome(123456789012) == ?? too slow..

As your code probably gets too slow for bigger inputs, it's a good option to add a few tests with huge inputs.

Improving performance

Finally!!

You'll probably be disappointed to see that most of the logic you've written can be rewritten using standard functions (this has been said by others):

def is_palindrome(a):
 s = str(a)
 return s == ''.join(reversed(s))

But for a more dramatic improvement, we'll have to look for a totally different algorithm, one that will be very efficient for very huge values. This can be done if you spot a pattern in the different solutions for the different tests we have written.

Let's consider a number with n digits : $$d1,d2,...,dn$$ and let's try to split it in the middle :

• if n is odd, we have $$n = 2*k+1$$ and we have 3 parts : $$d1,d2,..,dk$$ in the piece of the left, $$dk+1$$ in the middle, $$dk+2..dn$$ in the piece on the right. Based on the comparison of the left part and of the right part, the next palindrom the left part and its reversed with either dk or dk+1 in the middle.

• if n is even, the same logic applies without a middle component.

A few edge cases are to be considered but the following code works on basic cases :

def next_palindrome(a):
 s = str(a)
 n = len(s)
 k, r = divmod(n, 2)
 if r:
 left, mid, right = s[:k], s[k], s[k+1:]
 assert len(left) == len(right) == k
 assert s == left + mid + right
 print(s, left, mid, right)
 mid_n = int(mid)
 if left:
 left_n, right_n, right_n_rev = int(left), int(right), int(right[::-1])
 if left_n > right_n and left_n > right_n_rev:
 return int(left + mid + left[::-1])
 else:
 return int(left + str(mid_n+1) + left[::-1])
 else:
 return mid_n # 1-digit number
 else:
 left, right = s[:k], s[k:]
 assert len(left) == len(right) == k
 assert s == left + right
 print(s, left, right)
 left_n, right_n, right_n_rev = int(left), int(right), int(right[::-1])
 if left_n > right_n and left_n > right_n_rev:
 return int(left + left[::-1])
 else:
 new_left = str(left_n + 1)
 return int(new_left + new_left[::-1])

I've tried (unsucessfully) to give meaningful names to variables.

• Caridorc: You repeated something that I had already said, but you also made some great points, especially the tests, writing tests allows to write code faster (and not slower, as some people, including me a little time ago, thought), I would have up-voted even just for that alone. +1
• Chirac: +1 Thank you very much for this, especially the advice about coding accordingly to Python conventions. Gold.
• Chirac: This algorithm has some incredible performance. Gonna study it in depth, seems very well optimized
• SylvainD: I can already tell you what could be wrong : when incrementing a number leads to a longer number.

Answer 2

• reverseNumber does too much unnecessary work:

  def reverseNumber(a):
   result = 0
   while a != 0:
   result = result * 10 + a % 10
   a //= 10
   return result
  

  avoids expensive ** operation, and eliminates the need of findDegree altogether.

• Stylistically isPalindrome is noisy.

  def isPalindrome(a):
   return reverseNumber(a) == a
  

  does exactly the same.

• Algorithm is not the best. You are spending too much time in conversion to integer and arithmetic. I recommend to keep the number in form of string, and implement an increment (basically an elementary school addition).

Answer 3

This is way too verbose:

def isPalindrome(a):
 test = False
 if reverseNumber(a) == a:
 test = True
 return test

Instead, use:

def isPalindrome(a):
 return reverseNumber(a) == a

User interface

nbTest = int(raw_input())

The user will just see the programme hanging and will not understand why it is not responding. It would be better to add a prompt.

Optimize while drastically reducing code-size:

def isPalindrome(a):
 return str(a) == ''.join(reversed(str(a)))

Benchmark to prove that my version is faster:

import time
def reverseNumber(a):
 degreMax = findDegree(a)
 result = 0
 while a != 0:
 r = a % 10
 a = a // 10
 result = result + r*10**degreMax
 degreMax = degreMax - 1
 return result
def findDegree(a):
 degre = 0
 while a >= 10:
 a = a/10
 degre = degre + 1
 return degre
def isPalindrome(a):
 return reverseNumber(a) == a
def strPalindrome(a):
 return str(a) == ''.join(reversed(str(a)))
start = time.time()
result = map(isPalindrome,range(1,100000))
print("Numerical took: ",time.time() - start)
start = time.time()
result2 = map(strPalindrome,range(1,100000))
print("String took: ",time.time() - start)
if result != result2:
 raise ValueError("Function is broken.")

---

Another easy optimization that leads to better code is having a main function, because Python code runs faster in functions.

def main():
 nbTest = int(raw_input())
 inputs = []
 for i in range(0,nbTest):
 a = int(raw_input())
 inputs.append(a)
 for i in range(0,len(inputs)):
 print nextPalindrome(inputs[i])

---

You may want a if __name__ == "__main__" guard, so that you can import your module from other scripts.

Use Python 3

You should use Python 3 because Python 2.7 will stop receiving updates soon. range is also unnecessarily slow in Python 2.

Using the powerful syntax of Python

In Python you should never use the following:

for i in range(0,len(inputs)):
 print nextPalindrome(inputs[i])

Instead use the cleaner and more 'Pythonic':

for i in inputs:
 print nextPalindrome(i)