icyrock.com

HomeOld blogOld blog 2

PureScript solution to Project Euler problem 57

2022-07-30 12:52

Problem details at Project Euler problem 57 page.

Test

module Euler057Test (euler57suite) where

import Prelude

import Data.BigInt as BI
import Data.List.Lazy as LL
import Effect.Aff (Milliseconds(..), delay)
import Euler057 (ND(..), euler57, expansions)
import Test.Unit (TestSuite, suite, test)
import Test.Unit.Assert as Assert

euler57suite :: TestSuite
euler57suite =
  suite "Euler 57" do
    test "Warmup" do
      delay (Milliseconds 0.0)
      Assert.equal (LL.fromFoldable
        [ ND (BI.fromInt 3) (BI.fromInt 2)
        , ND (BI.fromInt 7) (BI.fromInt 5)
        , ND (BI.fromInt 17) (BI.fromInt 12)
        , ND (BI.fromInt 41) (BI.fromInt 29)
        , ND (BI.fromInt 99) (BI.fromInt 70)
        , ND (BI.fromInt 239) (BI.fromInt 169)
        , ND (BI.fromInt 577) (BI.fromInt 408)
        , ND (BI.fromInt 1393) (BI.fromInt 985)
        ]) (expansions 8)

    test "Real" do
      delay (Milliseconds 0.0)
      Assert.equal 153 (euler57 1000)

Solution

module Euler057 where

import Prelude

import Data.BigInt (BigInt)
import Data.BigInt as BI
import Data.Generic.Rep (class Generic)
import Data.List.Lazy as LL
import Data.Show.Generic (genericShow)
import Data.String as S

data ND = ND BigInt BigInt

derive instance ndEq :: Eq ND
derive instance ndGeneric :: Generic ND _
instance ndShow :: Show ND where
  show = genericShow

expansions :: Int -> LL.List ND
expansions e =
  let f (ND n d) = ND d (BI.fromInt 2 * d  + n)
      r = LL.take e $ LL.iterate f (ND (BI.fromInt 1) (BI.fromInt 2))
      g (ND n d) = ND (n + d) d
  in map g r

isNumLonger :: ND -> Boolean
isNumLonger (ND n d) = S.length (BI.toString n) > S.length (BI.toString d)

euler57 :: Int -> Int
euler57 e = LL.length $ LL.filter isNumLonger (expansions e)