Home

PureScript solution to Project Euler problem 15

2018-Dec-12 22:17
purescriptproject-euler

Problem details at Project Euler problem 15 page.

Test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
module Euler015Test (euler15suite) where
 
import Prelude
 
import Data.BigInt (fromString)
import Euler015 (euler15)
import Test.Unit (TestSuite, suite, test)
import Test.Unit.Assert as Assert
 
euler15suite :: forall e. TestSuite e
euler15suite =
  suite "Euler 15" do
    test "Warmup" do
      Assert.equal (fromString "6") (euler15 2)
    test "Real" do
      Assert.equal (fromString "137846528820") (euler15 20)

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
module Euler015 (euler15) where
 
import Prelude
 
import Data.Array (concat, drop, head, length, range, zip, (!!), (:))
import Data.BigInt (BigInt, fromInt)
import Data.Foldable (foldl)
import Data.Maybe (Maybe(..), fromMaybe, maybe)
import Data.Tuple (Tuple(..))
 
next :: Array BigInt -> Array BigInt
next a = concat [[fromInt 1], (g <$> zip a (drop 1 a)), [fromInt 1]]
  where g (Tuple a b) = a + b
 
type Mat a = Array (Array a)
 
pascal :: Int -> Mat BigInt
pascal n = foldl f [[fromInt 1]] (range 1 n)
  where f a _ = next r : a
          where r = fromMaybe [] (head a)
 
euler15 :: Int -> Maybe BigInt
euler15 n = maybe Nothing f (head p)
  where p = pascal (n * 2)
        f r = r !! (length r / 2)