Home

PureScript solution to Project Euler problem 55

2022-Apr-10 14:53
purescriptproject-euler

Problem details at Project Euler problem 55 page.

Test

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
module Euler055Test (euler55suite) where
 
import Prelude
 
import Data.BigInt as BI
import Euler055 (euler55, isLychrel, isPalindrome)
import Test.Unit (TestSuite, suite, test)
import Test.Unit.Assert as Assert
 
euler55suite :: TestSuite
euler55suite =
  suite "Euler 55" do
    test "Warmup" do
      Assert.equal false (isPalindrome (BI.fromInt 47))
      Assert.equal false (isPalindrome (BI.fromInt 74))
      Assert.equal true (isPalindrome (BI.fromInt 121))
 
      Assert.equal false (isPalindrome (BI.fromInt 349))
      Assert.equal false (isPalindrome (BI.fromInt 943))
      Assert.equal false (isPalindrome (BI.fromInt 1292))
      Assert.equal false (isPalindrome (BI.fromInt 2921))
      Assert.equal false (isPalindrome (BI.fromInt 4213))
      Assert.equal false (isPalindrome (BI.fromInt 3124))
      Assert.equal true (isPalindrome (BI.fromInt 7337))
 
      Assert.equal false (isLychrel 47)
      Assert.equal false (isLychrel 349)
      Assert.equal true (isLychrel 196)
      Assert.equal true (isLychrel 4994)
      Assert.equal true (isLychrel 10677)
 
    test "Real" do
      Assert.equal 249 (euler55 10000)

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
module Euler055 where
 
import Prelude
 
import Data.Array (filter, length, range, reverse)
import Data.BigInt (BigInt)
import Data.BigInt as BI
import Data.List.Lazy as LL
import Data.Maybe (fromJust)
import Data.String (fromCodePointArray, toCodePointArray)
import Data.String as S
import Partial.Unsafe (unsafePartial)
 
reverseStr :: String -> String
reverseStr = fromCodePointArray <<< reverse <<< toCodePointArray
 
isPalindrome :: BigInt -> Boolean
isPalindrome n =
  let s = BI.toString n
      {after, before} = S.splitAt (S.length s `div` 2) s
  in S.take (S.length before) (reverseStr after) == before
 
cands :: Int -> LL.List BigInt
cands n =
  let f m = m + unsafePartial fromJust (BI.fromString (reverseStr (BI.toString m)))
  in LL.take 50 $ LL.drop 1 $ LL.iterate f (BI.fromInt n)
 
isLychrel :: Int -> Boolean
isLychrel = LL.null <<< LL.filter isPalindrome <<< cands
 
euler55 :: Int -> Int
euler55 n = (length <<< filter isLychrel <<< range 1) (n - 1)