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

[Sterling Clover]

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é <chaddai.fouche at gmail.com>:
>> 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe