Skip to content

Instantly share code, notes, and snippets.

@kohyama kohyama/awtp.clj
Last active Oct 19, 2017

Embed
What would you like to do?
お釣りの要らない全ての支払い方
(require '[clojure.test :refer (with-test are run-tests)])
(with-test
(defn awtp [cs a]
((fn f [[h & r] a]
(cond
(zero? a) #{{}}
(nil? h) #{}
:else (set
(mapcat (fn [c]
(map #(if (pos? c) (assoc % h c) %)
(f r (- a (* c h)))))
(range 0 (inc (quot a h)))))))
(sort-by identity > cs) a))
(are [cs a r] (= (awtp cs a) r)
#{1 3} 8 #{{3 2, 1 2} {3 1, 1 5} {1 8}} ; 1円硬貨と3円硬貨があったとすると, 8円の支払いは 3円2枚と1円2枚, 3円1枚と1円5枚, 1円8枚.
#{2 3} 8 #{{3 2, 2 1} {2 4}}
#{5 10} 7 #{}
#{5 10} 23 #{}
#{10 50 100} 130 #{{100 1, 10 3}
{50 2, 10 3}
{50 1, 10 8}
{10 13}}
#{10 50 100} 150 #{{100 1, 50 1}
{100 1, 10 5}
{50 3}
{50 2, 10 5}
{50 1, 10 10}
{10 15}}))
@kohyama

This comment has been minimized.

Copy link
Owner Author

commented Jun 25, 2013

お釣りの要らない全ての支払い方

仕様

貨幣の種類をその金額である正の整数で表すとします.
貨幣の種類の集合 cs と, 金額 a を与えると,
それらの貨幣の種類の集合で可能な, お釣り無く支払える全ての支払い方を返します.
ひとつの支払い方は, 貨幣の種類をキー, その個数を値とするマップで表します.
使わなかった種類の貨幣については, 0枚としてマップに含めるのではなく, マップに含めないものとします.
全ての支払い方は, 支払い方の集合で返します.

(そのうち解説書きます)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.