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: kata, palindorme, praxis, programming