2

Any tips on optimizing this python code for finding next palindrome:

Input number can be of 1000000 digits

COMMENTS ADDED

#! /usr/bin/python
    def inc(lst,lng):#this function first extract the left half of the string then
                     #convert it to int then increment it then reconvert it to string
                     #then reverse  it and finally append it to the left half. 
                     #lst is input number and lng is its length
        if(lng%2==0):

            olst=lst[:lng/2]
            l=int(lng/2)
            olst=int(olst)
            olst+=1
            olst=str(olst)
            p=len(olst)
            if l<p:
                olst2=olst[p-2::-1]
            else:
                olst2=olst[::-1]
            lst=olst+olst2
            return lst
        else:
            olst=lst[:lng/2+1]
            l=int(lng/2+1)
            olst=int(olst)
            olst+=1
            olst=str(olst)
            p=len(olst)
            if l<p:
                olst2=olst[p-3::-1]
            else:
                olst2=olst[p-2::-1]
            lst=olst+olst2
            return lst



    t=raw_input()
    t=int(t)

    while True:
        if t>0:
            t-=1
        else:
            break

        num=raw_input()#this is input number
        lng=len(num)
        lst=num[:]

        if(lng%2==0):#this if find next palindrome to num variable
                     #without incrementing the middle digit and store it in lst.

            olst=lst[:lng/2]
            olst2=olst[::-1]
            lst=olst+olst2

        else:
            olst=lst[:lng/2+1]
            olst2=olst[len(olst)-2::-1]
            lst=olst+olst2

        if int(num)>=int(lst):#chk if lst satisfies criteria for next palindrome
            num=inc(num,lng)#otherwise call inc function
            print num
        else:
            print lst
Improve this question
8
  • 1
    An explanation of what it does and how it does this would be helpful. Commented Jan 20, 2011 at 13:31
  • 1
    This is where having some comments or descriptive variable names will help ppl decrypt whats being done. A quick look at your code seems to be painful due to the lack of comments or descriptive variables... Commented Jan 20, 2011 at 13:45
  • @g19fanatic I will comment it wright away. Commented Jan 20, 2011 at 13:57
  • There's a bug near the bottom; if you put in something like 12300, the output is 12300 because you're printing num rather than the answer you've computed and put in lst. Commented Jan 20, 2011 at 14:03
  • 1
    @Jason Orendorff Thanks I have corrected it. Commented Jan 20, 2011 at 14:10

4 Answers 4

Reset to default
2

I think most of the time in this code is spent converting strings to integers and back. The rest is slicing strings and bouncing around in the Python interpreter. What can be done about these three things? There are a few unnecessary conversions in the code, which we can remove. I see no way to avoid the string slicing. To minimize your time in the interpreter you just have to write as little code as possible :-) and it also helps to put all your code inside functions.

The code at the bottom of your program, which takes a quick guess to try and avoid calling inc(), has a bug or two. Here's how I might write that part:

