The Bamboo Garden Trimming Problem - Fun CS Theory |

Written by Mike James |

Sunday, 18 September 2022 |

Today is World Bamboo Day which, since 2009, is observed on September 18 in order to raise awareness about the conservation of this extremely useful plant. It reminded me of an algoritrhmic puzzle, the Bamboo Garden Trimming (BGT) problem, also known as the Robot Panda problem. Note: This article previously appeared in May 2020 as What is special about this problem it is that it is easy to state and understand and very approachable whether you are an amateur or a serious computer scientist. The problem, as stated in a paper with the title Cutting Bamboo Down to Size is:
Well, your first thought might be what a useless robotic panda to only be able to cut one bamboo per day - this was certainly Harry Fairhead's first comment but then he is our IoT, hardware and robotics guy! Try explaining to a practical man that pure algorithms are worth studying. Does it sound any more impressive expressed formally?
bi has a known daily growth rate of h_{i}>0, with h_{1}≥...≥h_{n}and ∑ h_{i} = 1. Initially, the height of each bamboo is 0, and at the end of each day, the robotic gardener can trim at most one bamboo to instantaneously reset its height to zero. The height of bamboo b_{i} at the end of day d≥1 and before the gardener decides which bamboo to trim is equal to (d−d′)h_{i}, where d′ < d is the last day preceding d in which b_{i} was trimmed (if b_{i} was never trimmed before day d, then d′= 0).The task is to construct a cutting algorithm that keeps the tallest bamboo as short as possible.This maximum height is called the makespan. Notice the overall growth rate of the garden is 1 and this means that the makespan has to be at least 1 - can you prove this? What is more there are simple cases where it can be arbitrarily close to 2 - what cases? After these preliminary observations we can start inventing algorithms to produce optimal makespans. This is where things get interesting: Two natural strategies are Reduce-Max and Reduce-Fastest(x). The paper goes on to prove some new upper bounds for both algorithms - read it to find out. It then goes on to examine the time and space demands of the algorithms. This is a really nice computer science problem that is interesting in its own right and makes a great example to introduce CS thinking. It might even hide an idea for a game within its workings - Angry Pandas? Let me know if you write it. If you would like to see an interactive simulation then visit: Bamboo Garden Trimming **Mike James**is the author ofwhich sets out to present the fundamental ideas of computer science in an informal and yet informative way.*The Programmer’s Guide To Theory,*
## More InformationCutting Bamboo Down to Size ## Related ArticlesNew Game Dots And Polygons Is NP Hard LZ Compression And The One-Bit Catastrophe Best Laid Plans of Lions and Men To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Twitter, Facebook or Linkedin.
## Comments
or email your comment to: comments@i-programmer.info |

Last Updated ( Sunday, 18 September 2022 ) |