icyrock.com

HomeOld blogOld blog 2

PureScript solution to Project Euler problem 58

2022-08-31 19:46

Problem details at Project Euler problem 58 page.

Test

module Euler058Test (euler58suite) where

import Prelude

import Effect.Aff (Milliseconds(..), delay)
import Euler058 (euler58, corners, cornersPrime)
import Test.Unit (TestSuite, suite, test)
import Test.Unit.Assert as Assert

euler58suite :: TestSuite
euler58suite =
  suite "Euler 58" do
    test "Warmup" do
      delay (Milliseconds 0.0)
      Assert.equal [1] (corners 1)
      Assert.equal [3, 5, 7, 9] (corners 3)
      Assert.equal [13, 17, 21, 25] (corners 5)
      Assert.equal [31, 37, 43, 49] (corners 7)

      Assert.equal [] (cornersPrime 1)
      Assert.equal [3, 5, 7] (cornersPrime 3)
      Assert.equal [13, 17] (cornersPrime 5)
      Assert.equal [31, 37, 43] (cornersPrime 7)

    test "Real" do
      delay (Milliseconds 0.0)
      Assert.equal 26241 (euler58 10)

Solution

module Euler058 where

import Prelude

import Data.Array (filter, length)
import Data.Int (pow)

corners :: Int -> Array Int
corners 1 = [1]
corners s =
  let c = pow s 2
      ss = s - 1
  in
    [ c - 3 * ss
    , c - 2 * ss
    , c - ss
    , c
    ]

isPrime :: Int -> Boolean
isPrime n
  | n <= 3         = n > 1
  | n `mod` 2 == 0 = false
  | n `mod` 3 == 0 = false
isPrime n =
  let go i
        | i * i > n            = true
        | n `mod` i == 0       = false
        | n `mod` (i + 2) == 0 = false
        | otherwise            = go (i + 6)
  in go 5

cornersPrime :: Int -> Array Int
cornersPrime = filter isPrime <<< corners

euler58 :: Int -> Int
euler58 pct =
  let go s p c
        | (100 * p) `div` c < pct = s
        | otherwise =
            let sn = s + 2
            in go sn (p + length (cornersPrime sn)) (c + 4)
  in go 7 8 13