Petrol Bunk in a Circle.

Problem

You have a circular track containing fuel pits at irregular intervals. The total amount of fuel available from all the pits together is just sufficient to travel round the track and finish where you started. Given the the circuit perimeter, list of each fuel pit location and the amount of fuel they contain, find the optimal start point on the track such that you never run out of fuel and complete circuit.

Solution

Method 1 - Using dynamic programming
 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.


Approach
Let D be the distance array.
Let P be the petrol array.
int [] D =  {4, 7, 4, 8, 4, 1};
int [] P =  {3, 5, 3, 8, 3, 6};

We have 28 KM to travel and 28 litres of petrol.

Now start with i=0;
D[0] = 4 > P[0] = 3; i=0 can not be starting point so we move to i=1;
D[1] = 7 > P[1] = 5; i=1 can not be starting point So we move to i=2;
D[2] = 4 > P[2] = 3; i=2 can not be starting pointso we move to i=3;
D[3] = 8 <= P[3] = 8; i=3 can be starting point, now keep on summing the D[i] and P[i] and P[i] >= D[i]
D[4] = 4 > P[4] = 3; here the P[i] is not greater or equal to D[i] so we break; and start from next i=5;


D[5]=1 < P[5] = 6; and carry over petrol is 5
now,
D[0] = 4 < P[0] + carry = 3 + 5;
D[1] = 7 < P[1] + carry = 5 + 4;
D[2] = 4 < P[2] + carry = 3 + 2;
D[3] = 8 < P[3] + carry = 8 + 1;
D[4] = 4 <= P[4] + carry = 3 + 1; // now next i = 5 is the same as the starting point ie index 5.
So the starting point is index=5;



 Total time complexity: O(n)

Here is code in java:

public static int findStartingNode(int [] D, int [] P) {
 int Dlen = D.length;
 int Plen = P.length;

 int Dsum = 0;
 int Psum = 0;
 for (int i=0; i<Dlen; i++) {
  Dsum += D[i];
 }

 for (int i=0; i<Plen; i++) {
  Psum += P[i];
 }
 System.out.println("Distance Sum: " + Dsum);
 System.out.println("Petrol Sum: " + Psum);

 if (Psum < Dsum) {
  return -1;
 }

 int start = 0;
 while (start < Dlen) {
  int i=start;
  int d = D[i];
  int p = P[i];

  while (d <= p) {
   int carry = p-d;
   if (i == (Dlen-1)) {
    i = 0;
   } else {
    ++i;
   }
   if (i == start) {
    return start;     
   }

   d = D[i];
   p = P[i] + carry;
  }
  if (i == (Dlen-1)) {
   start = 0;
  } else {
   start = i+1;
  }
 }
 return -1;
}

It returns the starting index of the vehicle.


References

• http://karmaandcoding.blogspot.in/2012/01/petrol-bunk-in-circle.html