How to translate this algorithm from Ruby to Clojure?

I've been solving a programming task in Ruby and after completing it I thought I should try applying my limited knowledge of Clojure to implement the same thing. I spent quite a bit of time but didn't manage to get it working.

The task is: We have array of coin types and expected sum. What is the best way to represent that sum with coin types that we have available spending minimum number of coins. So for representing 325 with coin types [100, 50, 20, 10, 5] we would produce the following result: [100, 100, 100, 20, 5].

Here is my Ruby code that seems to be working:

  def calc(coin_types, expected)
    calc_iter(coin_types.sort.reverse, expected, [])
  end

  def calc_iter(coin_types, expected, coins)
    sum = coins.sum

    return coins if sum == expected
    return nil if sum > expected

    coin_types.each do |type|
      result = calc_iter(coin_types, expected, coins + [type])
      return result if result
    end

    nil
  end

  # test
  calc([25, 10], 65) # should return [25, 10, 10, 10, 10]

And now two of my failed Clojure implementations:

1) (it takes forever to run so i had to kill it):

  (defn calc [types expected]
    (let [types (reverse (sort types))]
      (loop [coins []]
        (let [sum (count coins)]
          (if (= sum expected)
            coins
            (if (> sum expected)
              nil
              (first (filter #(not (nil? %))
                             (map #(recur (cons % coins))
                                  types)))))))))

2) (this one does finish in reasonable amount of times but returns wrong result):

  (defn calc-iter [types expected coins]
    (let [sum (count coins)]
      (if (= sum expected)
        coins
        (if (> sum expected)
          nil
          (first (filter #(not (nil? %))
                         (map #(calc-iter types
                                          expected
                                          (cons % coins))
                              types)))))))

  (defn calc [types expected]
    (calc-iter (reverse (sort types))
               expected
               []))

Solution

Here is a simple example:

(def coin-values [100, 50, 20, 10, 5])

(defn coins-for-amount [amount]
  (loop [amount-remaining amount
         coins-avail      coin-values
         coins-used       []]
    (cond
      (zero? amount-remaining) coins-used ; success
      (empty? coins-avail) nil ; ran out of coin types w/o finding answer
      :else (let [coin-val              (first coins-avail)
                  num-coins             (quot amount-remaining coin-val)
                  curr-amount           (* coin-val num-coins)
                  amount-remaining-next (- amount-remaining curr-amount)
                  coins-avail-next      (rest coins-avail)
                  coins-used-next       (conj coins-used num-coins)]
              (recur amount-remaining-next coins-avail-next coins-used-next)))))


(coins-for-amount 325) => [3 0 1 0 1]
(coins-for-amount 326) => nil
(coins-for-amount 360) => [3 1 0 1]

Note that in the current form it doesn't accumulate trailing zeros.

Update

In my original answer above, I never considered that tricky coin values like [25 10] might be chosen, so you would need 1 quarter and 4 dimes to reach a total of $0.65. The above algorithm would have chosen 2 quarters and then been stuck with $0.15 remaining and only dimes available.

If tricky coin values are allowed, you need to use an exhaustive search algorithm. Here is one version in Clojure:

(ns tst.demo.core
  (:use tupelo.core demo.core tupelo.test))

(defn total-amount [coins-used]
  (let [amounts (mapv (fn [[coin-value num-coins]] (* coin-value num-coins))
                  coins-used)
        total   (reduce + amounts)]
    total))

(defn coins-for-amount-impl
  [coins-used coin-values amount-remaining]
  (when-not (empty? coin-values)
    (let [curr-coin-value       (first coin-values)
          coin-values-remaining (rest coin-values)
          max-coins             (quot amount-remaining curr-coin-value)]
      (vec (for [curr-num-coins (range (inc max-coins))]
             (let [coins-used-new       (conj coins-used {curr-coin-value curr-num-coins})
                   amount-remaining-new (- amount-remaining (* curr-coin-value curr-num-coins))]
               (if (zero? amount-remaining-new)
                 coins-used-new
                 (coins-for-amount-impl
                   coins-used-new coin-values-remaining amount-remaining-new))))))))

(defn coins-for-amount [coin-values amount]
  (remove nil?
    (flatten
      (coins-for-amount-impl {} coin-values amount))))

And some short unit tests:

(dotest
  (is= 48 (total-amount {25 1    ; quarter
                         10 2    ; dime
                         1  3})) ; penny


  (let [results (coins-for-amount [10 5 1], 17)]
    (is= results
      [{10 0, 5 0, 1 17}
       {10 0, 5 1, 1 12}
       {10 0, 5 2, 1 7}
       {10 0, 5 3, 1 2}
       {10 1, 5 0, 1 7}
       {10 1, 5 1, 1 2}]))

  (is= (coins-for-amount [25 10], 65)
    [{25 1, 10 4}] ))

So it finds all possible combinations that reach the correct total. Counting the coins and finding the solution with the fewest coins (don't forget about ties!) is left as an exercise for the reader. ;)