The Next Palindrome

May 22, 2009

This exercise is much harder than it sounds, due to all the special cases that appear. Here’s one solution; it’s ugly, but it works:

(define (palin n)
  (let* ((ds (string->list n)) (len (length ds)) (len2 (quotient len 2)))
    (cond ((equal? ds (list #\9)) "11")
          ((= len 1) (list->string (plus1 ds)))
          ((all-nines? ds)
            (let loop ((ds ds) (ps (list #\1)))
              (if (null? ds)
                  (list->string (cons #\1 (cdr ps)))
                  (loop (cdr ds) (cons #\0 ps)))))
          ((even? len)
            (let* ((left (take len2 ds)) (right (drop len2 ds)))
              (if (lt? right (reverse left))
                  (list->string (append left (reverse left)))
                  (let ((x (plus1 left)))
                    (list->string (append x (reverse x)))))))
          (else (let* ((left (take len2 ds))
                       (middle (car (drop len2 ds)))
                       (right (cdr (drop len2 ds))))
                  (if (lt? right (reverse left))
                      (list->string (append left (list middle) (reverse left)))
                      (if (char=? middle #\9)
                          (let ((x (plus1 left)))
                            (list->string (append x (list #\0) (reverse x))))
                          (list->string (append left (plus1 (list middle)) (reverse left))))))))))

All the one-digit numbers are special cases, so the main body of the code doesn’t have to deal with null left-half and right-half digit lists. Another special case is numbers that consist of only nines, since the result is longer than the input. What’s left are two cases, even-length numbers and odd-length numbers.

Even-length numbers are easier. First, we split them into two halves, left and right. The easy case occurs when the left half is less than the right half when the digits of the left half are reversed; the result is just the left half and its reverse, appended together. Otherwise, the left half must be incremented by one before it is appended to the front of its reverse.

Odd-length numbers are similar, but add the additional wrinkle of a middle digit. In the particular case where the right half is less than the reverse left half and the middle digit is nine, the middle digit becomes zero, and the left half is incremented by one before it is appended to the middle digit and its reverse. The other cases are similar to the even-length numbers.

We treat the numbers as strings because of the requirement to handle very long numbers, as long as a million digits. That means we need some functions from grade-school aritemetic:

(define (all-nines? ds)
  (cond ((null? ds) #t)
        ((not (char=? (car ds) #\9)) #f)
        (else (all-nines? (cdr ds)))))

(define (lt? a b)
  (cond ((< (length a) (length b)) #t)
        ((< (length b) (length a)) #f)
        (else (let loop ((a a) (b b))
                (cond ((null? a) #f)
                      ((char<? (car a) (car b)) #t)
                      ((char<? (car b) (car a)) #f)
                      (else (loop (cdr a) (cdr b))))))))

(define (plus1 ds)
  (let loop ((ds (reverse ds)) (carry 0) (xs '()))
    (cond ((null? ds)
            (if (zero? carry)
                (reverse xs)
                (cons #\1 (reverse xs))))
          ((char=? (car ds) #\9)
            (loop (cdr ds) 1 (cons #\0 xs)))
          (else (append (reverse (cdr ds))
                        (list (integer->char
                                (+ (char->integer (car ds)) 1)))
                        (reverse xs))))))

Here you can see palin in action:

> (map palin '("0" "88" "808" "1999" "2133" "9999" "99999"))
("1" "99" "818" "2002" "2222" "10001" "100001")

Because I had seen so many incorrect solutions, I wanted to be sure my solution was correct. I calculated all the palindromes to one million, by brute force, and compared the result to a loop that calls palin to calculate the next palindrome iteratively:

(equal?
  (list-of (list->string x)
    (n range 1 10000002)
    (x is (string->list (number->string n)))
    (equal? x (reverse x)))
  (let loop ((p "0") (ps '()))
    (if (< 7 (string-length p)) (reverse ps)
      (let ((x (palin p)))
        (loop x (cons x ps))))))

Palin uses take and drop from the Standard Prelude, and the test program uses list comprehensions.

You can run the code at http://programmingpraxis.codepad.org/oHbzw5WF. For more about the math of palindromic numbers, see sequence A002113 in Neil J. A. Sloane’s Online Encyclopedia of Integer Sequences.

About these ads

Pages: 1 2

18 Responses to “The Next Palindrome”

  1. Jaime Vargas said

    ;; It doesn’t need to be that complicated.
    ;; Below is a simpler solution

    (define (next-palindrome n)
    (define (next-palindrome* n)
    (define digits-of-n (string->list (format “~a” n)))
    (cond
    [(equal? digits-of-n (reverse digits-of-n)) n]
    [else (next-palindrome* (add1 n))]))
    (next-palindrome* (add1 n)))

    (map next-palindrome ‘(0 88 808 1999 2133 9999 99999)) ==> ‘(1 99 818 2002 2222 10001 100001)

  2. lilac said

    Here’s how I did it:

    bisect xs = go xs xs where
    go xs [] = ([],[],xs)
    go (x:xs) (_:[]) = ([],[x],xs)
    go (x:xs) (_:_:ys) = let (fs,m,ss) = go xs ys in (x:fs,m,ss)

    increment = foldr go ([],True) where
    go ‘9’ (xs,True) = (‘0′:xs,True)
    go x (xs,True) = (succ x:xs,False)
    go x (xs,False) = (x:xs,False)

    nextPalindrome xs | fhr > secondHalf = firstHalf ++ middle ++ fhr
    | otherwise = startInc ++ endInc where
    (firstHalf, middle, secondHalf) = bisect xs
    fhr = reverse firstHalf
    (incremented, carry) = increment (firstHalf ++ middle)
    incremented’ | carry = ‘1’:incremented
    | otherwise = incremented
    startInc | carry = init incremented’
    | otherwise = incremented’
    endInc | null middle = reverse incremented’
    | otherwise = tail (reverse incremented’)

    It’s a bit fiddly, but there’s only really two cases: first half reversed > second half: take the palindrome starting with the first half. first half reversed <= second half: take the palindrome starting with the first half plus one (being careful to drop a digit if we increase the length in so doing).

  3. Jaime Vargas said

    ;; Hopefully. Better formated

    (define (next-palindrome n)
      (define (next-palindrome* n)
        (define digits-of-n (string->list (format "~a" n)))
        (cond
          [(equal? digits-of-n (reverse digits-of-n)) n]
          [else (next-palindrome* (add1 n))]))
      (next-palindrome* (add1 n)))
    
  4. lilac said

    @Jaime Vargas: note the problem requires this to work on inputs 1000000 digits. Try your program on (10^500000 – 1) * (10^500000).

  5. lilac said

    Once more with formatting?

    bisect xs = go xs xs where
      go xs [] = ([],[],xs)
      go (x:xs) (_:[]) = ([],[x],xs)
      go (x:xs) (_:_:ys) = let (fs,m,ss) = go xs ys in (x:fs,m,ss)
    
    increment = foldr go ([],True) where
      go '9' (xs,True) = ('0':xs,True)
      go x   (xs,True) = (succ x:xs,False)
      go x   (xs,False) = (x:xs,False)
    
    nextPalindrome xs | fhr > secondHalf = firstHalf ++ middle ++ fhr
                      | otherwise        = startInc ++ endInc where
      (firstHalf, middle, secondHalf) = bisect xs
      fhr = reverse firstHalf
      (incremented, carry) = increment (firstHalf ++ middle)
      incremented' | carry = '1':incremented
                   | otherwise = incremented
      startInc | carry     = init incremented'
               | otherwise = incremented'
      endInc | null middle = reverse incremented'
             | otherwise   = tail (reverse incremented')
  6. [...] Praxis – The Next Palindrome By Remco Niemeijer Today’s Programming Praxis problem is about palindromic numbers, i.e. numbers that read the same backwards [...]

  7. Remco Niemeijer said

    My Haskell solution (see http://bonsaicode.wordpress.com/2009/05/22/programming-praxis-%E2%80%93-the-next-palindrome/ for a version with comments):

    nextPalindrome :: Integer -> String
    nextPalindrome n =
        half ++ drop (mod (length . show $ n + 1) 2) (reverse half)
        where l = length . show $ n
              half = take (div l 2 + 1) . show $ div n (10 ^ div l 2) + 1
    
    main :: IO ()
    main = do
        print $ map nextPalindrome [0, 88, 808, 1999, 2133, 9999, 99999]
        print $ (takeWhile (<= 10^5) $ iterate (read . nextPalindrome) 0)
                == filter (\x -> show x == reverse (show x)) [0..10^5]
    
  8. Jaime Vargas said

    Lilac, my solution still applies eventhough it is inneficient.

  9. Remco Niemeijer said

    Updated version that’s one line shorter and 50% faster:

    nextPalindrome :: Integer -> String
    nextPalindrome n = half ++ drop (mod l 2) (reverse half)
        where l    = length . show $ n + 1
              half = take (div l 2 + 1) . show $ div n (10 ^ div l 2) + 1
    
  10. programmingpraxis said

    Remco, please try nextPalindrome 9919.

  11. Jaime Vargas said

    ;; Take 2: Efficient version

    (define (n->list n)
      (map (λ (x) (- (char->integer x) 48)) (string->list (format "~a" n))))
    
    (define (list->n l)
      (foldl (λ (x a) (+ (* 10 a) x)) 0 l))
    
    (define (scale-of n)
      (string-length (format "~a" n)))
    
    (define (make-palindromes n)
      (define digits (n->list n))
      (list (list->n (append digits (reverse digits)))
            (list->n (append digits (rest (reverse digits))))))
    
    (define (palindrome? n)
      (let ([digits (n->list n)])
        (equal? digits (reverse digits))))
    
    (define (next-palindrome n)
      (define-values (q r) (quotient/remainder n (expt 10 (quotient (scale-of n) 2)))) 
      (define candidates (cons (add1 n)
                               (append (make-palindromes q)
                                       (make-palindromes (add1 q))
                                       (make-palindromes (quotient (add1 q) 10)))))
      (apply min (filter (λ (x) (and (> x n) (palindrome? x))) candidates)))
    
  12. Remco Niemeijer said

    New version that works correctly for 9919:

    import Data.List.Split
    
    nextPalindrome :: Integer -> String
    nextPalindrome n = palindrome r where
        l = length . show $ n + 1
        [s, m] = splitPlaces [div (l - 1) 2, 2 - mod l 2] $ show n
        palindrome x = x ++ drop (mod l 2) (reverse x)
        r = if head m > last m then s ++ [head m]
            else take (div (l + 1) 2) . show $ div n (10 ^ div l 2) + 1
    
    main :: IO ()
    main = do
        print $ map nextPalindrome [0, 88, 808, 1999, 2133, 9999, 99999]
        print $ (takeWhile (<= 10^6) $ iterate (read . nextPalindrome) 0)
                == filter (\x -> show x == reverse (show x)) [0..10^6]
    
  13. programmingpraxis said

    Remco,

    I’m curious. In the first version, how did 9919, or any of the smaller numbers where the second half is less than the first half, pass your test? The test looks to me like it should have worked.

  14. FalconNL said

    They didn’t, because there was no such test. In the 0, 88…99999 list you used the second half is always greater than or equal to the first half.
    The other test just recursively calls nextPalindrome, so the input number is always symmetrical, in which case my original algorithm works ok.
    Since there was no test for that type of case I never noticed that bug.

  15. lilac said

    @Jaime Vargas: If thermodynamics means it’s impossible for your program to be executed on certain valid inputs (because any computing device would break down due to entropy first), then I would say the solution does not apply. 10^499978 years is plenty of time for that (and that’s assuming an insanely fast computer is used).

  16. Chethan T said

    Hey I am Happy To see this Post
    “Next Palindrome Number”! which was posted on my blog!
    And Thanks For Solving This!
    Very Nice Collection!

  17. RandomC# said

    This is a solution in c#

    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;
    using System.Threading.Tasks;

    namespace LeapYear_Trial
    {
    class Program
    {
    public bool Palindrome(string number)
    {
    return number.SequenceEqual(number.Reverse());

    }
    static void Main(string[] args)
    {
    Program obj = new Program();

    Console.WriteLine(“Input a number “);
    int num = Convert.ToInt32(Console.ReadLine());

    int nextNum = num + 1;
    while(!obj.Palindrome(nextNum.ToString()))
    {
    nextNum += 1;
    }

    Console.WriteLine(“The next smallest palindrome larger than {0} is {1}”, num, nextNum);
    }
    }
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 630 other followers

%d bloggers like this: