icyrock.com

Home

PureScript solution to Project Euler problem 12

2018-Sep-30 22:37
purescriptproject-euler

Problem details at Project Euler problem 12 page.

Test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
module Euler012Test (euler12suite) where
 
import Prelude
 
import Data.Maybe (Maybe(..))
import Euler012 (euler12)
import Test.Unit (TestSuite, suite, test)
import Test.Unit.Assert as Assert
 
euler12suite :: forall e. TestSuite e
euler12suite =
  suite "Euler 12" do
    test "Warmup" do
      Assert.equal (Just 28) (euler12 5)
    test "Real" do
      Assert.equal (Just 76576500) (euler12 500)

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
module Euler012 (euler12) where
 
import Prelude
 
import Data.Int (floor, toNumber)
import Data.Maybe (Maybe(..))
import Math (sqrt)
 
divCount :: Int -> Int
divCount n =
  let sqn = (floor <<< sqrt <<< toNumber) n
      divc i
        | n `mod` i == 0 = 1
        | otherwise      = 0
      go i c
        | i == sqn  = if sqn * sqn == n
                      then 2 * c + 1
                      else 2 * (c + divc i)
        | otherwise = go (i + 1) (c + divc i)
  in go 1 0
 
search :: Int -> Int -> Int -> Maybe Int
search n i v
  | divCount v > n = Just v
  | otherwise      =  search n (i + 1) (v + i)
 
euler12 :: Int -> Maybe Int
euler12 n = search n 2 1