def nextPal(num):
    lng = len(num)
    guess = num[:lng//2] + num[(lng-1)//2::-1]  # works whether lng is even or odd
    if guess > num:  # don't bother converting to int
        return guess
    else:
        return inc(numstr, n)

This simple change makes your code about 100x faster for numbers where inc doesn't need to be called, and about 3x faster for numbers where it does need to be called.

To do better than that, I think you need to avoid converting to int entirely. That means incrementing the left half of the number without using ordinary Python integer addition. You can use an array and carry out the addition algorithm "by hand":

import array

def nextPal(numstr):
    # If we don't need to increment, just reflect the left half and return.
    n = len(numstr)
    h = n//2
    guess = numstr[:n-h] + numstr[h-1::-1]
    if guess > numstr:
        return guess

    # Increment the left half of the number without converting to int.
    a = array.array('b', numstr)
    zero = ord('0')
    ten = ord('9') + 1
    for i in range(n - h - 1, -1, -1):
        d = a[i] + 1
        if d == ten:
            a[i] = zero
        else:
            a[i] = d
            break
    else:
        # The left half was all nines. Carry the 1.
        # Update n and h since the length changed.
        a.insert(0, ord('1'))
        n += 1
        h = n//2

    # Reflect the left half onto the right half.
    a[n-h:] = a[h-1::-1]
    return a.tostring()

This is another 9x faster or so for numbers that require incrementing.

You can make this a touch faster by using a while loop instead of for i in range(n - h - 1, -1, -1), and about twice as fast again by having the loop update both halves of the array rather than just updating the left-hand half and then reflecting it at the end.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

This is not enough. Your Implementation gives Time Limit Exceeded on spoj.pl/problems/PALIN
I think python is a wrong choice for this problem.I should implement it with c.
@gkt.pro I agree C is a more suitable language. However, according to SPOJ, a lot of people have solved it with Python. And note that my final version of this code is about 100x faster than what you started with.
Is there any big difference b/w the lists and array in python, I know only about list in python.Can you point me to some basic tutorials in array, i googled it but couldn't find a good one.
Arrays are more efficient but can only store numbers. Documentation is here: docs.python.org/library/array.html I don't know of any tutorials that cover it.
0

You don't have to find the palindrome, you can just generate it.

Split the input number, and reflect it. If the generated number is too small, then increment the left hand side and reflect it again:

def nextPal(n):
    ns = str(n)
    oddoffset = 0
    if len(ns) % 2 != 0:
        oddoffset = 1

    leftlen = len(ns) / 2 + oddoffset
    lefts = ns[0:leftlen]
    right = lefts[::-1][oddoffset:]
    p = int(lefts + right)
    if p < n:
        ## Need to increment middle digit
        left = int(lefts)
        left += 1
        lefts = str(left)
        right = lefts[::-1][oddoffset:]
        p = int(lefts + right)

    return p

def test(n):
    print n
    p = nextPal(n)
    assert p >= n
    print p

test(1234567890)
test(123456789)
test(999999)
test(999998)
test(888889)
test(8999999)
Improve this answer

6 Comments

@Douglas Leeder Can you please explain me how your code will be more efficient them mine.
To me this looks like a tighter implementation of gkt.pro's algorithm (and without the bug).
Actually this does have a bug or two though. if p < n should be if p <= n, and after that change nextPal(99) returns 1001 rather than 101.
@Jason I guess you're right - but mine's shorter and, I think, easier to understand.
@Jason I guess that come down to a definition on 'next'.
|
0

EDIT

NVM, just look at this page: http://thetaoishere.blogspot.com/2009/04/finding-next-palindrome-given-number.html

Improve this answer

4 Comments

Yes I have done that only but still it is taking lots of time.
For finding ONE next palindrome? EDIT - Ohhh, not necessarily from a palindrome to another one...
@gkt.pro: I misunderstood your problem, see my new algorithm.
I am doing what you said but just look at my code(added comment) and see if my implementation is efficient.
0

Using strings. n >= 0


from math import floor, ceil, log10



def next_pal(n):
    # returns next palindrome, param is an int
    n10 = str(n)
    m = len(n10) / 2.0
    s, e = int(floor(m - 0.5)), int(ceil(m + 0.5))
    start, middle, end = n10[:s], n10[s:e], n10[e:]
    assert (start, middle[0]) == (end[-1::-1], middle[-1]) #check that n is actually a palindrome
    r = int(start + middle[0]) + 1 #where the actual increment occurs (i.e. add 1)
    r10 = str(r)
    i = 3 - len(middle)
    if len(r10) > len(start) + 1:
        i += 1
    return int(r10 + r10[-i::-1])

Using log, more optized. n > 9


def next_pal2(n):
    k = log10(n + 1)
    l = ceil(k)
    s, e = int(floor(l/2.0 - 0.5)), int(ceil(l/2.0 + 0.5))
    mmod, emod = 10**(e - s), int(10**(l - e))
    start, end = divmod(n, emod)
    start, middle = divmod(start, mmod)
    r1 = 10*start + middle%10 + 1
    i = middle > 9 and 1 or 2
    j = s - i + 2
    if k == l:
        i += 1
    r2 = int(str(r1)[-i::-1])
    return r1*10**j + r2

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.