[Haskell-beginners] Re: Help with slow algorithm

[Heinrich Apfelmus]

Diego Echeverri wrote:
> 
> I've been playing with https://www.spoj.pl/ to get better with Haskell.
> I'm trying to do: https://www.spoj.pl/problems/PALIN/
> 
> Basically given a number k, you have to find a number bigger than k
> that is palindrome. The thing is that k can be 1000000 digits long.
> 
> I have learnt a bunch of things doing this exercise but I'm still
> getting time-limit exception.
> 
> Here's the code: http://gist.github.com/401880
> 
> I believe that the bottleneck is in the addOne function (Specially in
> the case where you have a bunch of nines). I have rewritten it to use
> STArray but isn't fast enough.
> doing: addOne $ B.replicate 500000 'a' takes too much time!

Are you sure that you are using a fast algorithm? For instance, starting
with k and counting up until you reach a palindrome is definitely not a
good idea; you need to do something cleverer.


Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com