Number of ways to make change for an amount

Question

Task

Write a program that, given the amount to make change for and a list of coins prints out how many different ways you can make change from the coins to STDOUT.

My approach

The number to make change for is N. Take one coin C and sum the number of ways to make N - C with the other coins. Add the number of ways to make N - 2C with the other coins, etc, for all N - XC > 0 where X is the number of C coins used. Do that recursively. Memoize it so it's effectively dynamic programming.

Code

(ns hackerrank.core
  (:require [clojure.string :as string]))

(defn get-ways
  [n coins]
  (if (= n 0)
    1
    (if (= (count coins) 0)
      0
      (let [[coin & other-coins] coins]
        (reduce
          #(+ %1 (get-ways (- n (* coin %2)) other-coins))
          (if (= (mod n coin) 0) 1 0)
          (range 0 (/ n coin)))))))

(def get-ways-memoized
  (with-redefs [get-ways (memoize get-ways)] get-ways))

(let
  [n (Integer/parseInt (nth (string/split (read-line) #"\s+") 0))
   coins-line (read-line)
   coins (if (= "" coins-line)
           []
           (map #(Integer/parseInt %) (string/split coins-line #" ")))]
  (println (get-ways-memoized n coins)))

Questions

• Any Clojure style / best practices, I'm mostly doing this to learn Clojure.

• Any ideas why this wouldn't pass the timing tests on HackerRank. I've checked that the memoized function runs faster than the non-memoized one and AFAIK apart from the large stack resulting from no tail call optimization it should be equivalent to an iterative approach with a matrix storing the results.

• Is there a way to do this manually, bottom-up rather than using memoize? Pseudo-code or a hint would be great as I'd like to try to implement it myself. Intuitively it feels like there can't be a bottom-up approach because I don't know in advance which sub-problems need to be solved.

Answer 1

Any Clojure style / best practices

Your nested if statements in get-ways might be nicer as a cond:

(defn get-ways
  [n coins]
  (cond
    (= n 0) 1
    (= 0 (count coins)) 0
    :else (let ...)))

There may be other things, but I'm not a clojure pro.

Why it won't pass the timing tests on HackerRank.

I suspect your with-redefs isn't doing what you expect. with-redefs will redefine get-ways for the duration of the with-redefs block. But all you're doing in that block is returning the re-defd function. So your initial call will call the memoized function, but every recursive call just calls the orignal function, so you lose all the benefit of memoizing in the first place.

You may be better off wrapping your (println (get-ways-memoized n coins))) in with-redefs, or maybe just redfining get-ways to always be memoized:

(def get-ways 
  (memoize (fn
    [n coins]
    ...)

Is there a way to do this manually.

Not sure, I'll leave that to someone else to try and answer.

Answer 2

Practically, the first thing I'd change is move the reading/printing part at the bottom into its own function, i.e. -main, that way it's properly prepared for being a reusable file.

(= (mod n coin) 0) is potentially a bit easier to understand by following this SO answer and using a separate function, i.e. divisible-by?.

Also, transforming the reduce into an explicit loop gives a bit more speed, e.g.:

(def get-ways
  (memoize
   (fn
     [n coins]
     (cond
       (= n 0) 1
       (= (count coins) 0) 0
       true (let [[coin & other-coins] coins
                  max (int (Math/ceil (/ n coin)))]
              (loop [i 0
                     sum (if (divisible-by? n coin) 1 0)]
                (if (>= i max)
                  sum
                  (recur (inc i) (+ sum (get-ways (- n (* coin i)) other-coins))))))))))

I imagine that not entering the first two cases into the map that memoize maintains might be nice too.

Apart from that, well you could obviously maintain the saved states in a dictionary yourself, but I'm not quite sure what benefit that'd give you. Maybe resetting would be easier, but it doesn't sound that necessary to be honest.