Home

PureScript solution to Project Euler problem 43

2021-Apr-01 22:05
purescriptproject-euler

Problem details at Project Euler problem 43 page.

Test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
module Euler043Test (euler43suite) where
 
import Prelude
 
import Data.BigInt as BI
import Data.Maybe (Maybe(..))
import Euler043 (euler43, prop)
import Test.Unit (TestSuite, suite, test)
import Test.Unit.Assert as Assert
 
euler43suite :: TestSuite
euler43suite =
  suite "Euler 43" do
    test "Real" do
      Assert.equal (Just true) (prop <$> BI.fromString "1406357289")
      Assert.equal (BI.fromString "16695334890") (Just $ euler43 unit)

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
46
47
48
49
module Euler043 where
 
import Prelude
 
import Data.Array (concatMap, filter, foldr, head, range, snoc, uncons, (:))
import Data.BigInt (BigInt)
import Data.BigInt as BI
import Data.Foldable (sum)
import Data.Maybe (Maybe(..))
 
inserts :: BigInt -> Array BigInt -> Array (Array BigInt)
inserts e a = case uncons a of
  Nothing           -> [[e]]
  Just {head, tail} -> (snoc a e) : (flip snoc head <$> inserts e tail)
 
perms :: Array BigInt -> Array (Array BigInt)
perms js = case uncons js of
  Nothing           -> [[]]
  Just {head, tail} -> concatMap (inserts head) (perms tail)
 
arrnToBigInt :: Array BigInt -> BigInt
arrnToBigInt = foldr (\j k -> k * BI.fromInt 10 + j) (BI.fromInt 0)
 
pandigitals :: Unit -> Array BigInt
pandigitals _ =
  let ds = BI.fromInt <$> range 0 9
      nz a = head a /= Just (BI.fromInt 0)
  in (map arrnToBigInt <<< filter nz <<< perms) ds
 
prop :: BigInt -> Boolean
prop j =
  let d234 = (j / BI.fromInt 1000000) `mod` BI.fromInt 1000
      d345 = (j / BI.fromInt 100000)  `mod` BI.fromInt 1000
      d456 = (j / BI.fromInt 10000)   `mod` BI.fromInt 1000
      d567 = (j / BI.fromInt 1000)    `mod` BI.fromInt 1000
      d678 = (j / BI.fromInt 100)     `mod` BI.fromInt 1000
      d789 = (j / BI.fromInt 10)      `mod` BI.fromInt 1000
      d890 = (j)                      `mod` BI.fromInt 1000
  in  d234 `mod` BI.fromInt 2
    + d345 `mod` BI.fromInt 3
    + d456 `mod` BI.fromInt 5
    + d567 `mod` BI.fromInt 7
    + d678 `mod` BI.fromInt 11
    + d789 `mod` BI.fromInt 13
    + d890 `mod` BI.fromInt 17
    == BI.fromInt 0
 
euler43 :: Unit -> BigInt
euler43 = sum <<< filter prop <<< pandigitals