Time limit on PALIN with Haskell

[fonsvdlaan]

Hi,

I posted this already in "Problems archive" but realised this would maybe be a more appropiate place.
I've written a solution to the problem PALIN and I think it's correct.
But when I submit it, it gives a time limit. Can anyone tell me what's wrong?

Cheers,
fonsvdlaan

module Main where
import Data.List
main :: IO ()
main = do
          numberofcasesstring     <- getLine
          let numberofcases       = read numberofcasesstring
          listofcasesstring       <- getContents
          let listofcases         = map read (words listofcasesstring)
          let listofanswers       = getPalindromes numberofcases listofcases
          let listofanswersstring = intercalate "\n" (map show listofanswers)
          putStr listofanswersstring
getPalindromes :: Int -> [Int] -> [Int]
getPalindromes 0 _      = []
getPalindromes n (x:xs) = (palindrome x) : (getPalindromes (n-1) xs)
palindrome :: Int -> Int
palindrome x | isPalindrome x = x
             | otherwise = palindrome (x+1)
isPalindrome :: Int -> Bool
isPalindrome x = (show x) == reverse (show x)

[leppyr64]

Your algorithm is far too slow. The input can have up to 1000000 digits. The distance between two palindromes can be enormous so stepping one by one will take forever. You need to think a little more about your algorithm.

[fonsvdlaan]

Hi,

I changed my algorithm drastically, so now it calculates the difference between the integer and the next palindrome and adds this to the integer.
It's much quicker, but I still get a time limit.
Does anyone know why my code is still too slow?

Cheers,
fonsvdlaan

module Main where
import Data.List
import Data.Char
main :: IO ()
main = do
          numberofcasesstring     <- getLine
          let numberofcases       = read numberofcasesstring
          listofcasesstring       <- getContents
          let listofcases         = words listofcasesstring
          let listofanswers       = getPalindromes numberofcases listofcases
          let listofanswersstring = intercalate "\n" listofanswers
          putStr listofanswersstring
getPalindromes :: Int -> [String] -> [String]
getPalindromes 0 _      = []
getPalindromes n (x:xs) = (palindrome x) : (getPalindromes (n-1) xs)
palindrome :: String -> String
palindrome string | even $ length string = palindromeEven string
                  | otherwise            = palindromeOdd string
palindromeEven :: String -> String
palindromeEven string = let lengte = length string
                            left = take (lengte `div` 2) string
                            right = drop (lengte `div` 2) string
                        in  if last left < head right
                            then makePalindrome (show (read left + 1)) "" right -- increase center digit (last of left part) by one
                            else makePalindrome left "" right
palindromeOdd :: String -> String
palindromeOdd string = let lengte = length string
                           left = take (lengte `div` 2) string
                           center = take 1 (drop (lengte `div` 2) string)
                           right = drop (lengte`div`2 + 1) string
                       in if last left < head right
                          then makePalindrome left (show (read center + 1)) right --increase center digit by one
                          else makePalindrome left center right
makePalindrome :: String -> String -> String -> String
makePalindrome l c r = show ((read (l ++ c ++ r)) + (sum (differences (reverse l) r)))
  where differences [] []         = []
        differences (x:xs) (y:ys) = (ord x - ord y)*10^(length ys):(differences xs ys)

[leppyr64]

Again, I don't really use Haskell, but I would supsect that this segment is dominating the time of execution:

makePalindrome :: String -> String -> String -> String
makePalindrome l c r = show ((read (l ++ c ++ r)) + (sum (differences (reverse l) r)))
  where differences [] []         = []
        differences (x:xs) (y:ys) = (ord x - ord y)*10^(length ys):(differences xs ys)

With the number having up to 1000000 digits this should be pretty slow.

The correct algorithm here will have O(number of digits) complexity. Your algorithm is that but along with the complexity of doing bignum mathematics which would not scale well.