The Robot Panda Problem - Fun CS Theory
Written by Mike James   
Monday, 04 May 2020

This isn't really news, but I think it's fun and deserves to be better known. It's the robot panda problem, otherwise known as the Bamboo Garden Trimming (BGT) problem. What is special about it is that it is easy to state and understand and very approachable whether you are an amateur or a serious computer scientist.

pandagarden

The problem, as stated in a recent paper, is:

"You just bought a house by a lake. A bamboo garden grows outside the house and obstructs the beautiful view of the lake. To solve the problem, you also bought a robotic panda gardener which, once per day, can instantaneously trim a single bamboo. You have already measured the growth rate of every bamboo in the garden, and you are now faced with programming the gardener with a suitable schedule of bamboos to trim in order to keep the view as clear as possible"

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?

The garden contains n bamboos b1,...,bn, where bamboo
bi has a known daily growth rate of hi>0, with h1≥...≥hn
and ∑ hi = 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 bi at the end of day d≥1 and before the gardener decides which bamboo to trim is equal to (d−d′)hi, where d′ < d is the last day preceding d in which bi was trimmed (if bi 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).
Reduce-Max trims the tallest bamboo of the day, while Reduce-Fastest(x) trims the fastest growing bamboo among the ones
that are taller than x. It is known that Reduce-Max and Reduce-Fastest(x) achieve a makespan of O(logn) and 4 for the best choice of x= 2, respectively.

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

pandagarden

  • Mike James is the author of The Programmer’s Guide To Theorywhich sets out to present the fundamental ideas of computer science in an informal and yet informative way.

 

More Information

Cutting Bamboo Down to Size
Davide Bilò, Luciano Gualà, Stefano Leucci, Guido Proietti and Giacomo Scornavacca

Related Articles

New Game Dots And Polygons Is NP Hard

The Grasshopper Problem

LZ Compression And The One-Bit Catastrophe

Best Laid Plans of Lions and Men

Irrational Guards

Cannibal Animal Games     

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.

 

Banner


Celebrate 25 Years of Java With JetBrains
03/07/2020

JetBrains is hosting a Java Technology Day on Friday July 10th with ten hour-long sessions from industry leaders. Register now to get instructions to join this virtual event which will be using GoToWe [ ... ]



Devs Finally Angry At Apple's App Store
24/06/2020

Fear And Loathing In The App Store 26 - If you are a dog on a leash you don't notice it unless you try to go your own way. So if you want to be a happy App Store developer don't pull on the leash like [ ... ]


More News

graphics

 



 

Comments




or email your comment to: comments@i-programmer.info

Last Updated ( Friday, 08 May 2020 )