Next palindrome number

You are given a positive integer $N. Write a script to find out the next palindromic number higher than $N.

Examples

Example 1
Input: $N = 1234
Output: 1331

Example 2
Input: $N = 999
Output: 1001

Analysis

This is - or isn't - easy.

It's easy if you do this:

$test = $N + 1;
$test ++ while $test ne reverse($test);

I think it's clear that that will produce the correct answer, but if $N is large it could take a long time.

So I looked for a more analytic, and faster, method, and I think I found one, but it's quite complicated.

Briefly - and see the code for more details - first establish whether $N has an even or odd number of digits. Divide it into 3 strings: $left, $middle and $right where $left and $right are the same length and $middle is the middle digit of an odd-length number or '' (a zero-length string) for an even-length one.

The first attempt is then

$left . $middle . reverse($left)

which will work roughly half the time - that is, when reverse($left) > $right. For example, it works for 123000 -> 123321 or 1234000 -> 1234321 but not for 123444 -> 123321.

Where it doesn't work for even-length $N, reverse($left) < $right and the answer is ($left + 1) . reverse($left + 1).

In the odd-length cases we need to:

• concatenate $left and $middle
• increment that
• split the result into a new $left and (one-digit) $middle
• and the answer is $left . $middle . reverse($left).

But even that doesn't work if $N is all 9s - such as 99, 999, 9999 etc. For those numbers the answer is

'1' . '0' x (length($N) - 1) . '1'

And lastly, for the single digit values of $N the answer is simply $N + 1, except for 9 where the answer is 11.

Finally, just to be sure my algorithm works, I have added the easy way (see above) as well, and checked that the two agree. For the thousands of random numbers I have checked, they do.

I am sorry that the 'Try it' feature is currently working very slowly or not at all owing to some issue with my web hosting provider.

Try it 

Try running the script with any input:

Your $N =

example: 123456

⤡

#!/usr/bin/perl

# Blog: http://ccgi.campbellsmiths.force9.co.uk/challenge

use v5.26;    # The Weekly Challenge - 2021-05-24
use utf8;     # Week 114 - task 1 - Next palindrome number
use warnings; # Peter Campbell Smith
binmode STDOUT, ':utf8';
use Encode;

next_palindrome_number(12345);
next_palindrome_number(12320);
next_palindrome_number(12321);
next_palindrome_number(123456);
next_palindrome_number(123999);
next_palindrome_number(1234320);
next_palindrome_number(9999);
next_palindrome_number(99999);

sub next_palindrome_number {
    
    my ($number, $length, $left, $middle, $right, $try, $verify, $left_middle);
    
    # initialise
    $number = $_[0];
    $length = length($number);
    
    # single digit
    if ($length == 1) {
        $try = $number == 9 ? 11 : $number + 1;
    } else {
    
        # divide up odd-length number
        if ($length & 1) {
            $left = substr($number, 0, int($length / 2));
            $middle = substr($number, ($length - 1) / 2, 1);
            $right = substr($number, ($length + 1) / 2, 99);
        
        # or even-length number
        } else {
            $left = substr($number, 0, $length / 2);
            $middle = '';
            $right = substr($number, ($length / 2), 99);
        }
        
        # try this
        $try = $left . $middle . reverse($left);

        # no good so increment left and try again
        if ($try <= $number) {
            unless (($left . $middle) =~ m|^9*$|) {
                
                # odd length
                if ($middle ne '') {
                    $left_middle = ($left . $middle) + 1;
                    ($left, $middle) = $left_middle =~ m|(.*)(.)|;
                    $try = $left . $middle . reverse($left);
                    
                # even length
                } else {
                    $try = ($left + 1) . reverse($left + 1);
                }
                
            # special case - all 9s
            } else {
                $try = '1' . '0' x ($length - 1) . '1';
            }
        }
    }
    
    # verify by incrementing
    $verify = $number + 1;
    $verify ++ while $verify ne reverse($verify);
    
    say qq[\nInput:  $number];
    say qq[Output: $try] . ($try == $verify ? '' : qq[ should be $verify]);
}

30 lines of code
Completed after the closing date and not submitted to GitHub

Output from script

Input:  12345
Output: 12421

Input:  12320
Output: 12321

Input:  12321
Output: 12421

Input:  123456
Output: 124421

Input:  123999
Output: 124421

Input:  1234320
Output: 1234321

Input:  9999
Output: 10001

Input:  99999
Output: 100001