477 Eric Normand Newsletter

00 Box of chocolates.md

Box of chocolates

You work at a chocolate shop that makes two sizes of chocolates:

• Small (2 grams each)
• Large (5 grams each)

When someone orders a box of chocolates, they order by total mass. It's your job to figure out how to fulfill the order using a combination of small and large chocolates to exactly hit the total mass ordered.

Your task is to write a function that takes three arguments:

1. smalls - The number of small chocolates available in the inventory.
2. larges - The number of large chocolates available in the inventory.
3. mass - The total mass of the ordered box.

Your function should return a map containing:

{:small ;; the number of small chocolates
 :large ;; the number of large chocolates
}

Or nil if the total mass is not possible.

One other constraint is you should strive to have the fewest number of chocolates that total to the target mass. That means you should prefer large chocolates over small chocolates if you have the choice.

Examples

(assemble 100 100 2) ;=> {:small 1 :large 0}
(assemble 100 100 1) ;=> nil
(assemble 100 100 10) ;=> {:small 0 :large 2}
(assemble 10 2 20) ;=> {:large 2 :small 5}

Thanks to this site for the problem idea, where it is rated Expert in Ruby. The problem has been modified.

Please submit your solutions as comments on this gist.

To subscribe: https://ericnormand.me/newsletter

Seeing that a more mathematical solution is not there, allow me to submit one:

(ns chocolates
  (:require [clojure.test :refer [deftest is testing]]))

;;; Looks like the backpack problem, but it is actually much easier
;;; Solving this with a bit of math
;;; We must always use the maximal amount of large boxes
;;; Then, look at the remainder to fulfill with small boxes:
;;;  - if even, easy-peasy, it is is the form `2*k` and `k` is the number of small boxes
;;;  - if odd, it is in the form `2*k + 1` and an existing large box is also `2*2 + 1`
;;;    So `k + 2 + 1` is the number of small boxes: `k` for the remainder, `2 + 1` when
;;;    decomposing the large box and using the `+1` of both sides

(defn assemble
  [{:keys [small large mass]}]
  ; dealing with edge cases
  (case mass
    1 nil
    3 nil
    (let [ls (min (quot mass 5) large)
          remaining (- mass (* 5 ls))
          ss (+ (quot remaining 2)
                (if (odd? remaining) 3 0))]
      (when (<= ss small)
        {:large (if (odd? remaining) (dec ls) ls)
         :small ss}))))

(deftest test-assemble
  (testing "edge cases"
    (is (nil? (assemble {:mass 1})))
    (is (nil? (assemble {:mass 3}))))

  (testing "easy cases"
    (is (= {:large 2 :small 2}
           (assemble {:large 5 :small 5 :mass 14})))
    (is (= {:large 5 :small 1}
           (assemble {:large 5 :small 4 :mass 27}))))

  (testing "shortage of larges"
    (is (= {:large 4 :small 5}
           (assemble {:large 4 :small 10 :mass 30}))))

  (testing "backtracking"
    (is (= {:large 2 :small 4}
           (assemble {:large 10 :small 10 :mass 18}))))

  (testing "shortage of small"
    (is (nil? (assemble {:large 3 :small 3 :mass 18})))))