module Euler070Test (euler70suite) where

import Prelude

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

euler70suite :: TestSuite
euler70suite =
  suite "Euler 70" do
    test "Warmup" do
      delay (Milliseconds 0.0)
      Assert.equal (Just 75841) (euler70 87109)

    test "Real" do
      delay (Milliseconds 0.0)
      Assert.equal (Just 8319823) (euler70 10_000_000)

module Euler070 where

import Prelude

import Control.Monad.ST (ST, for, run)
import Data.Array (drop, filter, fromFoldable, mapWithIndex, sort, (..))
import Data.Array.ST (STArray, modify, peek, withArray)
import Data.Foldable (minimumBy)
import Data.Int (toNumber)
import Data.List as L
import Data.Maybe (Maybe(..))
import Data.Tuple (Tuple(..), fst)

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
      for 1 (1 + n / i) \j -> do
        modify (j * i) (\vj -> vj - vj / i) a

sieve :: Int -> Array (Tuple Int Int)
sieve n =
  let phi = run (withArray (crosser n) (0..n))
  in mapWithIndex Tuple phi

digits :: Int -> Array Int
digits n =
  let go k
        | k < 10 = L.singleton k
        | otherwise = k `mod` 10 L.: go (k `div` 10)
  in sort $ fromFoldable $ go n

isPerm :: Tuple Int Int -> Boolean
isPerm (Tuple x y) = digits x == digits y

ratio :: Tuple Int Int -> Number
ratio (Tuple x y) = toNumber x / toNumber y

euler70 :: Int -> Maybe Int
euler70 = map fst <<< minimumBy (comparing ratio) <<< drop 2 <<< filter isPerm <<< sieve