Home

PureScript solution to Project Euler problem 10

2018-Jul-30 20:07
purescriptproject-euler

Problem details at Project Euler problem 10 page.

Test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
module Euler010Test (euler10suite) where
 
import Prelude
 
import Data.BigInt (fromString)
import Data.Maybe (Maybe(..))
import Euler010 (euler10)
import Test.Unit (TestSuite, suite, test)
import Test.Unit.Assert as Assert
 
euler10suite :: forall e. TestSuite e
euler10suite =
  suite "Euler 10" do
    test "Warmup" do
      Assert.equal (fromString "17") (Just $ euler10 10)
    test "Real" do
      Assert.equal (fromString "142913828922") (Just $ euler10 2000000)

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
module Euler010  where
 
import Prelude
 
import Control.Monad.Eff (Eff, forE)
import Control.Monad.ST (ST, pureST)
import Data.Array (drop, filter, (..))
import Data.Array.ST (STArray, peekSTArray, pokeSTArray, withArray)
import Data.BigInt (BigInt, fromInt)
import Data.Foldable (sum)
import Data.Int (floor, toNumber)
import Data.Maybe (Maybe(..))
import Math (sqrt)
 
floorF :: (Number -> Number) -> Int -> Int
floorF f = floor <<< f <<< toNumber
 
crosser :: forall h. Int -> STArray h Int -> Eff (st :: ST h) Unit
crosser n a =
  let sn = 1 + floorF sqrt n
  in forE 2 sn \i -> do
       v <- peekSTArray a i
       when (v == Just i) do
         let u = 1 + n / i
         forE i u \j -> do
           void $ pokeSTArray a (j * i) 0
 
genTable :: Int -> Array Int
genTable n = pureST (withArray (crosser n) (0..n))
 
genPrimes :: Int -> Array Int
genPrimes n = filter (_ /= 0) $ drop 2 $ genTable n
 
euler10 :: Int -> BigInt
euler10 n =
  let primes = genPrimes (n - 1)
  in (sum <<< map fromInt) primes