core.logic make change

make_change.clj

(ns make-change
  (:refer-clojure :exclude [==])
  (:require [clojure.core.logic :refer :all]
            [clojure.core.logic.fd :as fd]))

(def ^:dynamic *coin-set*
  {:penny   1
   :nickel  5
   :dime    10
   :quarter 25})

(def ^:dynamic *quantities* nil)

(defn possible-total-num-coins-interval [coin-set amount]
  (let [[smallest-coin largest-coin]  (apply (juxt min max) (vals coin-set))]
    (mapv #(long (Math/ceil (/ (double amount) %)))
          [largest-coin smallest-coin])))

(defn sum° [l summ]
  (matcha [l]
    ([[]]
     (== summ 0))

    ([[?x]]
     (== summ ?x))

    ([[?head . ?more]]
     (fresh [sum-more]
       (fd/+ ?head sum-more summ)
       (sum° ?more sum-more)))))

(defn make-change* [amount]
  (let [coin-set  *coin-set*
        coins     (vec (for [[coin-name value] coin-set
                             :let              [quantity (when *quantities*
                                                           (get *quantities* coin-name 0))]
                             :when             (<= value amount)]
                         {:name  coin-name
                          :value value
                          :n     (lvar)
                          :total (lvar)
                          :max-n ((fnil min Integer/MAX_VALUE) quantity (long (/ amount value)))}))
        num-coins (lvar)]
    (run 1 [q]
      (== q {:num-coins num-coins, :coins coins})
      (fd/in num-coins (apply fd/interval (possible-total-num-coins-interval coin-set amount)))
      (everyg
       (fn [{:keys [value n total max-n], :as coin}]
         (all
          (fd/in n (fd/interval 0 max-n))
          (fd/* value n total)))
       coins)
      (sum° (mapv :n coins) num-coins)
      (sum° (mapv :total coins) amount))))

(defn format-solution [{:keys [num-coins coins]}]
  (into (array-map :num-coins num-coins) (for [coin  (sort-by (comp - :value) coins)
                                               :when (pos? (:n coin))]
                                           [(:name coin) (:n coin)])))

(defn make-change [amount]
  {:pre [(not (neg? amount))]}
  (let [amount (long (Math/floor (* amount 100)))]
    (when-let [[solution] (not-empty (make-change* amount))]
      (format-solution solution))))

Examples:

(make-change 0.50)
;; => {:num-coins 2, :quarter 2}

(make-change 0.71)
;; => {:num-coins 5, :quarter 2, :dime 2, :penny 1}

;; specify different coin sets
(binding [*coin-set* british-coins]
  (make-change 0.71))
;; => {:num-coins 3, :fifty-p 1, :twenty-p 1, :penny 1}

;; specify the quantity of coins available
(binding [*quantities* {:quarter 2, :dime 100}]
  (make-change 1.0))
;; => {:num-coins 7, :quarter 2, :dime 5}