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.