I was glancing over one of my old college books; Optimisation from Brinkhuis, page 448. It had a fun problem that got me thinking. This document contains a solution to said problem that can be solved with maths, but is more fun to solve with python.

Party at a Convex Castle

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 5 \times 5 = 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.

As a final conclusion, I would mainly like to point out that associating alcohol to "more fun" is a path to ruin, albeit a fun optimisation problem.

koaning.io

Wine Cellar in a Convex Castle

Party at a Convex Castle

Example

The problem

Python Solution

Math Solution