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.