关于算法:Programming-Puzzle-Bamboo-Trimming

2020/3/27 Programming Puzzle: Bamboo Trimming

https://www.wild-inter.net/te… 1/8
back to main page — COMP 526 Applied Algorithmics
Programming Puzzle: Bamboo
Trimming
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 each day cut down
exactly one of your the bamboo plants, and you cut it right back to the
roots.
Sebastian Research Teaching Blog About
2020/3/27 Programming Puzzle: Bamboo Trimming
https://www.wild-inter.net/te… 2/8
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 bamboos
with daily growth rates , we assume that after growing for days
(without cutting), bamboo will have height . Right after you cut a
bamboo, its height is 0, and so is the initial height of all bamboos at the
beginning.
Writing for the height of bamboo after days, and the bamboo
that you cut on day , we obtain:
The task is to find an infinite schedule of cuts that keeps the
maximal height as low as possible.
To simplify your planning, you decide to restrict your attention to periodic
schedules, i.e., a fixed, finite list 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:
Unequal Pair: [1,199]
Fibonacci: [1,1,2,3,5,8,13,21]
Odds [3,3,3,5,5,7,7,9]
Powers3 [3,6,12,24,48,96,192,386]
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
add your vital username in the appropriate variable,
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:
The 5 bamboo plot classes (BambooX.java for each X in { UnequalPair ,
Fibonacci , Odds , Powers3 , Precision }),
the generated file with your results (results.csv) — Make sure you
have filled in your vital username!
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.
2020/3/27 Programming Puzzle: Bamboo Trimming
https://www.wild-inter.net/te… 4/8
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!
Bamboo trimming leaderboard
For each of the five bamboo plots listed below, you can enter the best ratio (as
output by the simulation) you were able to achieve.