HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

HackerRank - Candies

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
hackerrankcandiesstackoverflow

Problem

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  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

Solution

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+1))
        cL   = candies!(i-1)
        cR   = candies!(i+1)

Code Snippets

ratings[0] = ratings[n+1] = 0
candies[0] = candies[n+1] = 0
candies = listArray (0,n+1) $ [0] ++ [go i | i <- [1..n] ] ++ [0]
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)

Context

StackExchange Code Review Q#101502, answer score: 2

Revisions (0)

No revisions yet.