Created
March 17, 2014 17:13
-
-
Save oliyh/9603796 to your computer and use it in GitHub Desktop.
You are in a shop and have 10p. The following items are for sale: Muffin - 5p Milkshake - 3p Chocolate - 2p Gingerbread man - 1p You need to spend ALL your money. What combinations of items can you buy such that you spend all 10p?
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(def prices {:muffin 5 :milkshake 3 :chocolate 2 :gingerbread 1}) | |
(clojure.pprint/pprint (shop 10 prices)) | |
({:muffin 0, :chocolate 0, :milkshake 0, :gingerbread 10} | |
{:muffin 0, :chocolate 0, :milkshake 1, :gingerbread 7} | |
{:muffin 0, :chocolate 0, :milkshake 2, :gingerbread 4} | |
{:muffin 0, :chocolate 0, :milkshake 3, :gingerbread 1} | |
{:muffin 0, :chocolate 1, :milkshake 0, :gingerbread 8} | |
{:muffin 0, :chocolate 1, :milkshake 1, :gingerbread 5} | |
{:muffin 0, :chocolate 1, :milkshake 2, :gingerbread 2} | |
{:muffin 0, :chocolate 2, :milkshake 0, :gingerbread 6} | |
{:muffin 0, :chocolate 2, :milkshake 1, :gingerbread 3} | |
{:muffin 0, :chocolate 2, :milkshake 2, :gingerbread 0} | |
{:muffin 0, :chocolate 3, :milkshake 0, :gingerbread 4} | |
{:muffin 0, :chocolate 3, :milkshake 1, :gingerbread 1} | |
{:muffin 0, :chocolate 4, :milkshake 0, :gingerbread 2} | |
{:muffin 0, :chocolate 5, :milkshake 0, :gingerbread 0} | |
{:muffin 1, :chocolate 0, :milkshake 0, :gingerbread 5} | |
{:muffin 1, :chocolate 0, :milkshake 1, :gingerbread 2} | |
{:muffin 1, :chocolate 1, :milkshake 0, :gingerbread 3} | |
{:muffin 1, :chocolate 1, :milkshake 1, :gingerbread 0} | |
{:muffin 1, :chocolate 2, :milkshake 0, :gingerbread 1} | |
{:muffin 2, :chocolate 0, :milkshake 0, :gingerbread 0}) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
(defn basket-total [bskt] (reduce (fn [total [product qty]] (+ total (* (prices product) qty))) 0 bskt)) | |
;; binary-like count with n 'bits' which can have values between from and to | |
;; e.g. (permutations 3 0 3) -> ([0 0] [0 1] [0 2] [1 0] [1 1] [1 2] [2 0] [2 1] [2 2]) | |
(defn permutations [n from to] | |
(let [symbols (into [] (take n (repeatedly gensym))) | |
ranges (take n (repeatedly #(into [] (range from to)))) | |
bindings (into [] (interleave symbols ranges))] | |
(eval `(for ~bindings ~symbols)))) | |
(defn shop | |
"Given a certain amount of money, how many permutations of item can you buy?" | |
[money prices] | |
(filter #(= money (basket-total %)) | |
(map (fn [trial] (apply hash-map (interleave (keys prices) trial))) | |
(permutations (count prices) 0 (inc (int (/ money (first (vals (sort-by second prices)))))))))) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment