Nuts in an Oasis

A pile of nuts is in an oasis, across a desert from a town. The pile contains ‘N’ kg of nuts, and the town is ‘D’ kilometers away from the pile.

The goal of this problem is to write a program that will compute ‘X’, the maximum amount of nuts that can be transported to the town.

The nuts are transported by a horse drawn cart that is initially next to the pile of nuts. The cart can carry at most ‘C’ kilograms of nuts at any one time. The horse uses the nuts that it is carrying as fuel. It consumes ‘F’ kilograms of nuts per kilometer traveled regardless of how much weight it is carrying in the cart. The horse can load and unload the cart without using up any nuts.

Your program should have a function that takes as input 4 real numbers D,N,F,C and returns one real number: ‘X’

A desert oasis. Simply breathtaking.

Our first natural approach to this problem is to use a greedy approach. Since you have a cart with a maximum capacity of C, it would be rather stupid to not fit in as many nuts as possible into the cart. And there you have it, how about this simple approach: “If N = C, we could just fit all nuts into the cart and transport all of them in one trip; otherwise if N > C, fit in C kg nuts into the cart, travel to the destination, go back and fetch more nuts back, until there is no more nuts left. This yields the following equation:

The sum of X is the sum of two terms. The math symbol with the upper square bracket is the ceiling function.

* Note that the last trip (the right term) must be handled specially as it requires only one single trip!

Our poor horse (or donkey) has to pull the cart over the desert, could this be possible? Or die of hunger if there is no nuts in the cart.

Sharp readers might spot a flaw in the reasoning above. We might not want to go back to transport the last round of nuts, since it might consume more than the nuts transported. Besides, what happens when C < FD? Then, halfway down the trip our poor horse would have died of hunger!

Well, does that mean if C < FD, there’s no solution? How can you prove so? If there is a solution, how would your algorithm handle such cases? Worst still, even if C > FD, the above method does not necessarily yield the maximum X (Try to find a counter example!).

For such cases where C < FD, we definitely need to somehow subdivide the total distance (ie, choose a point somewhere in between as a transit), but the question remains:

How and where should we subdivide?

Here is where things might get a little hairy. Most people might be wondering if Dynamic Programming (DP) is really needed to find the division point that yields the maximum. It turns out this problem is highly recursive in nature and with one important observation, the derivation of the recursive formula is actually not that difficult (No DP involved though).

  • The most important observation is the rate of consumption remain constant no matter how you subdivide the distance, as long as the number of trips required is the same.
  • Since we are consuming the nuts at a constant rate, eventually we will reach one such transit point where just enough nuts are consumed such that transporting nuts to the next transit point requires one less round trip.

Let’s use a concrete example to illustrate the observation above. Assume N = 100, D = 20, C = 50, F = 1. Since N/C = 100/50 = 2, it requires 1 round trip + 1 last trip = a total of 3 trips to transport from point A to point B. Assume point B is our transit point, and the total consumption cost is 50 kg nuts. Point B could be derived mathematically, which is approximately 16.67 km (from point A). Point B must be the first transit point in order to maximize X, since from the next transit onwards you save yourself one full round trip!

Although we have found point B, we are still not quite done yet. We still need to find point C, point D, … until it reaches the destination. Since finding point C is just the exact same problem as the original problem (of course, with values of N and D changed), the rest could be solved in a recursive manner.

Continuing from the above example, we found that point B is 16.67 km from point A, which means there is about 3.33 km left to the destination, and right at point B we have a total of 50 kg of nuts to transport. Since we have to transport the remaining nuts directly to the destination (we could not subdivide again, since there are only 50 kg nuts remaining), the maximum X for the above example is: 50 – 3.33 * 1 = 46.67 kg.

Remember, every time you state a solution as a recursive formula, you must also provide the base case! Without the base case the recursion would never end. The base case is trivial to prove, as illustrated in the code below.

Please take note that the above example uses a case where N is divisible by C. You would have to figure out the case where N is not divisible by C, too (which should be straight forward once you understand the key observation). This would be left as an exercise to the reader.

Below is the full code for the solution. Deriving the mathematical formula seemed to be more tricky than I initially thought and is error prone if you’re not careful. I believe with slight modification: ie, introducing additional variables to be passed in the recursive function, the math derivation complexity could be reduced. Anyhow, my advice is to start with easy examples (like the case where N is divisible by C, and gradually apply to more complicated examples) as you visualize the formula in your head.

Edit:

Updated code with better comments and added case to handle where it might run out of fuel.

