On Sat, 7 Jun 2008 12:26:17 +0300
"Slavomir Kaslev"
I was just brushing my haskell-fu skills writing a solution for Google Treasure Hunt Problem 4. Hers is what it looks like:
primes = sieve [2..] where sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0]
sumOf n l = sum (take n l) : sumOf n (tail l)
find l = foldl1 aux l where aux (x:xs) (y:ys) | x == y = x : aux xs ys | x < y = aux xs (y:ys) | x > y = aux (x:xs) ys
puzzle = find (reverse [primes, p7, p17, p41, p541]) where p7 = sumOf 7 primes p17 = sumOf 17 primes p41 = sumOf 41 primes p541 = sumOf 541 primes
main = do mapM (\x -> putStrLn $ show x) puzzle
While the code is quite readable and straight forward it is as slow as tortoise with four legs broken. What optimizations would you suggest, while still keeping the code clear and highlevel?
While I can't quite prove it, I surmise find is wasting a lot of time tracking down numbers which are sums of three or four of those lists before continuing. Here's mine:
sliding n = map (sum . take n) $ tails primes
merge (x:xs) (y:ys) | x < y = x:merge xs (y:ys) | otherwise = y:merge (x:xs) ys
four = filter (\l -> length l == 5) $ group $ foldr1 merge $ map sliding [1,5,43,107,689]
In my original implementation I used an isPrime test at the end, but I like your approach better (hence the 1 in map sliding). Does this still count as "clear and highlevel"? :) Dries Harnie