Project Euler in Haskell – problems 6 through 10 « Blog Archive

Posted on November 30th, 2014 by icyrock.com

Project Euler in Haskell – problems 6 through 10

Continuing from the previous one, here are my solutions to problems 6-10. Same warning applies – they are unusually long for a Haskell program and as usual take them with a grain of salt.

Project Euler 6 in Haskell

Project Euler problem 6

ssdiff :: Int -> Int
ssdiff n = (sum [1..n] ^ 2) - (sum $ map (^2) [1..n])
  
main = do
  print $ ssdiff 10
  print $ ssdiff 100

Project Euler 7 in Haskell

Project Euler problem 7

import           Data.Numbers.Primes

nthprime :: Int -> Int
nthprime n = primes !! (n-1)

main = do
  print $ nthprime 6
  print $ nthprime 10001

Project Euler 8 in Haskell

Project Euler problem 8

import           Data.Char
import           Data.List

minLen :: Int -> [a] -> Bool
minLen n xs = not $ null (drop n xs)

nibbles :: Int -> [a] -> [[a]]
nibbles n xs = map (take n) $ filter (minLen n) $ tails xs

prod :: String -> Int
prod s = product $ map digitToInt s

maxProd :: String -> Int -> Int
maxProd s n = maximum $ map prod (nibbles n s)

main :: IO ()
main = do
     txt <- readFile "src/Euler/euler8.txt"
     numTxt <- return $ concat $ lines txt
     print $ maxProd numTxt 4
     print $ maxProd numTxt 13

Project Euler 9 in Haskell

Project Euler problem 9

pythTrip :: Int -> Int
pythTrip n = head [a * b * c | a <- [1..n - 2]
                             , b <- [a + 1..n - 2]
                             , let c = n - a - b
                             , c > b
                             , a ^ 2 + b ^ 2 == c ^ 2]

main :: IO ()
main = do
     print $ pythTrip 1000

Project Euler 10 in Haskell

Project Euler problem 10

This one was interesting. Using the Data.Numbers.Primes package, it’s very easy and very fast:

import qualified Data.Numbers.Primes as P

sumOfPrimes :: Int -> Integer
sumOfPrimes n = (sum . map toInteger . takeWhile (< n)) P.primes

main :: IO ()
main = do
     print $ sumOfPrimes 10
     print $ sumOfPrimes 2000000

However, I was intrigued how to do Sieve of Eratosthenes in Haskell. Here’s what I came up with:

import qualified Data.Vector.Unboxed as UV

sieve :: Int -> UV.Vector Bool
sieve m = let s = UV.replicate (1 + m) True
              sqm = (floor . sqrt . fromIntegral) m
              update v n
                | v UV.! n == False = v
                | otherwise  = UV.update v (UV.zip xs ys)
                  where sqn = n * n
                        xs = UV.enumFromStepN sqn n (1 + (m - sqn) `div` n)
                        ys = UV.replicate (UV.length xs) False
              sievep v n
                | n <= sqm = sievep (update v n) (n + 1)
                | otherwise = v
          in sievep s 2

primes :: Int -> [Int]
primes m = (UV.toList . UV.drop 2 . UV.map fst
            . UV.filter ((== True) . snd)
            . UV.zip (UV.enumFromN 0 (1 + m)) . sieve) m

sumOfPrimes :: Int -> Integer
sumOfPrimes = sum . map toInteger . primes

main :: IO ()
main = do
     print $ sumOfPrimes 10
     print $ sumOfPrimes 2000000

I must say I was a bit surprised how the process of writing turned out to be different. First, I used Vectors and Arrays package provided much confusion here. Not sure if I’m right, but looks like Vectors package is newer. Some things such as DiffArray turned out to be unsuccessful experiments, for example. Second, I found it quite un-Haskelly, given the solution is non-lazy and bounded.

I guess the number of different solutions and papers (some relatively new to that point) that I found, especially on the main Haskell Wiki page says a lot:

I guess I’ll just go with the built-in for now.

icyrock.com