Building numeric palindromes in Python

6/18/2006

I popped over to TopCoder and glanced at the sample algorithm problems. While I think TopCoder is a great site, it is unfortunate that contests limit contestants to use either Java, C++, or .NET.

I decided to attempt the first problem (building palindromes) using Python. I know there has to be a more efficient way of doing this!

def build_palindrome(seed):
    if is_palindrome(seed):
        return seed
    else:
        new_seed = seed + reverse_number(seed)
        if new_seed > 1000000000:
            return -1
        else:
            return build_palindrome(new_seed)

def is_palindrome(int_to_check):
    temp_list = convert_to_list(int_to_check)
    temp_length = len(temp_list)
    for i in range(temp_length):
        if temp_list[i] != temp_list[temp_length - i - 1]:
            return False
    return True

def reverse_number(x):
    temp_list = convert_to_list(x)
    temp_list.reverse()
    return int(reduce(lambda x, y: str(x) + str(y), temp_list))

def convert_to_list(x):
    temp_string = repr(x)
    temp_list = []
    for i in range(len(temp_string)):
        temp_list.append(temp_string[i])
    return temp_list

if __name__ == '__main__':
    print build_palindrome(51) ## put your number to test here, 51 -> 66

I wish the Python standard library shipped a function to "explode" a number to a list (using the list data structure felt comfortable to me). But hey - at least I managed to make a "questionable" reduce() call somewhere in there ;-). How would you go about building palindromes in Python, or your language of choice?

Update 1: A reader going by the name Janez sent me an e-mail of a tiny yet effective solution:

def palindrome(n):
    while str(n) != str(n)[::-1]:
        n += int(str(n)[::-1])
        if n >= 10 ** 9: return -1
    return n

In a benchmark (testing up to 100001), Janez's code beat mine by nearly 9 seconds (clocking in at 2.89 seconds). His technique: slicing. Note to self, start taking advantage of Pythonic shortcuts.