This problem set is due on Wednesday May 13, 2020 at 20:00 Central, to be submitted on Gradescope. Each problem is worth 10 marks in total.
You have been passed a large amount of information about turnip futures (which have recently become much more lucrative than crude oil) for the next $n$ days. The information you have acquired tells you for day $i$ the change in price from day $i-1$. For example,
| Day | 0 | 1 | 2 | 3 | 4 |
|---|---|---|---|---|---|
| Actual price | 98 | 112 | 67 | 84 | 95 |
| Your intelligence | (Today) | 14 | -45 | 17 | 11 |
A basic task in typography (both traditional and digital) is to arrange text so that the ends of lines are aesthetically pleasing, whether the text is justified or ragged. By aesthetically pleasing, we typically mean approximately even (although there is more than that).
Suppose we want to solve this problem for monospaced fonts. We are given, as our text, a list of $n$ words $w_1, \dots, w_n$ and a maximum line width $W$. We can assume that $|w_i| \leq W$ for all $1 \leq i \leq n$. Each word is to be separated by a space and no line may begin with a space. We assume that punctuation is part of the word just before it.
The badness of a text is the sum of the cubes of the number of blanks at the end of each line. More formally, let $|w|$ denote the length of a word. If line $i$ contains words $w_k$ through $w_\ell$, then the number of blanks at the end of line $i$ is \[b_i = W - \left( \sum_{j = k}^{\ell - 1} (|w_j| + 1) + |w_\ell| \right).\] Note that we add 1 for each space except for the final word. Then if there are $L$ lines in total, the badness of the text is \[B = \sum_{i = 1}^{L-1} b_i^3.\] The text with the most "even" formatting is one with line breaks that result in minimal badness. Note that we ignore the last line, because the last line is allowed to be much shorter than the rest of the text (we will ignore this when computing the badness to simplify the problem a bit).
For example, consider the following quote from Robert Bringhurst's The Elements of Typographic Style,
A typewriter that justifies its lines___ in imitation of typesetting is a________ presumptuous, uneducated machine,_______ mimicking the outward form instead of___ the inner truth of typography.__________Here, the extra spaces at the end are represented by underscores. The above text has a line width of 40. The number of blank spaces at the end of each line except for the last are 3, 8, 7, and 3 which gives a total badness of 909.