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.


Project Euler in Haskell

I’m in the process of familiarizing myself with Haskell (wouldn’t say it’s learning at this point), so decided to work on some Project Euler problems. Here are my solutions to problems 1-5. One thing to notice – they are unusually long for a Haskell program and as usual – take them with a grain of salt.

Project Euler 1 in Haskell

Project Euler problem 1

mul35 :: Int -> Int
mul35 n = sum xs
  where
    xs = [i | i <- [1..n-1], 
          (i `mod` 3 == 0) ||
          (i `mod` 5 == 0)]
    
main =
  do
    print $ mul35 10
    print $ mul35 1000

Project Euler 2 in Haskell

Project Euler problem 2

fibs :: [Int]
fibs = 1 : 2 : [a + b | (a, b) <- zip fibs (tail fibs)]

sumFibs :: Int -> Int
sumFibs ms = sum [x | x <- takeWhile (< ms) fibs, even x]

main = do
  print $ sumFibs 4000000

Project Euler 3 in Haskell

Project Euler problem 3

lpf :: Int -> Int
lpf n = if md == n then n
        else lpf (n `div` md)
        where md = head [x | x <- [2..n], n `mod` x == 0]

main = do
  print $ lpf 13195
  print $ lpf 600851475143 

Project Euler 4 in Haskell

Project Euler problem 4

import Data.List (tails)

numsLen :: Int -> [Int]
numsLen l = [mx,mx-1..mi] where
  mi = 10^(l-1)
  mx = 10^l - 1
  
digits :: Int -> [Int]
digits 0 = []
digits n = n `mod` 10 : digits (n `div` 10)

palindrome :: Int -> Bool
palindrome n = digits n == reverse (digits n)
  
lpal :: Int -> Int
lpal d = maximum ps where
  ns = numsLen d
  xss = tails ns
  ps = [y | x:xs <- xss, y <- map (* x) xs, palindrome y]
  
main = do
  print $ lpal 2
  print $ lpal 3

Project Euler 5 in Haskell

Project Euler problem 5

lcmm :: [Int] -> Int
lcmm [] = error "Empty list"
lcmm [x] = x
lcmm xs = foldr1 lcm xs

hdbf :: Int -> Int
hdbf n = lcmm [1..n] 

main = do
  print $ hdbf 10
  print $ hdbf 20
  print $ hdbf 30