# icyrock.com

HomeOld blogOld blog 2

# PureScript solution to Project Euler problem 71

2023-09-30 19:36

Problem details at Project Euler problem 71 page.

## Test

module Euler071Test (euler71suite) where

import Prelude

import Data.Maybe (Maybe(..))
import Effect.Aff (Milliseconds(..), delay)
import Euler071 (euler71)
import Test.Unit (TestSuite, suite, test)
import Test.Unit.Assert as Assert

euler71suite :: TestSuite
euler71suite =
suite "Euler 71" do
test "Warmup" do
delay (Milliseconds 0.0)
Assert.equal (Just 2) (euler71 8)

test "Real" do
delay (Milliseconds 0.0)
Assert.equal (Just 428570) (euler71 1_000_000)

## Solution

module Euler071 where

import Prelude

import Data.Array (catMaybes, range)
import Data.BigInt (BigInt, fromInt, toInt, toNumber)
import Data.Foldable (maximum)
import Data.Int (ceil)
import Data.Maybe (Maybe(..))
import Data.Rational (Ratio, numerator, (%))

ratios :: BigInt -> Maybe (Ratio BigInt)
ratios n =
let ub = fromInt \$ 1 + ceil (toNumber n * 3.0 / 7.0)
rt = fromInt 3 % fromInt 7
go v
| v == fromInt 0 = Nothing
| v % n < rt && gcd v n == fromInt 1 = Just \$ v % n
| otherwise = go (v - fromInt 1)
in go ub

euler71 :: Int -> Maybe Int
euler71 = join <<< map toInt <<< map numerator
<<< maximum <<< catMaybes <<< map ratios <<< map fromInt <<< range 1