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

(defn- fill [pieces piece-size mass]
  (let [pieces (-> mass (quot piece-size) (min pieces))]
    {:mass (- mass (* pieces piece-size))
     :pieces pieces}))

(defn assemble [small large mass]
  (let [{mass :mass large :pieces} (fill large 5 mass)
        {mass :mass small :pieces} (fill small 2 mass)]
    (when (zero? mass)
      {:small small
       :large large})))

(defn assemble [smalls larges mass]
  (loop [larges (min (int (/ mass 5)) larges)]
    (let [remaining (- mass (* 5 larges))
          n-smalls (min smalls (int (/ remaining 2)))
          n-mass (+ (* 5 larges) (* 2 n-smalls))]
      (if (= mass n-mass)
        {:small n-smalls
         :large larges}
        (when (< 0 larges)
          (recur (dec larges)))))))

(defn- fill [pieces piece-size mass]
  (let [pieces (-> mass (quot piece-size) (min pieces))]
    {:mass (- mass (* pieces piece-size))
     :pieces pieces}))

(defn assemble [small large mass]
  (let [{mass :mass large :pieces} (fill large 5 mass)
        {mass :mass small :pieces} (fill small 2 mass)]
    (when (zero? mass)
      {:small small
       :large large})))

This would fail to find a solution when mass is 18

@rmfbarker you are right, I've adopted your approach of recuring with fewer larges

(defn- fill [pieces piece-size mass]
  (let [pieces (-> mass (quot piece-size) (min pieces))]
    {:mass (- mass (* pieces piece-size))
     :pieces pieces}))

(defn assemble [small large mass]
  (let [{mass-left :mass large-filled :pieces} (fill large 5 mass)
        {mass-left :mass small-filled :pieces} (fill small 2 mass-left)]
    (cond
      (zero? mass-left)
      {:small small-filled
       :large large-filled}

      (< 0 large-filled)
      (recur small (dec large-filled) mass))))

