Interesting Dynamic Programming Challenge

A few days back I saw this programming question pop up on reddit and I thought it was interesting because I like doing dynamic programming (DP) type problems. Here’s the question,

The owner of a banana plantation has a camel. He wants to transport his 3000 bananas to the market, which is located after the desert. The distance between his banana plantation and the market is about 1000 kilometer. So he decided to take his camel to carry the bananas. The camel can carry at the maximum of 1000 bananas at a time, and it eats one banana for every kilometer it travels.

What is the largest number of bananas that can be delivered to the market?

Initially the number of trips that can be made back and forth between two points kind of threw me off because I wasn’t able to map the problem to a standard DP approach, but once I worked out a formula for the cost of making a trip between two points then I was able to simplify the problem. Next I stumbled down a blind alley where I was trying to model the problem as a two-dimensional DP problem, after mulling over the problem in my free time I finally got the recursive definition down today morning and was able to get the right answer. I think :)

Here’s the formula I used to calculate the bananas left after travelling a given distance,

def bananas_left(start_count, distance):
number_of_trips = (start_count//max_load)
return max(0, number_of_trips * max_load - (2*number_of_trips - 1) * distance * banana_per_mile)

Here’s the DP model I used,

Let M[n] be the max number of bananas at mile n then
M[n] = max { bananas_left(M[k], n-k) } for k = 0 .. n-1

it resembles the coin change DP problem.

Here’s the whole program,

def camel_and_bananas():
total_distance = 1000
banana_per_mile = 1
max_load = 1000
start_load = 3000

def bananas_left(start_count, distance):
number_of_trips = (start_count//max_load)
return max(0, number_of_trips * max_load - (2*number_of_trips - 1) * distance * banana_per_mile)

def print_path(index):
if index > 0:
print("{} bananas at mile {} starting with {} bananas at mile {}".format(M[index], index, M[index - W[index]], index - W[index]))
print_path(index - W[index])

M = [0] * (total_distance + 1)
W = [0] * (total_distance + 1)
M[0] = start_load

for n in range(1, total_distance + 1):
for k in range(n):
if bananas_left(M[k], n-k) > M[n]:
M[n] = bananas_left(M[k], n-k)
W[n] = n-k

print_path(total_distance)

It outputs

533 bananas at mile 1000 starting with 1001 bananas at mile 533
1001 bananas at mile 533 starting with 2000 bananas at mile 200
2000 bananas at mile 200 starting with 3000 bananas at mile 0

Which seems correct.

10 Comments

 Add your comment
  1. lots of assumptions need to be written down here…can u please do that? from my view, someone has to carry the remaining bananas and put 1 banana on Camel’s “BACK” for every kilometer…now going by conventional logic total number of banana’s that can be delivered is the number of bananas carrried by “someone”…

  2. The answer is simple logic..

    As it’s a camel, it can probably eat as many bananas before the trip and store up the energy. so even if it eats 2000 bananas before leaving, it will only just be able to take the remaining 1000 bananas to market and just get back again before it is out of energy…

    and if the camel can’t save up energy from the bananas, then the answer is zero, because it needs more bananas than it can carry to have enough food to get there and back

  3. Shouldn’t the answer be 0? The camel can only carry 1000 bananas at any given time, so you start with 1000. But it eats one banana per km, so after a single 1000km trip you won’t have any bananas left.

  4. CompetencyMatrixHater

    I worked this out in my head – it’s fairly obvious. There are 3000 bananas. The bananas can’t be taken straight to the market as the camel can only carry 1000. There’s no point taking bananas direct to the market, as the camel will eat them all before it gets there. So the camel travels 1 km at a time. At first it’s trying to move 3000 bananas, which takes 3 trips, plus 2 return trips. This costs 5 bananas per km, and this stage lasts for 200km until there are only 2000 bananas left. Then the cost drops to 3 bananas per km – for the next 333.33… km. Then the camel may as well simply keep going at a cost of 1 banana per km, as it is carrying all the bananas. It has (1000-333.33 – 200) km to go, so it ends up with 333.33 + 200 km. Of course the problem overlooks the problem of getting the camel back to the farm.

  5. Sorry, I just got to visit your site 3 days back..and came around this amazing question ( after almost a year later of the question to be posted )

    I ended up with a logic that depicts the case where the camel makes to the market with 400 bananas to sell!

    The camel will have 2 full to-and-fro trip of 400 km where it leaves a package of 200 bananas at every trip on the point of 400km, initially at every start of trip loaded with 1000 bananas. Then at the last trip it moves to 400 km with consumption of 400 bananas of last package of 1000 bananas with still having 600 bananas on load. Now as it has reached the point of 400km after consumption 0f 400 bananas, it loads 400 bananas left at initial 2 trips made. So, the remaining kilometers are 600 and the bananas on load gets to be 600(of 3rd trip) + 400 (of initial 2 trips) =1000 bananas of which it will consume 600 bananas for next 600 km and remains with 400 bananas to sell !

    400km point 1000 km point
    | |
    A————————————————————————B
    1000(set 1) –> drops(200)
    1000(set 2) –> drops(200)
    1000(set 3)–> 600 remains
    ——
    now loads(400 of initial 2 trips) –>reaches destination with 400 bananas left
    =total (600+400)= 1000 on continuation

    Actually I tried to solve this question with a logical approach.. as I was a bit noob to your methods of getting an answer with the help of a program which was a bit tough for me to understand at this moment.

    Though, if you just get time, then try to judge my answer.

  6. Hi Pratyush – That’s not a bad attempt, at least better than the people who couldn’t get past zero :) The maximum number is 533 as you can see from the output of the program, it also outputs the break down for the maximal result; 0, 200, 533 and 1000. See how that compares against your breakdown.

  7. Hi Pratyush – That’s not a bad attempt, at least better than the people who couldn’t get past zero :) The maximum number is 533 as you can see from the output of the program, it also outputs the break down for the maximal result; 0, 200, 533 and 1000. See how that compares against your breakdown.

  8. Ok, at the second attempt of reading it, I now get the logic. Thanks.

  9. I will show this to
    my friends too and I’ll see whats their suggestions for this, this is a great
    challenge, thanks!

    http://www.satellitephonesdirect.com.au/satellite-phones/iridium-9575-extreme

  10. www.linkedin.com/in/sunuthomas

    I would think the only way to solve it (with 2 intermediate points) is to write code that keeps moving these 2 points .

    STARTINGPOINT A—–INTERMEDIATE-B—INTERMEDIATE-C—-ENDPOINT D

    Move intermediate points B and C such that distances A-B ,BC or CD are always less than 500 .

    So in that case ,if you set up B at 167 and C at 501 (found through iterating in code) ,
    we would get an output of 499 bananas at endpoint D.

    ……

    The camel would take all the bananas to first intermediate point at 167 .

    So first time at intermediate point 167 , The bananas will be

    Trip 1, 1000 bananas == 1000 – 167*2 = 666 .
    Trip 2, 1000 bananas == 1000 – 167*2 = 666
    Trip 3, 1000 bananas == 1000 – 167 = 833 . (note ,the camel does not go back)

    So total bananas at first intermediate point = 2165

    Now second intermediate point is at 501 . Distance is 501 -167 . ie 334

    Bananas at 2nd intermediate point at 501 =

    Trip1 , 1000 bananas == 1000 – 334*2 = 332
    Trip2 , 1000 bananas == 1000 – 334 = 666 (note ,camel does not go back)

    Now we are left with 499 kilometers (endpoint d – intermediate point c) and 998 bananas .

    The camel just travels once to the end point ,eats 499 along the way and deposits 499 at the end.

    Note : if you substitute intermediate_point_B with 200 and 533 as intermeidatepoint_C , we would get only 334 bananas at the output .

Leave a Reply