The "Potter" Coding Dojo (in Clojure)

If you are considering doing this Coding Dojo yourself, you may want to postpone reading this until you do because it provides not one but two different solutions that passes all the suggested test cases.

(Paraphrased by yours truly; the original is over at codingdojo.)

• There is a bookshop that has only five distinct books; Let's call them 1–5
• The shop has unlimited quantities of each book
• Each book costs £8
• You can get a discount for buying several distinct books as a unit
• There is no discount for buying two (or more) copies of the same book as a unit
• A purchase can contain multiple units, thus you can get multiple discounts for a single purchase

These are the discounts:

Your mission: write a function to calculate the price of a purchase, such that the customer always pays the minimum available price.

Example: Buying the books 1, 2 & 3 can be put through the till in several different ways:

In this case, your function should pick option #3 as it is the cheapest.

I immediately thought that this was a combinatorial problem and scoured Clojure's collections library for suitable combinatorial operators. I didn't find what I wanted in the standard library, but clojure.math.combinatorics appeared to have what I needed.

clojure.math.combinatorics/partitions return all the different ways to partition the input into subsets, which sounds like it might work. I felt I was ready to start coding.

Let's start easy, with an import statement for clojure.math.combinatorics, a def for our book price, and a map of available discounts:

(ns potter.core
  (:require [clojure.math.combinatorics :as combo]))

(def book-price 8)

(def discount {2 0.95
               3 0.9
               4 0.8
               5 0.75})

Then let's try to price a single partition. Because combo/partitions returns all possible partitions, some have the same book twice in it. This makes no sense with our discount structure. However, we can just price superfluous books as if they were bought on their own, and the price attempts should be discarded by more optimal sets of partitions.

(defn price-partition
  [books]
  (let [unique (count (distinct books))
        mult (or (discount unique) 1)]
    (* book-price
       (+ (* unique mult)
          (* (- (count books) unique))))))

We're ready to price a sequence of partitions, each with their own discount applied, to make up a whole purchase.

(defn price-partition-seq
  [partitions]
  (->> partitions
       (map price-partition)
       (reduce +)))

Now, all we need to do is make our top-level price function that takes our input and returns the best price we can give. It is a brute force solution that takes the input and first calculates all possible ways to partition that into subsets, then calculates the price for each of those subsets, sorts the list of prices and grabs the lowest one. Simples!

(defn price
  [books]
  (->> books
       combo/partitions
       (map price-partition-seq)
       sort
       first))

Looks great! Let's try it out against some of the provided test cases²:

(testing "no discounts"
  (are [total books]
      (= total (price books))
    0 []
    8 [1]
    16 [2 2]
    24 [3 3 3]
    32 [4 4 4 4]
    40 [5 5 5 5 5]))

Alright!

(testing "Simple discounts"
  (are [total books]
      (= total (price books))
    (* 16 95/100) [1 2]
    (* 16 95/100) [1 3]
    (* 16 95/100) [1 4]
    (* 16 95/100) [1 5]
    (* 8 3 9/10) [1 3 5]
    (* 8 4 8/10) [1 2 3 5]
    (* 8 5 75/100) [1 2 3 4 5]))

Winning!

(testing "Multiple discounts"
  (are [total books]
      (= total (price books))
    (+ 8 (* 2 8 95/100)) [1 1 2]
    (* 2 (* 2 8 95/100)) [1 1 2 2]
    (+ (* 8 4 8/10) (* 8 2 95/100)) [1 1 2 3 3 4]
    (+ 8 (* 5 8 75/100)) [1 2 2 3 4 5]))

Still got it!

(testing "Edge cases"
  (are [total books]
      (= total (price books))
    (* 2 (* 8 4 8/10)) [1 1 2 2 3 3 4 5]
    (+ (* 3 (* 8 5 75/100)) (* 2 8 4 8/10)) [1 1 1 1 1
                                             2 2 2 2 2
                                             3 3 3 3
                                             4 4 4 4 4
                                             5 5 5 5]))

BOOOOOO! Failed!

That last edge case has 23 books in it, and finding all the possible partitions is a function whose time consumption grows rapidly with the number of books. For 13 to 15 books the time taken for this function roughly triples for each book added, so 23 books will take rather a long time. Witness:

potter.core> (time
              (count
               (combo/partitions
                [1 1 1
                 2 2 2
                 3 3 3
                 4 4
                 5 5])))
"Elapsed time: 1487.052629 msecs"
;; => 200549

potter.core> (time
              (count
               (combo/partitions
                [1 1 1
                 2 2 2
                 3 3 3
                 4 4 4
                 5 5])))
"Elapsed time: 4089.57496 msecs"
;; => 573003

potter.core> (time
              (count
               (combo/partitions
                [1 1 1
                 2 2 2
                 3 3 3
                 4 4 4
                 5 5 5])))
"Elapsed time: 12744.500346 msecs"
;; => 1688360

