Home

PureScript solution to Project Euler problem 35

2020-Aug-26 21:14
purescriptproject-euler

Problem details at Project Euler problem 35 page.

Test

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
module Euler035Test (euler35suite) where
 
import Prelude
 
import Euler035 (euler35)
import Test.Unit (TestSuite, suite, test)
import Test.Unit.Assert as Assert
 
euler35suite :: TestSuite
euler35suite =
  suite "Euler 35" do
    test "Warmup" do
      Assert.equal 13 (euler35 100)
    test "Real" do
      Assert.equal 55 (euler35 1000000)

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
module Euler035 where
 
import Prelude
 
import Data.Array (all, filter, length, range, (:))
import Data.Int (pow)
import Data.Set (Set, fromFoldable, member)
 
isPrime :: Int -> Boolean
isPrime n =
  let go j
        | j * j > n      = true
        | n `mod` j == 0 = false
        | otherwise      = go (j + 1)
  in go 2
 
primes :: Int -> Set Int
primes n = fromFoldable <<< filter isPrime $ range 2 n
 
rotate :: Int -> Int -> Int
rotate n p = (n `div` 10) + (n `mod` 10) * p
 
digits :: Int -> Int
digits n
  | n < 10    = 1
  | otherwise = 1 + digits (n `div` 10)
 
rotations :: Int -> Array Int
rotations n =
  let d = digits n
      p = pow 10 (d - 1)
      go j k
        | j == 0    = []
        | otherwise = k : go (j - 1) (rotate k p)
  in go d n
 
isCircular :: Set Int -> Int -> Boolean
isCircular p n = all (_ `member` p) (rotations n)
 
euler35 :: Int -> Int
euler35 n = length <<< filter (isCircular (primes n)) $ range 2 (n - 1)