Reverse and Add: find a palindrome

Question

This is one of codeeval challenges

Challenge Description:

Credits: Programming Challenges by Steven S. Skiena and Miguel A. Revilla

The problem is as follows: choose a number, reverse its digits and add it to the original. If the sum is not a palindrome (which means, it is not the same number from left to right and right to left), repeat this procedure. E.g.

195 (initial number) + 591 (reverse of initial number) = 786

786 + 687 = 1473

1473 + 3741 = 5214

5214 + 4125 = 9339 (palindrome) In this particular case the palindrome 9339 appeared after the 4th addition. This method leads to palindromes in a few step for almost all of the integers. But there are interesting exceptions. 196 is the first number for which no palindrome has been found. It is not proven though, that there is no such a palindrome.

Here is my solution for it:

#!/usr/bin/env python
import sys

"""
I've done some tests with timeit and it seems that both numeric and string version
have the same performance (at least for numbers < 10000)

# def reverse_num(num):
#   rev = 0
#   while(num > 0):
#     rev = (10*rev)+num%10
#     num //= 10
#   return rev
"""

def reverse(num):
    """Reverses the number

       >>> reverse(1456)
       6541
       >>> reverse(111)
       111
    """
    return int(str(num)[::-1])

def palindrome(num):
    """Return the number of iterations required to compute a palindrome

       >>> palindrome(195)
       (4, 9339)
    """
    # compute in 100 iterations or less
    for i in range(100):
        rnum = reverse(num)
        if rnum == num:
            break
        num = num + rnum
    return (i, num)

if __name__ == "__main__":
    with open(sys.argv[1]) as f:
        for line in f:
            print "%s %s" % palindrome(int(line))

Any remarks on the code style, on the algorithm itself?

Answer 1

Only 2 things:

1. Why do you have this? This makes your code a bit unclear and confusing. Remove this if you do not want to use it as it might make your actual code look messy.

   # def reverse_num(num):
   #   rev = 0
   #   while(num > 0):
   #     rev = (10*rev)+num%10
   #     num //= 10
   #   return rev
   

2. It is discouraged to use for i in range(100): in Python.

Answer 2

Comments from an answer to another question apply here to the commented function reverse_num:

divmod

In Python, when you are performing arithmetic and are interested in both the quotient and the remainder of a division, you can use divmod.

Magic numbers

You have 10 hardcoded in multiple places. My preference is to use a default argument giving the base to use.

def reverse(integer, base=10):
    result = 0
    while integer:
        integer, r = divmod(integer, base)
        result = base * result + r
    return result

---

More specific comments

• The documentation for palindrome is somewhat imprecise. It implies that it returns a number but it actually returns a tuple.

• num = num + rnum can be re-written num += rnum

• it may be interesting to memoize any result you compute so that you do not it to spend time to compute it later on. This needs some benchmarking to be sure this is relevant.