Programming Praxis – The Next Palindrome

Today’s Programming Praxis problem is about palindromic numbers, i.e. numbers that read the same backwards and forwards, such as 1001 or 35753. As mentioned in the comments, the provided solution is not particularly elegant. Let’s see if we can do better.

First our import:

import Data.List.Split

This is all we need to get the next palindrome. The reason I’m returning a String instead of an Integer is because converting a one million-digit string is not a very fast process. The read function from the prelude takes forever, and a custom function took about 4 seconds. Since nextPalindrome (10^1000000) takes about 2 seconds, that would triple the execution time.

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

Does it work? Let’s test. I’m only checking the first 10^5 instead of 10^6 numbers here so codepad doesn’t time out, but naturally it works correctly for all numbers.

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]

Seven times shorter than the provided solution and about half the length of the other Haskell solution. Good enough for me.

About these ads

Tags: , , ,

3 Responses to “Programming Praxis – The Next Palindrome”

  1. Remco Niemeijer Says:

    Updated nextPalindrome to be one line shorter and 50% faster.

  2. programmingpraxis Says:

    Remco, please try nextPalindrome 9919.

  3. Remco Niemeijer Says:

    Right you are. I’ve posted a new version that handles this correctly.

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 35 other followers

%d bloggers like this: