icyrock.com

HomeOld blogOld blog 2

PureScript solution to Project Euler problem 69

2023-07-13 16:34

Problem details at Project Euler problem 69 page.

Test

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)


Solution

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