patternMinor
HackerRank - Candies
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
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 rsSolution
You might consider using the trick of extending your array by one on both ends, ie. to include indices 0 and
and then
Also, you can eliminate the boundary assignments in
Finally you can use these definitions to make the guards more succinct:
n+1, and assign:ratings[0] = ratings[n+1] = 0
candies[0] = candies[n+1] = 0and 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] = 0candies = 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.