Programming Puzzle: Bamboo Trimming

This is an archived version of this module from Spring 2020.
Click here for the current iteration.

This continuous-assessment exercise consists of a small applied project with algorithmic and programming components, including a real-time leaderboard of the competition.

Will you be able to beat your classmates, or even your demonstrator?

You will be working on a real, challenging research problem, so the intention is as much on the process of producing solutions to algorithmic problems, as on the actual deliverable.

The Bamboo Trimming Problem

To offset the long hours of sitting in classes, you are a passionate gardener, and your pride and joy is your little forest of exotic bamboos. However, being one of the fastest-growing plants on earth, the bamboo plot requires constant attention. In an attempt to keep the effort manageable, you decide to cut down exactly one of your the bamboo plants each day, and you cut it right back to the roots.

Since your bamboos have vastly different growth rates, some of them need more frequent cutting than others. You set out to find a periodic schedule of which bamboo to cut each day, so as to minimize the maximal height of your garden.

Formalization

You decide to mathematically model the task as follows. Given $n$ bamboos with daily growth rates $g_1,\ldots,g_n$, we assume that after growing for $t$ days (without cutting), bamboo $i$ will have height $t\cdot g_i$. Right after you cut a bamboo, its height is 0, and so is the initial height of all bamboos at the beginning.

Writing $h_i(t)$ for the height of bamboo $i$ after $t$ days, and $c(t)$ the bamboo that you cut on day $t$, we obtain:

\[h_1(0) = h_2(0) = \cdots = h_n(0) = 0;\] \[h_i(t+1) = \begin{cases} g_i & \text{if } c(t) = i \\ h_i(t) + g_i & \text{otherwise} \end{cases}\qquad (t\ge 0).\]

The task is to find an infinite schedule of cuts $c : \mathbb N_0 \to [n]$ that keeps the maximal height $\sup_{t\in\mathbb N} \max_{i\in[n]} h_i(t)$ as low as possible.

To simplify your planning, you decide to restrict your attention to periodic schedules, i.e., a fixed, finite list $C$ of cuts that follow, and when you are done, you simply start from the beginning again.

Inputs

Your garden contains five named bamboo plots with the growth rates of the bamboos given below:

1. Unequal Pair: [1,199]
2. Fibonacci: [1,1,2,3,5,8,13,21]
3. Odds [3,3,3,5,5,7,7,9]
4. Powers3 [3,6,12,24,48,96,192,386]
5. Precision [2000,3999,4001]

Design as good a periodic schedule as you can find for each of them!

Can you argue that your solutions are best possible?

Code template

We prepared a Java implementation of the bamboo-trimming problem that you will use to evaluate your trimming schedules:

• Java sources

There is one main class BambooX for each value of X in the list above. They simulate the growth of the bamboo under your periodic schedule and report the maximum height ever reached, divided by the sum of all growth rates. The classes automatically store your results in a csv file.

Obey the comments! Once you downloaded the code, please in each of the 5 BambooX classes

1. add your vital username in the appropriate variable,
2. add your periodic schedule.

To compile the simulation, extract the zip archive to a folder and run javac *java there. To run a simulation, use, e.g, java BambooUnequalPair.

Deliverables

Submissions are due 23 March on SAM.

This is an individual project; each student has to submit his or her own solution comprising the following:

1. The 5 bamboo plot classes (BambooX.java for each X in {UnequalPair, Fibonacci, Odds, Powers3, Precision}),
2. the generated file with your results (results.csv) — Make sure you have filled in your vital username!
3. A document describing how you arrived at the solution (not more than two pages). Report also on dead ends you tried (what did not work), as well as on arguments why a solution better than a certain height is not possible.

Grading

The overall mark will consist of a weighted average.

• 40% for the description.
• 60% for the quality of the achieved solutions. The baseline are solutions that George has found; in principle you could get more than 100% for this subtask if you manage to beat his solutions!

Collaboration

This programming puzzle is mainly an individual project, and you have to submit you own solution. In particular, the description of your solution must be a single-author document.

Collaboration in small groups (not more than five students) on the conceptual level(discussing ideas, not sharing entire solutions) are accepted, but they must be declared in the description document, including proper mention of others’ contributions.

Leaderboard

We run a (voluntary, anonymous) leaderboard of the current best solution. Whenever you have a periodic schedule tried in the simulator, use the below form to share your achievements with the rest of the class!

Highscores

The plots below show all answers over time. Recall that lower is better.

New submissions are immediately added at the right end, but might take a few seconds and refreshing before they show up.