Spoilers! Project Euler solutions in Haskell

Not having done any Haskell programming in ages, I was provoked by Louis Sterrett to try some of the Euler Project problems. Even simple programs are good & healthy exercise, excellent for driving off the spleen and regulating the circulation. Besides, I’m still not very au fait with standard Haskell style and idioms, so it’s interesting to compare my solutions with others’ – the Haskell wiki also has some suggested solutions.

Here are my solutions to problems 1-2 and 4-5  (my solution to problem 3 was a little too disgusting even for my plebeian tastes; the ones on the Haskell wiki are much better). Don’t read ahead if you want to try the problems yourself!

  1. Find the sum of all the multiples of 3 or 5 below 1000.

    Solution 1 – brute force:

    problem1 = sum $ nub $ filter (`isMultipleOf` [3,5]) [1..999]
      where
        isMultipleOf n factors = (filter (\f -> n `mod` f == 0) factors) /= []
    

    “nub” filters out duplicates from a list – why it’s not called something like “unique”, I don’t know.

    Solution 2 – formula for summing the series:

    -- calculate sum of multiples of n, up to limit
    sumToLimit f limit = f * (upper) * (upper + 1) `div` 2
      where
        upper = (limit-1) `div` f
    
    problem1' =
      (sumToLimit 3 limit) + (sumToLimit 5 limit) - (sumToLimit 15 limit)
    
  2. Find the sum of even-valued terms in the Fibonacci sequence whose values do not exceed four million.

    Solution 1 – brute force:

    fibNums = 1 : 2 : (generateFibs 1 2)
      where
        generateFibs n1 n2  =
          let next = n1 + n2
          in next : (generateFibs n2 next)
    
    problem2 = sum $ filter even $ takeWhile (< 4000000) fibNums
    

    Solution 2 – Binet’s formula for terms of the sequence (see Wikipedia).

    fib n = floor $ ((a ** n) / (5 ** 0.5)) + 0.5
      where
        a = (1 + (5 ** 0.5)) / 2
    
    problem2' = sum $ filter even $ takeWhile (< 4000000) $ tail $ map fib [1..]
    

    (The Project Euler page defines the Fibonacci sequence as starting “1, 2, 3 …” rather than “1, 1, 2, 3 …”, so the “tail” function is used to discard the initial, unnecessary “1”.)

  1. Find the largest palindrome made from the product of two 3-digit numbers.

    Solution:

    import Data.List (sort)
    
    isPalindrome xs = xs == (reverse xs)
    isPalindromicNum = isPalindrome . show
    
    problem4 = last $ sort $ palindromes
      where
        threeDigitNums = [999, 998 .. 100]
        palindromes =
          [i * j | i <- threeDigitNums, j <- threeDigitNums, isPalindromicNum (i*j)]
    
  2. What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

    Solution:

    problem5 = foldr lcm 1 [1..20]
    

    (This is almost cheating, really, because Haskell has a “lowest common multiple” function built in.)

Advertisements