Re: [Haskell-cafe] Looking for suggestions to improve my algorithm

I played around with this for a while based on the same sort of algorithm and ended up with a similar solution too. It turns out the operations saved by keeping track of already visited nodes are more than outweighed by the cost of doing so. (As you can see, I still have the hook in my code where amCn returns the visited list that I'm just disregarding. Ii had initially kept a giant array of all values to calculate, but the cost of that was unmanageable. After that, my big roadblock was that I couldn't come up with a good sumDivisors function to save my life. I tried a number of "optimized" methods that combined trial division with reduction based on prime factorizations, but i had to either reduce the lists by checking divisibility again somewhere along the way, or calling nub, and strictness and memoization still didn't let me produce a factorization in reasonable time. In the end, I ended up lifting yours. The only problem is that I've been staring at it for a bit and am not really sure how it works. I'd love an explanation. In any case, the code of my solution follows: amCn maxval n = amCn' (propDSum n) [] where amCn' cur visitedlist = if cur > maxval || cur < n then (0,visitedlist) else if elem cur visitedlist then (0,visitedlist) else if (cur == n) then ((length visitedlist) + 1,visitedlist) else (amCn' $! (propDSum cur)) $! (cur:visitedlist) longestAmTo maxval = longestAm' 2 (0,0) where longestAm' n bestFit@(chainLen,minVal) = if n > maxval then bestFit else longestAm' (n+1) $! bestFit' where (count, visited) = amCn maxval n bestFit' = if chainLen > count then bestFit else (count,n) properDivisorsSum :: UArray Int Int properDivisorsSum = accumArray (+) 1 (0,1000000) $ (0,-1):[(k,factor)| factor<-[2..1000000 `div` 2] , k<-[2*factor,2*factor+factor..1000000] ] propDSum n = properDivisorsSum ! n --S On Aug 30, 2007, at 11:33 AM, Chaddaï Fouché wrote:

2007/8/30, Chaddaï Fouché :

...

I managed it in 7 seconds (on 1500 MHz) with an idea close to yours (but I used IntSet, not IntMap), Daniel Fisher gave you some good ideas to achieve it, the real snail in this problem is the sumDivisors function.

I put my final solution on the wiki, it get it done in 6s now (on a Pentium M 1.73Mhz).

-- Jedaï _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe