I recently completed the Book Store exercise on Exercism. It is a copy of the Potter Kata from Coding Dojo.
The basic premise is that a bookstore wants to promote sales of a particular book series. They offer progressively higher discounts on the purchase of multiple books. The catch is that you have to buy different books from the series to get the discounts.
There are five books in the series, and the discounts are as follows:
- One book is full price, $8, as are multiple copies of the same book.
- Two different books will be discounted by 5% each.
- Three different books are discounted 10% each.
- Four different books are discounted 20% each.
- Five books (a complete set) are discounted by 25% each.
The store wants to be able to group any given basket of books to provide the greatest discount. You may note that a basket of one copy of the entire series, plus three more titles, (that is, five books, plus three books) will have a lower price if treated as two groups of four, rather than a group of five and a group of three.
tl;dr
- What type of problem is this? Is it an assignment problem? A variation of the knapsack problem?
- Is there a general solution that, given a discount scheme, will identify all of the pricing "anomalies," such as the one above?
- I don't need an answer so much as a pointer in the right direction for inquiry and analysis.
What I Did
I wanted to create a solution that did not rely on brute force to examine every possible configuration of a basket, or simply hardcode the correction from 5/3 groupings to 4/4. I came up something that works with this discount scheme and some more contrived schemes, but I am certain it is not generally correct.
The pricing anomaly in this problem occurs because the discount increases by 10% from the third book to the fourth book, rather than 5% as with all of the other jumps. If all of the jumps were the same, it would always be best to take the largest possible grouping. Interestingly, if the disproportionate jump took place on the third book (say, a 15% discount instead of 10%), then I do not believe any anomalies would be created, and it would still be optimal to always take the largest available grouping. In the alternative, if you contrive the discount scheme as two for 5% off, three for 23% off, four for 24% off, and five for 25% off, then a number of anomalies will be created (at least five) and must be accounted for. For example, a basket of 5/5/2 books would be cheaper if charged as 3/3/3/3, and cheaper still if charged as 4/4/4, while a basket of 5/5/5/1 books would be cheaper at 4/4/4/4, but cheaper still at 5/5/3/3.
My (incorrect) Approach
My current solution looks for anomaly candidates by analyzing the rate of increase in each discount from the base price for a single book as follows:
| set | discount | discount / (set - 1) |
|---|---|---|
| 1 | 0.00 | N/A |
| 2 | 0.05 | 0.05 |
| 3 | 0.10 | 0.05 |
| 4 | 0.20 | 0.667 |
| 5 | 0.25 | 0.625 |
I believe that if the third column either stayed the same or increased with each step, then the "greedy" solution of always taking the largest possible grouping would always be optimal. However, since the factor for four books is larger than the factor for five books, then there may be situations where groups of four might be cheaper than groups of five and a smaller group.
Next, I take all of the anomaly candidates and search for situations where multiple groups of the candidate (e.g., 4/4, 4/4/4, etc.) would be preferable to the default, largest first approach (5/3, in this case).
I do not think my approach is correct or efficient. How can I approach this problem more rigorously?
(Also, please suggest better tags to improve the visibility of this question. Thank you!)