koaning.io: Wine Cellar Strategies

I was glancing over one of my old college books; Optimisation from Brinkhuis, page 448. It had a fun problem that got me thinking.

Story of a Wine Cellar

There’s a long summer party happening at a convex shaped castle. The main attraction of the party is a wine cellar that contains many bottles of wine, \(n\) in fact. Every night the attendees of the party can drink a bottle of wine, causing a party vibe. The attendees wonder, should all the wine be drunk on a single night or should the wine be spread out?

Let’s assume that the partyvibe can be quantified. The total party vibe is a product of the number of bottles of wine drunk per evening.

Example

Suppose that we have 20 bottles of wine. Then these allocations would have the following values:

\[ \begin{equation} \label{eq1} \begin{split} \text{score}(\{10, 10\}) & = 10 \times 10 = 100 \\\\ \text{score}(\{4, 6, 10\}) & = 10 \times 6 \times 4 = 240 \\\\ \text{score}(\{10, 5, 5\}) & = 10 \times 5 \times 5 = 250 \end{split} \end{equation} \]

The problem

What is the optimal allocation? How many bottles should be opened on every evening? Assume that we only have \(n\) bottles to start with.

Python Solution

This problem, turns out, can be solved with a bit of recursion via dynamic programming. The main thing to recognize is the recursive relationship. In maths; I have a function \(s(n,b)\) that I want to optimise where \(n\) is the number of bottles that are currently in the cellar and \(b\) is the number of bottles that is being taken for this night. On considering the problem, maths look like this:

\[ \arg \max_b s(n, b) = b \times \arg \max_{b'} s(n-b, b')\]

Writing this in python turns out to be relatively simple, but it took me 10 minutes on paper to get it right.


from functools import reduce

def argmax_slow(bottles):
    if bottles == 0:
        return [1]
    if bottles <= 3:
        return [bottles]
    else:
        max_score, max_args = 0, []
        for b in range(1, bottles + 1):
            b_args = argmax(bottles - b)
            b_value = reduce(lambda x,y: x * y, [b] + b_args)
            if b_value > max_score: 
                max_score, max_args = b_value, [b] + b_args
        return max_args

Since the function is recursive, one would be wise to add a cache in order to memoize intermediate results.


from functools import lru_cache

@lru_cache(maxsize=512)
def argmax(bottles):
    if bottles == 0:
        return [1]
    if bottles <= 3:
        return [bottles]
    else:
        max_score, max_args = 0, []
        for b in range(1, bottles + 1):
            b_args = argmax(bottles - b)
            b_value = reduce(lambda x,y: x * y, [b] + b_args)
            if b_value > max_score: 
                max_score, max_args = b_value, [b] + b_args
        return max_args

The timing from jupyter lab shows the speedup is definately measureable.


> %time _ = argmax(512)
CPU times: user 4 µs, sys: 1 µs, total: 5 µs
Wall time: 6.2 µs
> %time _ = argmax_slow(512)
CPU times: user 14.8 ms, sys: 1.07 ms, total: 15.9 ms
Wall time: 15 ms

Math Solution

The interesting thing about this problem really shows itself when you see a solution.


> argmax_slow(20)
[2, 3, 3, 3, 3, 3, 3]

Maybe we didn’t need any programming here. Let’s consider some parts of the problem:

You never want to open just one bottle. Instead of opening lots of bottles in one evening, it seems a better tactic to open bottles on many evenings. Why so many threes though?

It might not seem straightforward, but it’s because \(2^3 < 3^2\). Spending two nights with three bottles is “more better” in this example than spending three nights with two.

Final Remark

As a final remark, I really would like to point out that associating alcohol to “more fun” is an obvious path to ruin although the strategy of spreading the drinks such that you never consume more than three a night seems like sound advice.