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é <[EMAIL PROTECTED]>:
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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
