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)

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