main page  —  COMP 526 Applied Algorithmics

# Programming Puzzle: Bamboo Trimming

This is an archived version of this module from Spring 2022.

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: You specify a fixed, finite list $C$ of cuts to execute, and when you are done with this list, you simply start from the beginning again, and repeat this process indefinitely.

## Inputs

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

1. Inquality: [98,1,1]
2. Power: [10,10,10,10,50,50,50,50,250,250,250,250,1250,1250,1250,1250,6250,6250,6250,6250]
3. Odds [3,3,3,5,5,7,7,9]
4. Fibonacci: [1,1,2,3,5,8,13,21]
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 Python implementation of the bamboo-trimming problem that you will use to evaluate your trimming schedules:

There is one file bambooX.py 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. 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.py files

1. add your MWS username to variable username, and
2. add your periodic schedule to list queue.

To run the simulation, extract the zip archive to a folder and run, e.g., python3 bambooInequality.py there.

## Deliverables

For how and where to submit, please check Canvas.

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

1. The 5 bamboo plot files (bambooX.py for each X in {Inequality, Power, Odds, Fibonacci, Precision}),
2. the generated file with your results (results.csv) — Make sure you have filled in your MWS (University Managed Windows) 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.

### Marking

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 Ben 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.