On Sat, 7 Jun 2008 12:26:17 +0300 "Slavomir Kaslev" <[EMAIL PROTECTED]> wrote:
> 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
signature.asc
Description: PGP signature
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
