Sweet Packs | Puzzles for Programmers and Pros

A certain gourmet donut store prides itself on being able to provide its customers with any number of donuts between 1 and 160. A customer may go to the counter and say “I want 43 donuts” and 43 donuts will appear.

Warm-Up

The restaurant wants to package their donuts in four different sizes. Your job is to figure out what those sizes should be in order to minimize the number of packets needed to fill the average order. For starters, assume that any order between 1 and 160 is equally likely.

For example, suppose the packet sizes are 1, 5, 10, and 20. If a customer orders 48 donuts, then the number of packets required is six: two packets of 20, one of 5, and three of 1.

My recommended strategy is to try all possible different combinations of four sizes and find the best. A few observations make this fast. First, one of the sizes is constrained to be 1, so really you have to test ascending triplets of sizes between 2 and 160 only. When evaluating a triplet, include a packet of size 1, calculate the average cost, and simply keep the best.

The inner loop of this process is “calculate the average cost.” That is, given a set of four packet sizes, compute the average number of packets needed for each order. Dynamic programming works really well for this purpose. See if you can figure out how.

Solution to Warm-Up

Here is high-level pseudo-code of one dynamic programming method.

Goal: Given four sizes 1, s1, s2, and s3, find the cost per order.

Create an array of size 160. This will be your cost array.

Initialize each entry to have infinite cost except for the entries at locations 1, s1, s2, and s3 to which you assign a cost of 1.

 for entry i = 2 to 160   if cost(i) == infinite      for entry j from 1 to i-1        if (cost(j) + cost(i-j)) < cost(i)             cost(i) := (cost(j) + cost(i-j))        end if      end for   end if end for

Sum all the costs and divide by 160 to get the average cost.

This technique takes quadratic time in the maximum number of donuts, but this is fast enough for our purposes. Without using dynamic programming, one would have to work much harder.

Now that you see how to evaluate a given candidate set of packet sizes, it remains only to go through the different packet size triplet possibilities to find the best set of packet sizes.

Assuming orders for any number of donuts are equally likely, which set of packet sizes results in the minimum average number of packets required per order? What is that minimum average?
Assume that orders for any number of donuts under 50 are equally likely and are five times as likely as those over 50. So, for example, an order for 14 donuts is five times as likely as an order for 53 donuts, whereas it is equally likely to an order for 47 donuts. Which set of packet sizes gives the minimum average number of packets required per order in this case? What is that minimum average?

Solution to Sweet Packs

Assuming orders for any number of donuts are equally likely, which set of packet sizes gives the minimum average number of packets required per order? What is that minimum average?

The dynamic program given as part of the problem statement is the inner loop. The outer loop generates triplets, and then evaluates them. There are 4,019,679 triplets in all, but only 657,359 that are ascending. For each one, we evaluate the cost and try to find the minimum. This is admittedly not very cheap, but takes only a few minutes. The best set of packet sizes I could find was 1, 6, 29, and 37 having an average cost of 4.7 packets per request.

Assume that orders for any number of donuts under 50 are equally likely and are five times as likely as those over 50. So, for example, an order for 14 donuts is five times as likely as an order for 53 donuts, whereas it is equally likely to an order for 47 donuts. Which set of packet sizes gives the minimum average number of packets required per order in this case? What is that minimum average?

The same dynamic programming approach works, but the cost function has to change somewhat to reflect the change in likelihood. The way I did that was to multiply the cost of orders between 1 and 50 by five. To get the best average, divide the total cost by 360 (160 + (4 × 50)). Otherwise, nothing changes in the process. The best packet sizes are 1, 5, 12, and 32 and the average (weighted by likelihood) required number of packets is just under 4.