Ytdyklly

I recently did a programming challenge: given a positive number find the next palindromic number. In PHP, I decided to do something like this:

<?php



function palindromic($input) {

  while (1) {

    $number = (string) ++$input;



    if ($number == strrev($number)) {

      return $number;

    }

  }

}

I was then asked to provide test inputs for the function and to explain why, so I had (where x is a random number)

• x < 10: test single digits


• 10 < x < 100: tests numbers with even length


• 100 < x < 1000: tests numbers with odd lengths


• 1,000,000 < x: tests a largish number

Note: we can always assume a positive number, so checking for non-positive numbers or inputs that are a different type, or asserting exceptions thrown back, etc aren't relevant to the challenge.

Apparently there were some other important numbers to test, can anyone explain what I've missed here?

I don't code in java or python so I don't fully follow the methods provided in the commented link under the question.

I've decided to write a method that avoids the incremental checking for palindromic integers. Instead, it uses arithmetic based on a few preliminary string function results to discover the closest greater palindromic integer. Note, there are limitations to my method because the input and output are integers rather than strings. I can conclude after testing that my method will stay true into the 10's of trillions.

Code: (Demo)

function nextPalindromicInteger($integer) {

    if ($integer < 9) {

        $next = $integer + 1;

        return "$integer => $next (+1) " . ($next != strrev($next) ? "FAIL" : "PASS") . "n";

    }

    $size = strlen($integer);

    $psize = ceil($size / 2);  // find length of rhs & lhs including pivot when length is odd

    $npsize = $size - $psize;  // find length of rhs & lhs excluding pivot when length is odd

    $rnplhs = (int)strrev(substr($integer, 0, $npsize));  // reverse nplhs

    $nprhs = (int)substr($integer, -$npsize);  // store right hand side integer excluding pivot  //KEEP

    $trimmed=strlen(rtrim(substr($integer, 0, $psize), '9')); // store length of rtrim'd plhs

    if ($rnplhs > $nprhs) {

        $bump = 0;

    } elseif (!strlen(trim($integer, '9'))) {

        $bump = 2;

        $nprhs = 0;

        $rnplhs = 0;

    } else {

        if ($psize != $npsize) {  // odd integer length

            if ($trimmed == 1) {

                $exponent = 1;  // dictates $bump=11

            } else {

                $exponent = $npsize;

            }

        } else {  // even integer length

            $exponent = $trimmed;

        }

        $bump = pow(10, $exponent);

        if ($psize == $npsize || $trimmed < $psize) {

            $bump += pow(10, $exponent - 1);

        }

    }

    $next = $integer + $rnplhs - $nprhs + $bump;

    return "$integer => $next (+" . ($next - $integer) . ") " . ($next != strrev($next) ? "FAIL" : "PASS") . "n";

}

for ($x = 0; $x < 14; ++$x) {

    $integer = rand(pow(10, $x), pow(10, $x + 1) - 1);

    echo nextPalindromicInteger($integer);   

}

If I spent some more time refining, I could probably write my function more eloquently, but for the purposes of this question it is sufficient to reveal (to me at least) some of the fringe cases.

I found in my development and testing that it was important to test against:

• a range of integers, some with even length and some with odd length.


• integers with a pivot (shared middle digit) of nine.


• integers with an odd length and a non-9 pivot.


• integers consisting entirely of 9's.


• integers where the reversed left-hand-side component minus the right-hand-side component is: >0, =0, and <0
  

Once I isolated the patterns that exist with certain sequences, I could declare the correct "bump" or adjustment. Some bumps are static, others depend on the length or value of the left-hand-side component.

As for your relevant numbers to check using your method, I can't think of any that would cause trouble because you are looping and checking each iteration. Perhaps the challenge was assuming that you would try to write a method without loops as I did or run "inside out" string comparison checks on each side's digits.

As for checking "large-ish" numbers, I found that once I had perfected the bumps from 1 to 9999, all integers above that were accounted for.

Possible Output:

9 => 11 (+2) PASS

75 => 77 (+2) PASS

776 => 777 (+1) PASS

4891 => 4994 (+103) PASS

92764 => 92829 (+65) PASS

999539 => 999999 (+460) PASS

7059657 => 7060607 (+950) PASS

48756572 => 48766784 (+10212) PASS

633149324 => 633151336 (+2012) PASS

2096785014 => 2096886902 (+101888) PASS

80448359477 => 80448384408 (+24931) PASS

237762850363 => 237763367732 (+517369) PASS

7730351516591 => 7730351530377 (+13786) PASS

79541453924626 => 79541455414597 (+1489971) PASS