2
\$\begingroup\$

The following is the conclusion in a long chain of attempts to solve Project Euler problem #14 (Longest Collatz sequence) on HackerRank in the Haskell programming language.


The problem is defined as follows:

The following iterative sequence is defined for the set of positive integers:

n → n/2 (n is even)

n → 3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following sequence:

13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

It can be seen that this sequence (starting at 13 and finishing at 1) contains 10 terms. Although it has not been proved yet (Collatz Problem), it is thought that all starting numbers finish at 1.

Which starting number, under a given N, produces the longest chain?

An existing question discusses the problem in the context of the original Project Euler constraints, namely:

Each problem has been designed according to a "one-minute rule", which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.

Note the ambiguous specification of the host machine's processing power, and the lack of any space (memory) constraints. For the problem itself:

Which starting number, under one million, produces the longest chain?

Only one input value (1,000,000) is given, and one output value is requested.

On the other hand, the HackerRank website gives the following constraints for Haskell programs:

Runtime: 5 seconds

Memory: 512 MB

And, for the problem itself:

The first line contains an integer T, i.e. number of test cases. Next T lines will contain an integer N.

1 <= T <= 10^4

1 <= N <= 5*10^6 (i.e. 5,000,000)

These constraints are significantly more strict, and the requested computations more resource-intensive.


After dabbling (with no success) in binary-tree memoization (improved time, not space), bit manipulation (no significant improvements), tail recursion (avoiding stack overflow errors), and immutable arrays/vectors (decent runtime, but gratuitous space usage), I stumbled upon Haskell's State Thread monad and mutable vectors.

Using these tools finally appeased HackerRank's testing process. However, due to my relative inexperience with such advanced Haskell libraries and language features, I want to receive the critiques of other developers with regard to efficiency, style, and (potentially) less advanced alternatives to achieve the same result.

My working code follows:

import qualified Data.Vector.Unboxed.Mutable   as M
import qualified Data.Vector.Unboxed           as U
import           Data.Vector.Generic            ( iscanl' )
import           Data.Bits                      ( shiftR )
import           Control.Monad.ST               ( runST )
import           Control.Monad                  ( forM_
                                                , forM
                                                )

collatzLengthVector :: Int -> U.Vector Int
collatzLengthVector n = runST $ do
    vec <- M.replicate n (-1)
    M.write vec 0 0
    M.write vec 1 1
    let c x = if even x then shiftR x 1 else 3 * x + 1
    let f x = do
            -- (-1) means "unset." (-2) means "index out of bounds."
            cache  <- if x < n then M.read vec x else pure (-2)
            result <- if cache < 0 then succ <$> f (c x) else pure cache
            if cache == (-1) then M.write vec x result else pure ()
            return result
    forM_ [2 .. n - 1] f
    U.freeze vec

chainScan :: U.Vector Int -> Int -> Int -> Int -> Int
chainScan vec i i' l = let l' = vec U.! i' in if l >= l' then i else i'

longestChains :: U.Vector Int -> U.Vector Int
longestChains vec = U.tail $ iscanl' (chainScan vec) 0 vec

main = do
    inputSize <- getLine
    let n = read inputSize :: Int
    inputs <- forM [1 .. n] (const getLine)
    let ints   = map read inputs :: [Int]
    let chains = longestChains . collatzLengthVector . succ . maximum $ ints
    mapM_ (print . (chains U.!)) ints

Aside from general critiques, I am curious to hear:

  1. Is this scenario a good use case for mutable data structures in Haskell? Why or why not?
  2. What best practices exist for distinguishing between the various different types of Vectors in Haskell's library offerings? I struggled to keep straight in my head whether I should be calling e.g. freeze from the Mutable package, Unboxed package, Generic package, etc.
  3. Should I have simply abandoned Haskell altogether for HackerRank's version of this problem? I stuck with it because my goal is to learn Haskell. However, from a pragmatic perspective, I feel confident that I could have discerned the underlying inefficiencies of my old solutions and solved the problem elegantly in, say, C++, and gained the immediate benefits of mutable cache memory as a standard language construct.
\$\endgroup\$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.