icyrock.com

Home

PureScript solution to Project Euler problem 31

2020-Apr-08 18:25
purescriptproject-euler

Problem details at Project Euler problem 31 page.

Test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
module Euler031Test (euler31suite) where
 
import Prelude
 
import Euler031 (euler31)
import Test.Unit (TestSuite, suite, test)
import Test.Unit.Assert as Assert
 
euler31suite :: TestSuite
euler31suite =
  suite "Euler 31" do
    test "Warmup" do
      Assert.equal 11 (euler31 10)
    test "Real" do
      Assert.equal 73682 (euler31 200)

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
module Euler031 where
 
import Prelude
 
import Data.Array (uncons)
import Data.Maybe (Maybe(..))
 
coins :: Array Int
coins = [200, 100, 50, 20, 10, 5, 2]
 
waysOne :: Int -> Int -> Array Int -> Int
waysOne n j k =
  let go 0 = ways n k
      go l = ways (n - j * l) k + go (l - 1)
  in go (n / j)
 
ways :: Int -> Array Int -> Int
ways n j =
  case uncons j of
    Nothing             -> 1
    Just { head, tail } -> waysOne n head tail
 
euler31 :: Int -> Int
euler31 n = ways n coins