4
\$\begingroup\$

Here is the solution I've written for Hacker Rank Candies challenge. It uses dynamic programming (memoization in a boxed array). I'm interested on what could be done to improve this code in term of style and performance (although it passes all the testcases of the challenge) For example, I wonder if the bunch of guards I used could be made prettier

import System.IO
import Data.Array

main = do
    contents <- getContents
    print $ runTest contents

runTest :: String -> Int
runTest = sum . candies . map read . tail . lines

candies :: [Int] -> [Int]
candies rs = elems candies where
    go i 
        | n ==1 = 1
        | i == 1 = if (ri > riplus) then candies ! (2) + 1 else 1
        | i == n = if (ri > riminus) then candies ! (n - 1) + 1 else 1
        | ri > riminus  && ri > riplus = max (candies! (i-1)) (candies! (i+1)) + 1
        | ri > riminus = candies! (i-1) + 1
        | ri > riplus = candies! (i+1) + 1
        | otherwise = 1
        where
            ri = ratings!i
            riplus = ratings!(i+1)
            riminus = ratings!(i-1)
    ratings = listArray (1,n) rs
    candies = listArray (1,n) [go i | i <- [1..n]]
    n = length rs
\$\endgroup\$
2
\$\begingroup\$

You might consider using the trick of extending your array by one on both ends, ie. to include indices 0 and n+1, and assign:

ratings[0] = ratings[n+1] = 0
candies[0] = candies[n+1] = 0

and then go 1 and go n will be handled by the other clauses.

Also, you can eliminate the boundary assignments in go with:

candies = listArray (0,n+1) $ [0] ++ [go i | i <- [1..n] ] ++ [0]

Finally you can use these definitions to make the guards more succinct:

go i | incL && incR  = 1 + max cL cR
     | incL          = 1 + cL
     | incR          = 1 + cR
     | otherwise     = 1
  where incL = (ratings!(i-1)) < (ratings!i)
        incR = (ratings!i) > (ratings(i+1))
        cL   = candies!(i-1)
        cR   = candies!(i+1)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.