# icyrock.com

HomeOld blogOld blog 2

# PureScript solution to Project Euler problem 70

`2023-08-22 19:46`

Problem details at Project Euler problem 70 page.

## Test

``````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)

``````

## Solution

``````module Euler070 where

import Prelude

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

``````