icyrock.com

Home

PureScript solution to Project Euler problem 23

2019-Aug-16 00:11
purescriptproject-euler

Problem details at Project Euler problem 23 page.

Test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
module Euler023Test (euler23suite) where
 
import Prelude
 
import Euler023 (euler23)
import Test.Unit (TestSuite, suite, test)
import Test.Unit.Assert as Assert
 
euler23suite :: TestSuite
euler23suite =
  suite "Euler 23" do
    test "Warmup" do
      Assert.equal 276 (euler23 24)
    test "Real" do
      Assert.equal 4179871 (euler23 28122)

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
38
39
40
41
42
43
44
45
module Euler023 where
 
import Prelude
 
import Control.Monad.ST as ST
import Control.Monad.ST.Internal as STI
import Data.Array (filter, range)
import Data.Array.ST as AST
import Data.Foldable (sum)
import Data.Int (floor, toNumber)
import Math (sqrt)
 
sqrti :: Int -> Int
sqrti = toNumber >>> sqrt >>> floor
 
divisors :: Int -> Array Int
divisors n =
  let f i
        | n `mod` i /= 0 = []
        | i == 1 || n / i == i = [i]
        | otherwise = [i, n / i]
  in range 1 (sqrti n) >>= f
 
isAbundant :: Int -> Boolean
isAbundant n = sum (divisors n) > n
 
abundants :: Int -> Array Int
abundants = range 1 >>> filter isAbundant
 
notTwo :: Int -> Array Int
notTwo n =
  let as = abundants n
      rs = range 0 n
  in ST.run (do
      xs <- AST.thaw rs
      void $ STI.foreach as \i -> do
        void $ STI.foreach as \j -> do
          let s = i + j
          when (s <= n) do
            void $ AST.poke s 0 xs
      AST.unsafeFreeze xs
    )
 
euler23 :: Int -> Int
euler23 = notTwo >>> sum