Finding the next palindrome given a number

I recently was looking for websites similar to Project Euler, and came across SPOJ - the Sphere Online Judge. It gives us some problems, then asks us to submit a solution, which it will evaluate and tell if we are worth our salt as programmers ;)
More details here.

There, I came across this problem which looked quite interesting. Basically, the challenge is, given a number n, we've got to find the palindromic number which comes after this.
Some definitions:
Palindromic number: A number that reads the same either way, like 12421, 57375, 8448, 146641, etc.
"comes after this": the palindrome number must be greater than the given number - given 12321, we must find the next palindrome and not return 12321 itself as the answer.

Ok, with those made clear, let's dive into the problem.

On first sight, it seems simple enough: iterate from n+1 checking if each number is a palindrome. Stop when you find a palindrome.
Unfortunately, that strategy is too slow for our purposes - SPOJ clearly states the inputs can be very huge, in which case this brute force would probably not be able to complete it within the given 9 seconds.

Anyway, we are programmers, and must seek more efficient ways when they exist. Here, it does seem there must be a way to find the next palindrome given a number. What would it be?

My first thought was, simply mirror the number around its centre. Then, we'd surely end up with a palindromic number.
What I mean is, given a number 16310, mirror the first half values across the central '3' to give 16361. If the number has an even number of digits, just mirror it about the centre of the number, like 3628 to 3663.

That strategy works as long as the resulting 'mirror-imaged' value is greater than the original number. What if it results in a number less than (or equal to) the original? Say, for 41258, it would give 41214, which is less than the original number. Or 12321, which would give 12321 itself, which is equal to the original number.

So my next strategy was, if simple mirror-imaging fails, increment the middle digit and then do a mirror image. So, 41258 would become 41314. 12321 would be 12421.

But again, there's a problem with this approach. What if the number had even number of digits? There is no middle digit to increment. Let's say the number was 4265. It's simple to see that, instead of the middle digit, if we increment the digit to the left of the middle (2 here), and do the mirror image, we'll have the palindrome we want: 4334 in this case.

So far, so good.

Now, onto a big issue: 9. Yes, the digit nine. We saw that when the simple mirroring fails, we increment the middle (or left to middle) digit. Now, what do we get when we increment 9? 10. Oops! We can't put a 10 where 9 was. Want proof? Try 41968. Simple mirroring would give 41914, no luck there. Incrementing the 9 to 10 would give 411014, not a palindrome even. And also, it's surely false that there's no palindrome between 41,968 and 411,014 (that's between forty one thousand and four hundred and eleven thousand).

So, what do we do? Luckily, something we learnt in elementary school - carrying over - seems to help here too. Wherever the 10 occurred, keep the 0 there itself, carry over the 1 to the previous digit. So here, 41968 would become 42068 which on applying mirroring would give 42024.

Here too, there's a caveat: consider the extreme cases: 99999 would give (with repeated carryover) 1000001, and 9999 would give 100001. In both cases there's an extra 0 hanging in there. So far I've not been able to generalize it, and have been keeping the case of all digits being 9 a special case only. In this special case, I do the usual procedure, then remove one of the 0's from the resulting number. Ugly, but works. :)

EDIT: Turns out if I finish the increment and carrying over parts fully, then mirror image the number according to how many digits it now has, the 9999 cases take care of themselves with the original algo itself - no 'special cases' needed. :)

So, I believe this is the complete algorithm to find the next palindrome given a number. I have not thought through the steps very carefully, so if you see any flaws, kindly point them out...

I'm trying to code this thing in the Lisp programming language, so I'm taking baby steps towards the solution. As of now, I'm yet to implement the carrying over for 9 part alone. And I don't have any idea how complex that is going to be.

Update: I finished coding this in Lisp, but lost the code somewhere. I coded it again in Python now, which is available here. I've put in a lot of comments so as to make it somewhat easily understandable. Hope this helps the doubting Thomases believe. :)

By the way, my GATE solutions blog now has full feed access, which means you can read it fully without leaving the comfort of your RSS reader.

Happy coding :)