Home

PureScript solution to Project Euler problem 53

2022-Feb-28 15:53
purescriptproject-euler

Problem details at Project Euler problem 53 page.

Test

1
2
3
4
5
6
7
8
9
10
11
module Euler053Test (euler53suite) where
 
import Euler053 (euler53)
import Test.Unit (TestSuite, suite, test)
import Test.Unit.Assert as Assert
 
euler53suite :: TestSuite
euler53suite =
  suite "Euler 53" do
    test "Real" do
      Assert.equal 4075 (euler53 100)

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
module Euler053 where
 
import Prelude
 
import Control.MonadZero (guard)
import Data.Array (range, scanl, zip, (:))
import Data.BigInt (BigInt)
import Data.BigInt as BI
import Data.Foldable (sum)
import Data.Map (Map)
import Data.Map as M
import Data.Maybe (Maybe(..))
 
facts :: Int -> Map Int BigInt
facts n =
  let ks = range 1 n
      v1 = BI.fromInt 1
      vs = v1 : scanl (*) v1 (BI.fromInt <$> range 2 n)
      es = zip ks vs
  in M.fromFoldable es
 
combs :: Map Int BigInt -> Int -> Int -> Maybe BigInt
combs fs r n = do
  rf  <- M.lookup r fs
  nrf <- M.lookup (n - r) fs
  nf  <- M.lookup n fs
  pure $ nf / rf / nrf
 
euler53 :: Int -> Int
euler53 m = sum do
  let fs = facts m
  let mbi = BI.fromInt 1_000_000
  n <- range 1 m
  r <- range 1 n
  let cm = combs fs r n
  guard $ case cm of
    Nothing -> false
    Just c  -> c > mbi
  pure 1