icyrock.com

HomeOld blogOld blog 2

PureScript solution to Project Euler problem 64

2023-02-10 00:08

Problem details at Project Euler problem 64 page.

Test

module Euler064Test (euler64suite) where

import Prelude

import Effect.Aff (Milliseconds(..), delay)
import Euler064 (euler64)
import Test.Unit (TestSuite, suite, test)
import Test.Unit.Assert as Assert

euler64suite :: TestSuite
euler64suite =
  suite "Euler 64" do
    test "Warmup" do
      delay (Milliseconds 0.0)
      Assert.equal 4 (euler64 13)

    test "Real" do
      delay (Milliseconds 0.0)
      Assert.equal 1322 (euler64 10_000)

Solution

module Euler064 where

import Prelude

import Data.Array (filter, length, range)
import Data.Int (floor, odd, round, toNumber)
import Data.Number (sqrt)
import Data.Set (empty, insert, member)
import Data.Tuple (Tuple(..))
import Data.Tuple.Nested (Tuple3, tuple3)

irrational :: Int -> Boolean
irrational n = 
  let si = floor $ sqrt $ toNumber n
  in si * si /= n

next :: Number -> Tuple3 Int Int Int -> Tuple3 Int Int Int
next s (Tuple _ (Tuple j (Tuple k _))) = 
  let jo = toNumber j
      ko = toNumber k
      jn = round $ (s * s - ko * ko) / jo
      an = floor $ (s + ko) / toNumber jn
      kn = an * jn - k
  in tuple3 an jn kn

repeating :: Int -> Int
repeating n =
  let s = sqrt $ toNumber n
      si = floor s
      go j v t =
        let tn = next s t
        in case j of
             _
               | j == (-1)   -> go (j + 1) v tn
               | member tn v -> j
               | otherwise   -> go (j + 1) (insert tn v) tn
  in go (-1) empty (tuple3 si 1 si)

euler64 :: Int -> Int
euler64 = length
  <<< filter odd
  <<< map repeating
  <<< filter irrational
  <<< range 1