Programming Puzzle: Panda Feeding Problem

This continuous-assessment exercise consists of a small applied project with algorithmic and programming components.

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

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

The Panda Feeding Problem 🐼

As a committed supporter of your small local zoo, which among other animals boasts a Giant Panda called Pam, you took on the task of providing for the food for Pam. Since you are also a passionate gardener, you are growing your own little forest of exotic bamboos. Luckily one of the fastest-growing plants on earth, and thanks to the wet British climate growing constantly, the bamboo plot provides reliable food. However, Pam is a fussy eater and refuses to eat more than one (hopefully long!) stick of bamboo. In an attempt to keep Pam happy, you thus decide to each day cut down exactly one of your bamboo plants, and you cut it right back to its roots.

Since your bamboos have vastly different growth rates, some of them can be harvested more frequent than others. But it is important that Pam receives food reliably. You set out to find a periodic schedule of which bamboo to cut each day, so as to maximize the minimal length Pam ever gets. (That some sticks are longer on other days does not help poor Pam if there is one day where she cannot a proper meal.)

Formalization

You decide to mathematically model the task as follows. Given $k$ bamboos with daily growth rates $g_1,\ldots,g_k$, 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. To avoid effects of an initial period, the initial height of all bamboos at the beginning is set to $\infty$. (This just corresponds to letting your garden grow for a long while before you start any harvest, and does not affect the stable-state harvest.)

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:

The task is to find an infinite schedule of cuts $c : \mathbb N_0 \to [k]$ that achieves a guarantee for the daily harvest, $\inf_{t\in\mathbb N} h_{c(t)}(t)$, as high as possible.

To simplify your planning, you decide to restrict your attention to periodic schedules: You specify a fixed, finite list $C = C[0..m)$ of cuts to execute, and when you are done with this list, you simply start from the beginning again, and repeat this process indefinitely: $c(t) = C[t \bmod m]$.

Inputs

Your task is to create a schedule for the following possible named bamboo plots with the growth rates of the bamboos as given below:

1. Unequal Pair: [99, 1]
2. Oversupply: [10, 10, 5]
3. Precision: [2001, 1999, 1000]
4. Power: [16, 8, 4, 2, 1, 1]
5. Odds: [9, 7, 7, 5, 5, 3, 3]
6. More Odds: [9, 7, 7, 5, 5, 3, 3, 3]
7. Fibonacci: [21, 13, 8, 5, 3, 2, 1, 1]

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

Can you prove that your solutions are best possible?

Code template

We prepared a Python 3 implementation of the panda-feeding problem that you can use to evaluate your schedules:

• Python sources

There is one file pandaX.py for each value of X in the list above. They simulate the growth of the bamboo under your periodic schedule and report the guaranteed (minimal) harvest achieved. Before you get started, you must insert your MWS (Managed Windows) username in config.py; this is the login name you use for the university computers. The classes automatically store your results to a file in the current working directory.

To run the simulation, extract the zip archive to a folder and run, e.g.,

python pandaUnequalPair.py

there.

Obey the comments! Once you downloaded the code, in each of the bamboo*.py files, add your periodic schedule to list queue. Do not change panda.py.

Deliverables

This is an individual project; each student has to submit their own solution.

The submission is on Canvas. It consists of the following parts and you have to submit all of them by uploading 3 files for the submission (plus the optional file 4 if you choose to include it). Note: Canvas does not automatically check whether you included all needed files, so this is up to you!

• File 1: Solutions
  The file username-results.json generated by running all bamboo plots with your solutions. Marks will be given for solutions achieving a higher guaranteed harvest. A secondary criterion here is simplicity of the solution: If you cannot seem to improve the harvest guarantee, extra marks can be awarded for the simplest solution that achieves that solution quality.
  Upload this JSON file as is.
• File 2: Code
  Submit all the pandaX.py files as well as any other code you may have used.
  Upload a single ZIP file with your code.

• File 3: Report
  (a) Describe any systematic approaches you used (if applicable) and (b) explain any additional code you used. Structure your writing with sections.
  (Not more than 1 page.)
  Submit 1 PDF file for this part. Only typed solutions will be marked.

• [OPTIONAL] File 4: Impossibility results
  Challenge task: Try to prove impossibility results for the bamboo plots, i.e., harvest heights that are provably impossible to attain with any schedule (not just yours). You will have to invent formal arguments to be able to do this.
  *Submit 1 PDF file for this part (if you want).

Marking

The mark is given for the quality of the achieved solutions, as a weighted average over the 7 bamboo plots. The baseline are solutions that your tutors have found; in principle you could get more than 100% for a subtask if you manage to beat their solution!

However, marks for solutions are withheld or reduced if the report does not adequately support them, i.e. if it fails to explain how they were found, e.g., by describing the process to obtain them including relevant intermediate steps or used algorithms.

Collaboration & GenAI Policy

This programming puzzle is an individual project, and you have to submit you own solution. As for all assessments, the University of Liverpool Policy on Academic Integrity applies; please refer to the Canvas page for details.

The use of generative AI for producing solutions to this assessment is not encouraged since it is intended to be worked on to build intuitions on the algorithmic problems. Using tools to generate code (such as GitHub Copilot) is allowed for routine code, but strongly discouraged for generating algorithmic solutions. If you are using generative AI in any form, it has to be documented as precisely as possible. For example, for ChatGPT, you are required to include your chat as an appendix.