5

I wrote this solution to the coin change problem on HackerRank:

makeChange :: Int -> [Int] -> Int
makeChange n ys = go n (sort ys)
    where go _ [] = 0
          go n (x:xs)
            | x == n = 1
            | x > n = 0
            | otherwise = (makeChange n xs) + (makeChange (n - x) (x:xs))

However it times out on some of the larger test cases. I saw this article on implementing memoization using let bindings but it mostly went over my head and I'm not sure how I would implement that here. Any help?

I rewrote it and got a substantial performance improvement, but i'm still timing out on the hacker rank exercise:

makeChange' :: Int -> [Int] -> Int
makeChange' =
    let go _ [] = 0
        go n (x:xs)
          | x == n = 1
          | x > n = 0
          | otherwise = (makeChange' n xs) + (makeChange' (n - x) (x:xs))
    in go

f (x:y:xs) = makeChange' x ys
    where ys = sort xs
main = interact $ show . f . map read . words

I moved the pre-sort into an intermediate function f which I am also using to handle the input from Hacker Rank. They give you a string with the change target, the length of the change array, and the array of change units. I use f to drop the length from the input.

Improve this question

3 Answers 3

Reset to default
6

This problem does not need memoization. If a is an infinite length list where a !! n is the total number of ways to make a total sum of n with some set of coins, and you get a new distinct coin of value x, you can update the list a to the new list b using the facts that:

  • The first x elements will not change; because, you cannot use the new coin for a sum less than x. so, take x a.

  • For the remaining elements:

    b(n) = a(n) + b(n - x)

    where the first summand means do not use the new coin at all, and the 2nd summand means use it at least once.

This can be simply implemented using a right fold, with initial value [1, 0, 0, ...], because with no coins the only sum you may make is zero. Haskell laziness is also very useful here:

solve :: Int -> [Int] -> Int
solve n xs = (foldr go (1:repeat 0) xs) !! n
  where go x a = let b = (take x a) ++ zipWith (+) b (drop x a) in b

then:

\> solve 4 [1, 2, 3]
4
\> solve 10 [2, 5, 3, 6]
5

as in the examples in the question.

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Briliiant. And seems significantly faster than the array version in Probie's answer.
Wow looks like an amazing solution. Its way beyond my skill level to understand it at this point, but i'm trying to work through it.
2

I think this is best solved with an explicit 2D array. In effect, we give the result of each function call a location in this array. This allows us to only need to evaluate function at most once. There's a tiny bit more boilerplate we have to add, because we need to check if we'd index outside the array

makeChange :: Int -> [Int] -> Int
makeChange n ys = arr ! (n,1)
    where 
      len = length xs
      xs = sort ys
      arr = array ((1,1),(n,len)) [((i,j), go i j x)| i <- [1..n], (j,x) <- zip [1..] xs]
      go n ix x | x == n = 1
                | x > n = 0
                | otherwise = (if ix + 1 <= len then (arr ! (n, ix+1)) else 0) + 
                              (if (n-x) > 0 then (arr ! ((n-x), ix)) else 0)
Improve this answer

Comments

2

I'll try to demonstrate how behzad.nouri's code is working in an effort to understand it myself:

Keeping in mind Haskell's laziness, we observe that !! n means our final list will be evaluated up to it's (n+1)th element. Our main block for each coin is:

let b = (take x a) ++ zipWith (+) b (drop x a) in b

There's a little trick here that works because b is a list. Note that a similar kind of self-reference wouldn't work if b were an integer. Let's say our only coin was 2:

 > let b = (take 2 [1,0,0,0,0]) ++ zipWith (+) b (drop 2 [1,0,0,0,0]) in b
=> [1,0,1,0,1]

(Which means one way to make zero, one way to make two, and one way to make four.) What happens is b gets built recursively as it's self-referenced until there is a length match for the zip evaluation:

 > zipWith (+) [] (drop 2 [1,0,0,0,0])
=> []
-- But we prepended [1,0] so the next `b` is [1,0]
 > zipWith (+) [1,0] (drop 2 [1,0,0,0,0])
=> [1,0]
-- But we prepended [1,0] so the next `b` is [1,0,1,0]
 > zipWith (+) [1,0,1,0] (drop 2 [1,0,0,0,0])
=> [1,0,1]
-- But we prepended [1,0] so the result matching the length is [1,0,1,0,1]

Now let's use this knowledge to follow through solve 4 [1,2,3]:

let b = (take 3 [1,0,0,0,0]) ++ zipWith (+) b (drop 3 [1,0,0,0,0]) in b

take 3 [1,0,0,0,0] -- n+1 elements are evaluated from the infinite list
=> [1,0,0]

++       [0,0] -- drop 3 from [1,0,0,0,0]
     (+) []
     =>  []
     -- prepend [1,0,0]
     =>  [1,0,0]

++       [0,0]
     (+) [1,0,0]
     =>  [1,0]
     -- prepend [1,0,0]
     =>  [1,0,0,1,0]

That's one way to make zero and one way to make three. Next:

let b = (take 2 [1,0,0,1,0]) ++ zipWith (+) b (drop 2 [1,0,0,1,0]) in b

take 2 [1,0,0,1,0]
=> [1,0]

++     [0,1,0]
   (+) []
   =>  []
   -- prepend [1,0]
   =>  [1,0]

++     [0,1,0]
   (+) [1,0]
   =>  [1,1,0]
   -- prepend [1,0]
   =>  [1,0,1,1,0]

++     [0,1,0]
   (+) [1,0,1,1,0]
   =>  [1,1,1]
   -- prepend [1,0]
   =>  [1,0,1,1,1]

That's one way to make 0, one way to make 2, one way to make 3, and one way to make 4. Next:

let b = (take 1 [1,0,1,1,1]) ++ zipWith (+) b (drop 1 [1,0,1,1,1]) in b

This is the one with the most iterations since b is built from just one element

take 1 [1,0,1,1,1]
=> [1]

++   [0,1,1,1]
 (+) []
 =>  []
 -- prepend [1]
 =>  [1]

++   [0,1,1,1]
 (+) [1]
 =>  [1]
 -- prepend [1]
 =>  [1,1]

++   [0,1,1,1]
 (+) [1,1]
 =>  [1,2]
 -- prepend [1]
 =>  [1,1,2]

++   [0,1,1,1]
 (+) [1,1,2]
 =>  [1,2,3]
 -- prepend [1]
 =>  [1,1,2,3]

++   [0,1,1,1]
 (+) [1,1,2,3]
 =>  [1,2,3,4]
 -- prepend [1]
 =>  [1,1,2,3,4]

That's 1 way to make 0, 1 way to make 1, 2 ways to make 2, 3 ways to make 3, and 4 ways to make 4.

Improve this answer

Comments

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.