Challenge – Camel and Bananas

Posted on by

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.

  • Abhay

    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”…

  • http://profiles.google.com/jeffuk jeff sergeant

    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

  • CT Vargas

    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.

  • 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.