suggest an algorithm for the following puzzle!

Question

There are n petrol bunks arranged in circle. Each bunk is separated from the rest by a certain distance. You choose some mode of travel which needs 1litre of petrol to cover 1km distance. You can't infinitely draw any amount of petrol from each bunk as each bunk has some limited petrol only. But you know that the sum of litres of petrol in all the bunks is equal to the distance to be covered.

ie let P1, P2, ... Pn be n bunks arranged circularly. d1 is distance between p1 and p2, d2 is distance between p2 and p3. dn is distance between pn and p1.Now find out the bunk from where the travel can be started such that your mode of travel never runs out of fuel.

Answer 1

There is an O(n) algorithm.

Assume v[0] = p1 - d1, v[1] = p2 - d2, ... , v[n-1] = pn - dn. All we need to do is finding a starting point i, such that all the partial sum is no less than 0, i.e., v[i] >= 0, v[i] + v[(i+1)%n] >= 0, v[i] + v[(i+1)%n] + v[(i+2)%n] >= 0, ..., v[i]+...+v[(i+n-1)%n] >= 0.

We can find such a start point by calculating s[0] = v[0], s[1] = v[0]+v[1], s[2] = v[0]+v[1]+v[2], ..., s[n-1] = v[0] + ... + v[n-1], and pick up the minimum s[k]. Then the index (k+1)%n is the start point.

Proof: Assume the minimum element is s[k]. By the problem description, there must be the minimum s[k] <= 0.

Because the total sum v[0] + v[1] + ... + v[n-1] = 0, we have v[k+1] + v[k+2] + ... v[n-1] = -s[k] >= 0, and it is impossible that v[k+1] + ... v[j] < 0 (k < j < n). (Because if v[k+1] + ... v[j] < 0, then s[j] < s[k], which is contradictory with the assumption that s[k] is minimum.) So we have v[k+1] >= 0, v[k+1] + v[k+2] >= 0, ..., v[k+1] + v[k+2] + ... + v[n-1] >= 0.

Because s[k] is the minimum one, We also have v[k+1] + v[k+2] + ... + v[n-1] + v[0] = -s[k] + v[0] = -s[k] + s[0] >= 0, -s[k] + v[0] + v[1] = -s[k] + s[1] >= 0, ..., -s[k] + v[0] + v[1] + ... + v[k-1] = -s[k] + s[k-1] >= 0. So all the parital sum starting from (k+1) is no less than 0. QED.

Answer 2

Let's choose a junk algorithm that we know is wrong to see why it is wrong...

Notation...

Current Point: (gallons of gas at Current Point, gallons required to make next point)-> Remaining Gas (gallons)

In a little more mathematical form:

P[i]: (g(P[i]), d(P[i+1])) -> sum of (g(P[i]) - d(P[i+1])) from i=1 to current point-1

(And now for the bad algorithm...)

P1: (2,2) -> 0 (at P2)
P2: (5,3) -> 2 (at P3)
P3: (2,4) -> 0 (at P4)
P4: (2,5) -> -3 (ran out of gas 3 miles short of P5)

In order to make it to P5, we have to have three extra gallons of gas by the time we make it to P3, and in order to have 3 extra gallons at P3, we need to have 3 extra gallons at P1:

??? -> +3 (at P1)
P1: (2,2) -> 0+3 = 3 (at P2)
P2: (5,3) -> 2+3 = 5 (at P3)
P3: (2,4) -> 0+3 = 3 (at P4)
P4: (2,5) -> -3 +3 = 0 (made it to P5)

The trick, therefore, is to find the very worst sections -- where you are not given enough gas to traverse them. We know we can't start from P4, P3, P2, or P1. We have to start somewhere earlier and save up enough gas to make it through the bad section.

There will no doubt be multiple bad sections within the circle, making this somewhat complicated, but it's actually quite easy to figure out how to do this.

It's possible that the next few points following the very worst stretch in the circle could be traveled after the stretch, but only if they make no changes to your gas reserves. (e.g. the point after the worst stretch gives you 2 gallons of gas and makes you go 2 gallons of distance to the next point.)

In some cases, however, the worst section MUST be covered last. That's because before you start on that section, you need as much gas saved up as possible, and the next point after the worst stretch might give you the very last bit of gas that you need, which means you need to traverse it prior to taking on the worst stretch. Although there may exist multiple solutions, the simple fact of the matter is that traversing the worst section last is ALWAYS a solution. Here's some code:

class point_ {
int gasGiven_;
int distanceToNextPoint_;

public:
int gasGiven() {return gasGiven_;}
int distanceToNextPoint {return distanceToNextPoint_;}
}

class Circle_ {
public:
numberOfPoints;
point_ *P;
}

In main():

int indexWorstSection=0;
int numberPointsWorstSection=0;
int worstSum=0;
int currentSum=0;
int i=0; 
int startingPoint =0;

// construct the circle, set *P to malloc of numberOfPoints point_'s, fill in all data

while (i<(Circle.numberOfPoints-1) || currentSum<0)
   {
   currentSum += Circle.P[i].gasGiven() - Circle.P[i].distanceToNextPoint();

   if (currentSum < worstSum) { worstSum = currentSum; indexWorstSection=i-numberPointsWorstSection; startingPoint=i;}

   if (currentSum>0) { currentSum=0; } 
     else { numberPointsWorstSection++; }

   if (i==(Circle.numberOfPoints-1)) { i=0; }
     else { i++; }
   }

if (indexWorstSection<0) indexWorstSection=Circle.numberOfPoints+indexWorstSection;

The reason why you can't make it a for-loop is because the worst section might be, for example, from i=(Circle.numberOfPoints -2) to i=3. If the currentSum is under zero, it must continue back at the start of the array.

Haven't tried the code and haven't done any serious programming in almost a decade. Sorry if it has some bugs. You will no doubt have to clean this up a bit.

Answer 3

This does what several of the other answers do - finds the minimum of the "graph" created by the net-change-in-petrol deltas as you circle around. Depending on where we start, the exact values may be moved uniformly upwards or downwards compared to some other starting position, but the index of the minimal value is always a meaningful indication of where we can start and know we'll never run out of petrol. This implementation tries to minimise memory use and completes in O(n).

#include <iostream>

int dist[] = { 3, 10, 2, 4, 6, 9 };
int refill[] = { 3, 4, 6, 3, 7, 11 };

static const int n = sizeof dist / sizeof *dist;

int main()
{
    int cum = 0, min = 0, min_index = 0;
    for (int i = 0; i < n; ++i)
    {
        cum += refill[i] - dist[i];
        std::cout << cum << ' ';
        if (cum <= min)
        {
            min = cum;
            min_index = i;
        }
    }
    std::cout << "\nstart from index " << (min_index + 1) % n << " (0-based)\n";
}

See it running on ideone.com