module Euler069Test (euler69suite) where

import Prelude

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

euler69suite :: TestSuite
euler69suite =
  suite "Euler 69" do
    test "Warmup" do
      delay (Milliseconds 0.0)
      Assert.equal (Just 6) (euler69 10)

    test "Real" do
      delay (Milliseconds 0.0)
      Assert.equal (Just 510510) (euler69 1_000_000)

module Euler069 where

import Prelude

import Control.Monad.ST (ST, for, run)
import Data.Array (mapWithIndex, (..))
import Data.Array.ST (STArray, peek, poke, withArray)
import Data.Foldable (maximumBy)
import Data.Int (toNumber)
import Data.Maybe (Maybe(..), maybe)
import Data.Tuple (Tuple(..), fst, snd)

crosser :: forall h. Int -> STArray h Int -> ST h Unit
crosser n a =
  for 2 n \i -> do
    mvi <- peek i a
    when (mvi == Just i) do
      let u = 1 + n / i
      for 1 u \j -> do
        let l = j * i
        mvj <- peek l a
        maybe (pure false) (\vj -> do
          let vjn = vj - vj / i
          poke l vjn a) mvj

sieve :: Int -> Array (Tuple Int Number)
sieve n =
  let ns = 0..n
      phi = run (withArray (crosser n) ns)
      f i p = Tuple i (if p == 0 then 0.0 else toNumber i / toNumber p)
  in mapWithIndex f phi

euler69 :: Int -> Maybe Int
euler69 = map fst <<< maximumBy (comparing snd) <<< sieve