Sunday, April 17, 2011

Kata: Palindrome generation in Python

I took this Kata from topcoder.com. My initial solution:

def isPalindrome(n):
       return n == reverseNumber(n)
      
def generatePalindrome(n):
       while not isPalindrome(n):
               n = n + reverseNumber(n)
       return n

def reverseNumber(n):
       res = 0
       while n > 0:
               res =  (res*10) + (n%10)
               n = n/10
       return res
      
n = 265
print reverseNumber(n)
print n
print isPalindrome(24543)
print generatePalindrome(24543)

Another faster isPalindrome implementation. It is still linear but much faster since it does not require reversing the string. It also uses less memory, since only N/2 characters need to be copied into a new structure (Stack like):


def isPalindrome(word):
    size = len(word)
    if size == 0:
        return False
    
    stack = list(word[0:size/2])
    start = size/2 + size%2
    
    for c in word[start:]:
        if c != stack.pop():
            return False
    return True
        
def tests():
    assert isPalindrome("a")
    assert not isPalindrome("ab")
    assert isPalindrome("aba")
    assert isPalindrome("abba")
    
tests()