(require '[clojure.test :as t])

(t/deftest assemble-test
  (t/is (= {:small 1 :large 0} (assemble 100 100 2)))
  (t/is (nil?                  (assemble 100 100 1)))
  (t/is (= {:small 0 :large 2} (assemble 100 100 10)))
  (t/is (= {:small 5 :large 2} (assemble 10 2 20)))
  (t/is (= {:small 4 :large 2} (assemble 100 100 18)))
  (t/is (= {:small 3 :large 0} (assemble 100 100 6))))

(t/run-tests)

aX + bY = c

I remember this very particular problem in math is called "indeterminate equation".

it's so fast to calculate even for large numbers.

Este es un claro ejemplo de algoritmo voraz como el del cambio de las monedas del capítulo 6 del libro "Fundamentos de algoritmia".

(ns assemble)
(require '[clojure.test :as test])

(defn assemble [numero-small numero-large masa]
  (let [masa-small 2
        masa-large 5
        large-teorico (quot masa masa-large)
        large-real (min large-teorico numero-large)
        masa-restante (- masa (* large-real masa-large))
        small-teorico (quot masa-restante masa-small)
        small-real (min small-teorico numero-small)]
    (if (and (= large-real 0)
             (= small-real 0))
      nil
      {:small small-real :large large-real})))

(test/testing "Assemble tests"
              (test/is (= (assemble 100 100 2) {:small 1 :large 0}))
              (test/is (= (assemble 100 100 1) nil))
              (test/is (= (assemble 100 100 10) {:small 0 :large 2}))
              (test/is (= (assemble 10 2 20) {:large 2 :small 5})))

aX + bY = c
@hamidb80 you gave me an idea..

This is perhaps not in keeping with the spirit of the challenge (sorry), but clojure.core.logic is a handy way to solve constraint problems like this, with aX+bY=c being one constraint and the number of small and large chocolates in inventory being the others:

(require '[clojure.core.logic :refer [run*]]
         '[clojure.core.logic.fd :as fd])

(defn getsols-via-constraint [s l m]
  (run* [smalls larges]
    (fd/in smalls (fd/interval 0 s)) ; s smalls available
    (fd/in larges (fd/interval 0 l)) ; l larges available
    (fd/eq (= m (+ (* smalls 2) (* larges 5)))))) ; 2s+5l=m aka aX+bY=c 

(defn assemble [s l m]
  (let [[sm lg] (first (getsols-via-constraint s l m))]
    (if (and sm lg) {:small sm :large lg})))

For some reason I don't understand, the results always return with largest 'large' first, so I didn't even have to sort the list of solutions.

(defn assemble [max-smalls max-larges mass]
  (first (for [small (range (inc max-smalls))
               :let [large-mass (- mass (* 2 small))]
               :while (<= 0 large-mass)
               :let [large (/ large-mass 5)]
               :when (and (int? large) (<= large max-larges))]
           {:small small :large large})))

Update: closed-form solution without iteration:

(defn assemble [max-smalls max-larges mass]
  (let [prelarge (min max-larges (quot mass 5))
        mass (- mass (* 5 prelarge))
        q (mod mass 2)
        small (+ (* 3 q) (quot mass 2))]
    (if (and (<= q prelarge) (<= small max-smalls))
      {:large (- prelarge q) :small small})))

(defonce small 2)
(defonce large 5)

(defn assemble
  "Assemble MASS grams of chocolates given the availability of SMALLS and LARGES numbers of small
   and large chocolates."
  [smalls larges mass]
  (let [all-boxes (for [s     (range (inc smalls))
                        l     (range (inc larges))
                        :when (= mass (+ (* s small) (* l large)))]
                    {:small s
                     :large l})]
    (when (seq all-boxes)
      (first (sort-by #(+ (:small %) (:large %)) all-boxes)))))

After my brain hurt using mods and quots in which @jonasseglare did succeed, like @mchampine I used core.logic.

(require
 '[clojure.core.logic :refer [run* fresh] :as logic]
 '[clojure.core.logic.fd :as fd])

(defn assemble [smalls larges mass]
  (some->>
   (run* [s l]
     (fd/in s (fd/interval 0 smalls))
     (fd/in l (fd/interval 0 larges))
     (fd/eq (= (+ (* s 2) (* l 5)) mass)))
   first
   (zipmap [:small :large])))

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

@mchampine I noticed that when the variables are swapped (run* [l s]), the smallest 'large' is returned first. The logic engine probably starts searching for answers with the first variable bound to the minimum value in the domain. In the case of small first this leads to finding the most larges and thus fewest number of chocolates

This looks like a variant of the Bounded Knapsack problem. Here is my adaptation of the Knapsack-01 recursive definition, which can be used by 'unrolling' the number of chocolates.

Problems that can be defined recursively like this one make Clojure's memoization truly shine, there is almost no thinking required beyond the recursive definition. Compare this to sweating out the dynamic programming details (and in-place updates!) of arrays and such.

(def knapsack01-sel
 (memoize (fn [i w [vfn wfn :as fs] sel]
            (let [vi (vfn i)
                  wi (wfn i)]
              (cond
                (= 0 i)
                [0 #{}]
                (< w wi)
                (knapsack01-sel (dec i) w fs sel)
                :else
                (max-key first
                         (knapsack01-sel (dec i) w fs sel)
                         (-> (knapsack01-sel (dec i) (- w wi) fs sel)
                             ((fn [[value sel]]
                                [(+ value vi) (conj sel i)])))))))))

(defn config [sk lk]
 (let [mid (inc lk)
       lidxs (range 1 mid)
       sidxs (range mid (+ mid sk))
       ;; assign arbitrary values, prefer large chcolates by a factor of 10
       vfn (fn [i] (cond (zero? i) 0
                         (< i mid) 10
                         (< i (+ mid sk)) 1))
       wfn (fn [i] (cond (zero? i) 0
                         (< i mid) 5
                         (< i (+ mid sk)) 2))]
   [vfn wfn mid]))

(defn fmt [ids mid]
 (->> ids sort
      (split-with #(< % mid)) 
      (map count)
      ((fn [[lk sk]] {:large lk :small sk} ))))

(defn assemble [skount lkount total]
 (let [[vfn wfn mid] (config skount lkount)
       [_ ids](knapsack01-sel (+ skount lkount) 
                         total
                         [vfn wfn]
                         #{})]
   (when (= total
           (->> ids (map wfn) (apply +)))
     (fmt ids mid))))

(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}

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})))))