It's time to try a different approach.

Although the simple solution works for small numbers of books, it is impractical for larger stacks of books. I felt that it might be possible to break the problem down somewhat, or at least approximate the solution for larger problems. I renamed my price function to best-price and added a new fast-price function³:

(defn fast-price
  [books]
  (loop [counts (->> books frequencies vals sort)
         total 0]
    (if (seq counts)
      (let [c (first counts)
            n (count counts)
            p (* c (price-partition (take n (iterate inc 1))))]
        (recur (->> counts
                    (map #(- % c))
                    (remove zero?))
               (+ total p)))
      total)))

Then it was a case of finding a suitable threshold to switch from one to the other. I checked the wind direction, phases of the moon, read my tea leaves and goat entrails and came up with:

(defn price
  [books]
  (if (< (count books) 10)
    (best-price books)
    (fast-price books)))

Job done! Well, sort-of. This solution is fast and finds a price, but it does not find the best price for the final edge case.

My fast solution eagerly tries to build as big partitions as possible from the remaining books. So if you have the following: 1 1 2 2 3 3 4 5 it will price that as:

$\pounds 8\times 5\times (1-0.25)+\pounds 8\times 3\times (1-0.9)=\pounds 51.60$

However, it's actually cheaper to price that as two partitions of four books:

$2\times \pounds 8\times 4\times (1-0.2)=\pounds 51.20$

After a bit of trial-and-error in the Clojure REPL I felt confident that this was the only such edge case, and decided to just build my solution around that. I deleted most of the code I had, along the way micro-optimised⁴ fast price lookup for a unit of books. This map directly gave the price for a stack of 1-5 unique books, having the discount already added to it.

(def fast-price-lookup
  "Pre-calculated prices (with discount)
  for a stack of up to 5 distinct books."
  {1 book-price
   2 (* 2 book-price 95/100)
   3 (* 3 book-price 9/10)
   4 (* 4 book-price 8/10)
   5 (* 5 book-price 75/100)})

I then did a variety of my previous fast-price function. I separated all the books into piles of distinct books, then built the biggest sets of unique books I could (by taking one from each pile) and priced them as a unit unless I reached a state that I recognised I could more beneficially price as $4+4$ than $5+3$ books. Here's the code for that:

(defn price
  [books]

  ;; Separate the books into piles of
  ;; individual books
  (loop [book-piles (->> books
                         frequencies
                         vals
                         sort)
         total 0]

    ;; Any more piles of books left?
    (if (seq book-piles)

      ;; Do we hit the special case
      ;; where two four-book stacks are
      ;; cheaper than two stacks of
      ;; three and five unique books
      ;; each?
      (if (= '(1 1 2 2 2) book-piles)

        ;; Return current total plus the
        ;; cost of two stacks of four
        ;; unique books.
        (+ total (* 2 (fast-price-lookup 4)))

        ;; Take one book from each
        ;; remaining pile & add the cost
        ;; of this stack of books to the
        ;; running total.
        (recur (->> book-piles
                    (map dec)
                    (remove zero?))
               (+ total
                  (fast-price-lookup
                   (count book-piles)))))

      ;; No more piles of books left;
      ;; return total.
      total)))

There's a lot to like about this. It's dirt simple, and fast. I can price millions of books with this, no problems.

I was very, very pleased with myself until Michelle, a colleague, pointed out that it is highly sensitive to changes in the discount amounts. She even went as far as calling it cheating which made me feel like taking a few deep breaths into a paper bag. But she is right! Change the discount amount given for four books and the pricing function may start to exhibit weird behaviour.

Michelle tried to show me how to solve the problem using Maths but kept on being distracted from reaching a solution by my questions about her notation⁵. We did manage to satisfy ourselves that given a huge amount of books we can break the problem into smaller chunks, of size at most $N\times N$ where $N$ is the biggest number of books we offer a lump discount for. The problem is that in our case $N=5$ and $5\times 5=25$ is more books than we have in the edge case that we already failed to handle.

This was as far as I got at this work trip, but I've been thinking about the problem (too much) since. Is it possible to make a solution that is correct, fast enough to handle all the provided edge cases, and robust against changes in the discounts? It feels like it should be.

I think there will still be a combinatorial element to the solution. My hope is to add some domain-informed restrictions such that we can pass all the suggested test cases in a reasonable time span. I believe it should be possible. I can think of some restrictions:

• Don't generate partitions with more than N items, where N is max number of books we offer a discount for (i.e. 5)
• Don't generate partitions with duplicates

One approach I thought of was to generate a set of different shapes of sets that fit those constraints, and try to fit the books we have into these sets.

If you want to get into more details and play with this code yourself you might find it easier to check out my coding-dojo repo rather than piece it together from this blog post.

I hope I'm done with this problem now. It's been praying on my mind for a month, hence I decided to try "writing it out of my system"—and the result is this article. I hope you're happy, whoever you are who came up with this exercise :-)