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:

$$$$\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}$$$$

#### 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

> argmax_slow(20)

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.