VN:F [1.9.22_1171]
Rating: 2.9/5 (19 votes cast)
Nuts in an Oasis, 2.9 out of 5 based on 19 ratings

49 thoughts on “Nuts in an Oasis

  1. Anonymous

    1337,
    may be I am being dumb (and I only read the question part not your solution) but the horse consumes fuel in the return trip as well right? But the question does not clarify that —

    VA:F [1.9.22_1171]
    +1
  2. 1337c0d3r

    @Anonymous:
    Yes, that's a hidden implication in the question.

    "It consumes 'F' kilograms of nuts per kilometer traveled regardless of how much weight it is carrying in the cart."

    VA:F [1.9.22_1171]
    0
  3. Raynor

    I think there is a bug in your reasoning. Suppose N = 101(only changed part), D = 20, C = 50, F = 1 the answer should be still 46.67 because you really CAN'T use the extra one unit of nuts. But your code give 46.87 as answer. This is because you assume all of nuts at starting point should be transfered, however this is not always the case.

    VA:F [1.9.22_1171]
    0
    1. Rishabh Malhotra

      That;s right, but hen the test case would not be the same as mentioned, and there would be more than one transit point contrary to the trivial case given here 🙂 Try understanding where he has written about “Although we have found point B, we are still not quite done yet. We still need to find point C, point D” The solution is recursive

      VA:F [1.9.22_1171]
      0
  4. 1337c0d3r

    @Raynor:
    The answer should be 46.87. This is because 100kgs of nuts could be transported to the first transit point which is 0.2km from the start point (with the consumption of 1kg nuts).

    Therefore, if you choose to abandon that 1kg of nuts, you are transporting 0.2km less :/

    VA:F [1.9.22_1171]
    0
  5. 1337c0d3r

    @Anonymous:
    The basic idea is to try to get the remainingNuts to be divisible by C, while being as large as possible (must be less than N).

    For example, if N = 100, C = 50, then remainingNuts = 50.

    If N = 101, C = 50, then remainingNuts = 100.

    That is, you try to carry the nuts as much as possible until the next trip you carry the nuts with ONE less round trip.

    VA:F [1.9.22_1171]
    0
  6. Leon

    Will this work?

    X f(D,N,F,C)
    {
    if(min(N,c)<=F*D) return 0;

    return min(C,N)-F*D+f1(D,N-min(C,N),F,C);
    }

    x f1(D,N,F,C)
    {
    if(min(N,C)<=2*F*D) return 0;
    return min(C,N)-2*F*D + f1(D, N-min(C,N), F,C);
    }

    VA:F [1.9.22_1171]
    0
  7. Anonymous

    For pratical reason, I think other than D, the rest params should be integer. I have solved it using DP (I tested both programs with various data points and get back the same value). Yours is much neater and faster. It would be difficult to get all these ironed out though. So I kept my DP solution because it is easier to follow.

    Thank you for the solution.

    Here is my version

    int GetMaxNuts(int N /*# of nuts*/, int D/*distance*/, int C /*carry each round*/, int F /*fuel per km*/)
    {
    int* x = new int[D+1];
    int* lastStop = new int[D+1];
    int round = 2*((N-1)/C +1) – 1; //total one way trip. last -1 is because we don't need to go back after the last trip
    for (int i=0; i<=D; i++)
    {
    x[i] = N-round*i*F;
    lastStop[i] = 0;
    }

    for(int i=2; i<=D; i++)
    {
    for(int j=1; j 0 ? x[D] : 0;
    }

    VA:F [1.9.22_1171]
    0
  8. 1337c0d3r

    @Anonymous:
    Is it possible to modify your code to work for real numbers? Because the question specified that N, D, C, and F are all real numbers.

    By the way Blogger has problem with pasting codes in the comment section, you can try pasting somewhere like pastebin.

    VA:F [1.9.22_1171]
    0
  9. Anonymous

    If [a1,a2,a3…,an,b1,b2…bn] is given input change this to [a1,b1,a2,b2…..an,bn] , solution should be in-place. Can you use divide and conquer to do it?

    VA:F [1.9.22_1171]
    0
  10. Sachin

    I am confused by your definition of “transit point”. It is like at this transit point, horse will unload the cart in between the way with just enough nuts left so that it can reach the oasis again and fill up the cart to its capacity. Later on, it’ll pick up the nuts from the way on its way back ?

    VA:F [1.9.22_1171]
    0
  11. Anonymous

    Yes, the transit point is the point where the horse will unload the cart. Consider the case where C < FD, e.g. C = 50, F = 1, D = 51. You can't transport the nuts in one trip because your horse will starve to death along the way. Does that mean you have no solution? Not necesarily; it depends on your value of N. Continuing with this example, if you had 53 nuts then you could take 50 nuts a distance of 1 meter (consuming 1 along the way), drop off 48, return (consuming another 1 on the return trip), take another trip with 3 nuts to the transit point (consuming 1 along the way), pickup the 48 nuts at the transit point, and now you can transport 50 to the destination.

    So if C is 50, you want to ask "How far can I move the nuts such that I can make one trip carrying 50 nuts to the destination?" I.E. "What is the furthest transit point I can choose where I can end up with 50 nuts at that transit point?"

    If you work through the example given, you can see that for the transit point as 16.67, you can get 50 nuts to the 16.67 point by using the spare 50 nuts that you have. If N was 99 instead of 100, then you would be able to get 50 nuts to some point slightly less than 16.67 using the 49 spare nuts you have.

    VA:F [1.9.22_1171]
    +2
    1. Anonymous

      This explanation is easier to understand. I am wondering whether the author has unnecessarily complicated the equation. I think it should have been:

      VA:F [1.9.22_1171]
      0
  12. hangyu

    Hi, is this right?

    // remaining weight of nuts after consumption
    double remainingNuts = C*(ceil(N/C) – 1.0);

    How can you get this?

    VA:F [1.9.22_1171]
    0
  13. Sean

    Nice job in designing and explaining your solution! I can understand the logic of your solution, but I still not convinced your solution gives the maximal possible value. Can you give the proof of correctness to make your post complete and perfect? Thanks!

    VA:F [1.9.22_1171]
    +1
  14. Pingback: Nuts in an Oasis: An Interview Question from Amazon / Google | 口├人人│의 Blog

  15. Simon

    For the example you gave, when N=100, C=50, D=20, F=1, this is my solution which gave totally different results with yours.

    First, my first transit point A is at 10KM. The horse carries 80kg nuts to B. So 70kg nuts are left when it reaches B, and 20kg nuts left at the starting point. Then, the horse carries 10kg back to the starting point and leaves 60kg nuts in B. After it goes back, it carries the rest of 20kg to B with 10kg transported to B. So there are total 70kg nuts at B. Finally, it transports all rest 70kg to the end point by traveling 10km. Therefore, it finally transports 60kg to the end point.

    However, you get 46.67, which is not maximum.

    Anywhere wrong here?

    VA:F [1.9.22_1171]
    0
  16. Nathan W.

    I think this isn’t a programming question, but rather one for testing if you can cover all the corner cases.
    Here is my solution, straightforward arithmetic, without any recursion.

    VA:F [1.9.22_1171]
    0
  17. Nathan W.

    Oops, my code got eaten partially. Why there isn’t a preview function?

    VA:F [1.9.22_1171]
    0
  18. Nathan W.

    Buggy wiki, last try.

    // assume all integers
    int maxNutsBack(int N, int C, int D, int F)
    {
    // not worth it, can’t even afford the initial 1-way trip, note possibly N < C
    if (min(C, N) <= F*D) {
    return 0;
    }

    // stop, can't afford a following round-trip, or not enough nuts
    if (min(C, N) <= 2*F*D || N 2*F*D) {
    netW += (N – C)%C – 2*F*D;
    }

    return netW;
    }

    VA:F [1.9.22_1171]
    0
  19. Nathan W.

    // assume all integers
    int maxNutsBack(int N, int C, int D, int F)
    {
    // not worth it, can’t even afford the initial 1-way trip, note possibly N < C
    if (min(C, N) <= F*D) {
    return 0;
    }

    // stop, can't afford a following round-trip, or not enough nuts
    if (min(C, N) <= 2*F*D || N 2*F*D) {
    netW += (N – C)%C – 2*F*D;
    }

    return netW;
    }

    VA:F [1.9.22_1171]
    0
  20. Genghis

    Correct me if I am wrong, I considered transit point to be exactly at distance 1 Km from the previous transit point. For transit from A to B, let Na = number of nuts at A, Nb = number of nuts at B left, then Nb = Na(1 – 2F/C) + F.
    For the example that you have considered, this one is giving around 56 nuts left at 20 Km.

    How is this answer wrong ? Even if it is wrong, how do you prove the approach that you have taken will give you the maximum nuts.

    VA:F [1.9.22_1171]
    0
  21. siv

    Hi,

    Could you please explain how did you come to this equation
    // remaining weight of nuts after consumption
    double remainingNuts = C*(ceil(N/C) – 1.0);

    Thanks in advance
    Siv

    VA:F [1.9.22_1171]
    0
  22. guoguo

    “Hi,

    Could you please explain how did you come to this equation
    // remaining weight of nuts after consumption
    double remainingNuts = C*(ceil(N/C) – 1.0);

    Thanks in advance
    Siv”

    I have the same question. Could you explain it a little bit?
    Thank you so much.

    guoguo

    VA:F [1.9.22_1171]
    0
      1. Amol

        Got equation is coming from this observation above…
        “Since we are consuming the nuts at a constant rate, eventually we will reach one such transit point where just enough nuts are consumed such that transporting nuts to the next transit point requires one less round trip.”

        VA:F [1.9.22_1171]
        0
  23. johny

    Hi 1337,

    Could you elaborate a bit more on the rationale behind the key idea: try to get the remainingNuts to be divisible by C, while being as large as possible (must be less than N)?

    1. Why must remainingNuts be divisible by C?
    2. Why must remainingNuts be as large as possible while less than N?

    Thanks!
    johny

    VA:F [1.9.22_1171]
    0
  24. Dahai Xu

    I think this problem is a waste of time since it is too flexible. 1) Assume B is a first (intermediate) transit point, why should I bring all the nuts to B first? How about dropping partial before B, partial after B? 2) If N = 110, C=50, why should I transport 50 twice then 10 for the third trip? Maybe 40,40,30 division is a better choice? 4 real numbers D,N,F,C basically make this problem intractable.

    VA:F [1.9.22_1171]
    0
    1. Brady Fang

      If N = 110, C = 50, D = 20, F = 1, basically, you will take 5 trips of 2 km to point B (the first transit point), where you will have N = 100 kg to transport.

      From point B, you will take 3 trips of 16.67 km to point C (the second transit point), where you will have N = 50 kg to transport.

      From point C, you will take the final trip of 1.33 km to the destination point, where you will have N = 48.67 kg nuts!

      VA:F [1.9.22_1171]
      0
  25. fwlx

    I’m trying to explain more towards the calculation of “remainingNuts”
    1. There is a pre-assumption that we should take all nuts to move but not leave any on the way.(Someone may be abot to prove this)
    Based on above condition, at the start point, the needed trips is constant to move nuts to a position, which equals to N_TRIPS = (2*(ceil(N/C)-1) + 1), so the consumption rate is constant which equals F * N_TRIPS

    In order to get an optimized result, we need to make the 2ed phase’s trip number smaller, but how to make it smaller? After move some distance, the total weight is smaller, so if we make the total nuts weight divisible by C, then the next phase will be smaller.

    For example
    N(120), C(50) D(100), F(1) then the 1st stage to move all nuts to the 1st transit requires 2*(ceil(120/50) -1) + 1 = 5 trips with consumption rate as 5*F nuts/kilometer

    Per the rule, the 1st stage should only consume 20nuts, then it will make the 2ed stage only requires 2*(ceil(100/50) -1) + 1 = 3 trips. The consumption rate will reduce to 3*F nuts/kilometer.

    In one word, we need to reduce the consumption rate as much as possible.

    VA:F [1.9.22_1171]
    +1
  26. Bonnie

    I like your code so much and appreciate all your effort for the code, but I really have difficulty in understanding your English:(

    VA:F [1.9.22_1171]
    0
  27. Feng

    First, the optimal solution will not leave any nuts at the starting location. Otherwise, assume L kg nuts is left. Then the horse could move (N-L) nuts d km closer to town, eating the L nuts. Thus a new input is (N-L, D-d, C, F). Since L kg is left, the initial input could be modified to (N-L, D,C,F). It’s obvious that the X(N-L,D,C,F)<=X(N-L,D-d,C,F).

    Second, the following observation is not correct:
    'Since we are consuming the nuts at a constant rate, eventually we will reach one such transit point where just enough nuts are consumed such that transporting nuts to the next transit point requires one less round trip.'
    You are assuming that the nuts could be loaded to the cart during the trip. However, they could be loaded when the cart comes back to starting location.

    VN:F [1.9.22_1171]
    0
    1. Feng

      Forget about my previous second comment. I got your meaning now:
      It takes ceil(N/C) times to load all the nuts. The #round trip is ceil(N/C)-1, so the total #trips is 2* ( ceil(N/C) -1 )+1.
      The nuts eaten by horse is cons=d*F*( 2*ceil(N/C)-1 ), then the remaining nuts at B is N-cons.
      The current transport A->B takes ceil(N/C) loads. So the next transport B->C takes one less loads. N-cons = C*(ceil(N/C)-1).

      However, it is not convincing that this solution is optimal. Why do you set next transit point require ‘one’, not more, less round trip?

      VN:F [1.9.22_1171]
      0
  28. teasping

    hi 1337c0d3r,
    I used to run some test case against your previous code and they failed. Unfortunately, now it fails with your current implementation with double typed arguments. The error is when N is not multiplies of C. E.g, (N, D, C, F) = (3200, 1000,1000,1), in the first round, your function works as below:
    numTrips = 5;
    costPerKm = 5;
    remaingingNuts = 2000;
    traveled = (3200-2000)/5=240.

    the error is the traveled 240km.
    3200 —240km—> 1000-240
    +1000 -240
    +1000 -240
    200 no =1800
    based on calculated numberTrips, the rest 200kg nuts will never be loaded by horse, so that the statement calculating traveled distance should use formatted N of 3000 instead of 3200. That is where the error is.

    My solution is to calculate two optional traveled distance when N%C != 0, one is to use numberTrips of 2*(floor(N/C)-1)+1, another is +2. the max of the two should be the one applied. Considering all the later rounds uses N as multiplies of C, the added code just work in 1st round.

    the test case can be N=3200,3400,3600 while D=1000,C=1000, F=1,

    VA:F [1.9.22_1171]
    0
  29. Bunnih

    I am thinking about why next transit point must reduce one less round trip, not two less or more?

    Let’s compare the two cases: the first one is we reduce one less round trip as in the original text (case 1). The second is we reduce two round trip (case 2).

    Suppose we start from point A and we let numTrips = 2*(ceil(N/C) – 1) + 1. Let numTrips >=5 since we want to reduce two less round trip next. Suppose B is selected as our next point in case 1 and C is our next point in case 2. D is the point we selected after B in case 1.

    From A to B, the horse eats the same amount of nuts for both case 1 and case 2. To compare the two case, we need to compare the more nuts the horse eats in B-C for case 2, and the more nuts the horse eats in C-D for case 1. It is equivalent to compare the distance between B-C and C-D since the horse eats two more trip in B-C but two less trip in C-D for case 2. If B-C is larger than C-D, then reducing one round trip (case 1) is more beneficial. On the other hand, if B-C is less than C-D, case2 is more beneficial. One observation is that the horse eats the same amount of nuts in B-C of case 2 and B-D of case 1 (Actually the amount is capacity). So B-C = capacity/ numTrips, B-D = capacity/(numTrips-2). We can derive that numTrips shoud be less than 4 if we want B-C=5 (otherwise we cannot reduce 2 round trip), it follows that case 1 is better. So we only need to reduce one round trip each time.

    VA:F [1.9.22_1171]
    0
    1. Bunnih

      We can derive that numTrips shoud be less than 4 if we want B-C less than C-D. Since we already assume than numTrips>=5 (otherwise we cannot reduce 2 round trip), it follows that case 1 is better. So we only need to reduce one round trip each time.

      VA:F [1.9.22_1171]
      0
  30. K76154

    I realized that you don’t really need this complicated algorithm. All you need is divide C by the number of trips you need with greedy method * F, without considering whether we will run out of nuts before we return to the oasis. For example, N=100, C=50, D=20, F=1. Number of trips you need with greedy method = 3, the answer will be 50/(3 * 1) = 16.67. N=150, C=50, D=20, F=1, the answer will be 50/(5*1) = 10.

    So this can be as simple as traveled = C/(ceil(N/C) * 2 – 1) * F

    The above should be able to be contained in just two lines of codes excluding the base case.

    double getMaxNuts(double N, double D, double C, double F) {
    // base case:
    // We have the capacity to carry all nuts,
    // so fetch all the nuts in one trip
    if (N = 0.0) ?
    nutsAtDestination :
    0.0; // out of fuel!
    }

    int numTrips = 2*(ceil(N/C) – 1) + 1;
    double traveled = C/(numTrips * F)

    // we are able to travel greater (or equal) than the remaining
    // distance, so fetch the nuts right to the destination
    if (traveled >= D)
    return N – D*numTrips*F;

    // calculate recursively as we travel ONE less round trip now.
    return getMaxNuts(remainingNuts, D-traveled, C, F);
    }

    VA:F [1.9.22_1171]
    0
  31. Mike

    Got this fucker during the interview. The biggest issue with this problem if that it doesn’t state anywhere that you can stop in-between.

    VA:F [1.9.22_1171]
    0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*