Hi Darren, On Thu, Sep 27, 2012 at 06:22:56PM -0700, Darren Grant wrote:
collatz 1 = [1] collatz n = let next x | even x = x `div` 2 | otherwise = 3*x+1 in n:collatz (next n)
why creating a list if you're only interested in its length? Something like a 'collatzLength' function could be suitable. Instead of adding it to the list just increase an accumulator. collatzLength n = go n 0 where go n acc ... ... or collatzLength n lenCache = go n 0 lenCache where go n acc lenCache ... ...
import qualified Data.Map as M
type CollatzSubMap = M.Map Int [Int]
collatz :: (Int, CollatzSubMap) -> ([Int], CollatzSubMap) collatz (1,m) = ([1], m) collatz (n,m) = let next x | even x = x `div` 2 | otherwise = 3*x+1 in case M.lookup n m of Nothing -> let (ns,m') = collatz (next n, m) in (n:ns, M.insert n (n:ns) m') Just ns -> (ns,m)
result = maximum [length $ fst $ collatz (x, M.empty) | x <- [1..999999] :: [Int]]
Where I'm currently stumped is in feeding the resulting map from one call to collatz into the next iteration in the list comprehension; that M.empty should carry the end result of previous iterations.
why creating a list if you only want its maximum value? result = go 1 0 M.empty where go n maxLen lenCache ... ... Greetings, Daniel