CODEWITHSUNDEEP
algorithm
user1684308
user1684308

Reputation: 63

Algorithm - Max number of grains that can be transported

I came across an interview question asked at Google which I can not solve:

There is a pile of N kg grains at an oasis located in a distance of D km to a town. The grains need to be transported by a camel cart whose initial location is at the oasis. The cart can carry C kg of grains at a time. The camel uses the grains as fuel while transporting them. It consumes F kg/km.

Write a function that computes the maximum amount of grains (X kg) that can be transported to the town.

I tried to use recursion but I couldn't get much further without confusing myself.

Here's what I have so far:

number of transports = N / C

fuel amount for distance D = D * F

X = N - ((number of transports) * 2 * (fuel amount for distance D))

Upvotes: 6

Views: 206

Answers (4)

Tushar Gupta
Tushar Gupta

Reputation: 1410

Assuming that N, D, C and F are inputs, - 

float computeMaxGrains(float N, float D, float C, float F)
{
    //Case when the cart can carry all grains at once
    if(N <= C)
    {
        float remainingGrains = N - D*F;
        if(remainingGrains >= 0)
        {
            return remainingGrains;
        }
        else
        {
            //out of fuel
            return 0;
        }
    }

    // Grains consumed per Km = (Total Number of Trips) * F
    // Total Number of Trips = 2*(N/C) + 1
    float grainsConsumedPerKm = (float) (2*(Math.floor(N/C)) + 1);

    // Remaining grains after Camels fuel = C*(N/C - 1)
    float remainingGrains = (float) (C*(Math.floor(N/C)));

    // Distance that the Camel is able to travel before the camel is 
    // 1 less round trip = 
    // (N - Remaining Grains) / grainsConsumedPerKm
    // From equation N - (grainsConsumedPerKm * distanceTravelled) = 
    // Remaining Grains
    float distanceTravelled = (N - remainingGrains) / grainsConsumedPerKm;

    if(distanceTravelled >= D)
    {
        return N - (D * grainsConsumedPerKm);
    }

    //Use recursion for every 1 less round trip
    return computeMaxGrains(remainingGrains, D-distanceTravelled, C, F);
}

Upvotes: 4

Patricia Shanahan
Patricia Shanahan

Reputation: 26185

I think this problem is best worked iteratively, forwards. I'm going to split out the decision points. If I were writing one formula, I would use ?: All results are in Kg.

The first question is whether there is enough grain, and cart capacity, to 
justify an initial trip from oasis to town. The camel would eat FD, so 
if FD >= min(N,C) the answer is 0

If FD < min(N,C), the net amount transferred on the initial oasis to town 
trip is min(N,C)-FD. 

The camel is now in town, the remaining grain pile is N-min(N,C), and we 
have to decide whether to send it back again. If C <= 2FD, no round trip
can be profitable.

Otherwise consider a round trip with at least C remaining at the oasis. That 
gains net C-2FD (FD put in the cart in town to keep the camel fed getting 
to the oasis, C-FD remaining in the cart when it gets back to town).

If N>C, we can do floor((N-C)/C) of those round trips, net gain 
floor((N-C)/C)*(C-2FD).

After doing the initial run and any full cart round trips, the remaining 
grain pile is N%C, the remainder on dividing N by C.

If N%C > 2FD it is worth doing a final trip to empty the grain pile, with 
an additional net gain of N%C-2FD.

Upvotes: 2

Sajal Jain
Sajal Jain

Reputation: 708

This is just a guess. I am not absolutely sure.

Let G(x) denote the maximum amount of grain transported to a distance x from the source. Then 

G(x+1)= (G(x)/C)*(C-2F) + max(F,G(x)%C - F)

Now, G(0)=N and we need to find G(D) using the above formulation.

The second term max(F,G(x)%C-F) denotes

  1. F = when he does not come back to collect the remaining grains in last visit
  2. G(x)%C - F =remaining grain in the last visit and then consumes F to go back to the destination

Upvotes: 0

Sinkingpoint
Sinkingpoint

Reputation: 7634

As a idea, while there is more than D*F grain in the oasis the camel will travel, with C kg, or however much is left in the oasis. The camel consumes D*F kg on the trip there, drops off his load - 2*D*F kg of grain and returns if there is enough grain left to warrant the return journey.

Upvotes: 0

Related Questions