module Euler072Test (euler72suite) where

import Prelude

import Data.BigInt (fromInt, fromString)
import Data.Maybe (Maybe(..))
import Effect.Aff (Milliseconds(..), delay)
import Euler072 (euler72)
import Test.Unit (TestSuite, suite, test)
import Test.Unit.Assert as Assert

euler72suite :: TestSuite
euler72suite =
  suite "Euler 72" do
    test "Warmup" do
      delay (Milliseconds 0.0)
      Assert.equal (fromInt 21) (euler72 8)

    test "Real" do
      delay (Milliseconds 0.0)
      Assert.equal (fromString "303963552391") (Just $ euler72 1_000_000)

module Euler072 where

import Prelude

import Control.Monad.Rec.Class (Step(..), tailRec)
import Data.Array (fromFoldable, range, zip)
import Data.BigInt (BigInt, fromInt)
import Data.Foldable (foldl, sum)
import Data.Map as Map
import Data.Maybe (Maybe(..))

phi :: Int -> Array BigInt
phi dm =
  let r = fromInt <$> range 2 dm
      mi = Map.fromFoldable $ zip r r
      g {m, d, n}
        | n <= fromInt dm = Loop
           {m: Map.update (\v -> Just $ v * (d - fromInt 1) / d) n m, d, n: n + d}
        | otherwise = Done m
      f m d
        | Map.lookup d m == Just d = tailRec g {m, d, n: d}
        | otherwise = m
      mr = foldl f mi r
  in (fromFoldable <<< Map.values) mr

euler72 :: Int -> BigInt
euler72 = sum <<< phi