Find first circular tour that visits all petrol pumps

First circular tour that visits all petrol pumps

Assuming there are n petrol pumps situated at circumference of a circle.  Each petrol pump can fill certain amount of petrol to your truck or bike. Given the information capacity of each petrol pump and distance of this petrol pump to next one, find first circular tour that visits all petrol pumps. You cannot move from one petrol pump to next if distance is more than petrol you have. Assumption is truck goes 1 unit of distance for 1 unit of petrol and it has infinite capacity tank.
circular tour that visits all petrol pumps

Example inout to problem be : (4,6),(7,5),(6,5). First set gives capacity of first petrol pump i.e 4 and distance to next petrol pump i.e. 6. As we can see that this cannot be the starting point of tour as distance to travel is more than petrol i.e  net available petrol is 4-6 =2. What if we start from next station which has 7 liter of petrol, and distance to next pump is 5. We can travel to station 2. Available petrol with us is 7-5 = 2.  We get 6 liters more at station 2, petrol = 8 and distance to be travelled is only 5. When we reach at station 0 (mind you it’s a circle), we have available petrol as 8-5 =3. If we want to go to station 1, to complete the circle (we started with station 1), we have petrol  = 3 + 4 = 7 and distance to travel is 6 and hence, we can move. To sum up, station 1 should be our starting point of circular tour which visits all petrol pumps.

Circular tour that visits all petrol pumps

Brute force approach as explained in example will be to start with  a random petrol pump as starting point for circular tour. Our end should be immediately next petrol pump. As we move in circle, our start and end points move too, based on conditions. When end becomes to start, that mean we have finished the circle.

StartPoint = 0; endPoint = 1;

How to decide if our truck can reach to next petrol station? If capacity of start station is more than the distance to be travelled, then yes. We keep starting point as same, and end point moves forward to next to next station. Update available petrol too.

endPoint = (endPoint + 1)%numStations
availablePetrol = petrol[startPoint] - distance[startPoint]

What if that is not the case, i.e distance to be travelled is more than petrol available? Then, we cannot move from current start point to next station. Hence, change start point to next station and start all over again.

startPoint = (startPoint + 1)%numStations
endPoint = (endPoint + 1)%numStations

For each petrol pump, we have to possibilities, first, we have available petrol, and we can move to next station, or we don’t have enough available petrol and we change our starting point.

Brute force approach as discussed above has complexity of O(n2), as we check each petrol pump as start point and find if circular tour that visits all petrol pump is possible or not.

Let’s try optimizing it. We can use a queue to enqueue all the petrol pumps which are already visited while there was available petrol. If we reach a petrol pump where available petrol becomes negative,  that means, we have to travel more distance that petrol available. Start dequeueing from queue station, till available petrol become positive again. The station when available petrol becomes positive is the new start point to consider for circular tour.

Circular tour that visits all petrol pumps : Queue based approach

In queue based implementation, we have to used an auxiliary queue which adds to extra space complexity. We can use same array as queue and get rid of this extra space requirement. We can use start and end stations in tour as front and rear of queue.

Implementation using input array as queue

#include <stdio.h>
 
typedef struct station
{
  int petrol;
  int distance;
}Station;
 
int circularTour(Station stations[], int n)
{
    int startPos = 0;
    int end =  1;
 
    int availablePetrol = stations[startPos].petrol 
                          - stations[startPos].distance;
 
    while (end != startPos || availablePetrol < 0)
    {
        while (availablePetrol < 0 && startPos != end)
        {
            availablePetrol -= stations[startPos].petrol 
                               - stations[startPos].distance;
            startPos = (startPos + 1)%n;
 
            if (startPos == 0)
               return -1;
        }
        
        availablePetrol += stations[end].petrol - stations[end].distance;
 
        end = (end + 1)%n;
    }
 
    // Return starting point
    return startPos;
}
 
// Driver program to test above functions
int main()
{
    int n = 3;
    Station stations[n];
    
    stations[0].petrol = 6;
    stations[1].petrol = 3;
    stations[2].petrol = 7;

    stations[0].distance = 4;
    stations[1].distance = 6;
    stations[2].distance = 3;
 
    printf("Start point  : %d ", circularTour(stations, n));
 
    return 0;
}

There is another good solution to problem which does not use queue at all and is based on greedy algorithm.

1. If sum of petrol at all stations is more than sum of distances between all stations, it imply that there is no solution possible.

2. We start at i, and hit available petrol as negative at j. As we know TotalSum(petrol) – TotalSum(distance) is greater than 0. Discard i to j and start from j + 1 station.

Circular tour that visits all petrol pumps : Greedy algorithm

Complexity to find circular tour that visits all petrol pumps using queues and greedy approach is O(N).

#include <stdio.h>

typedef struct station{
	int petrol;
	int distance;
} Station;

int circularTour(Station stations[], int n) {
	
	int total = 0;
	int availablePetrol = 0;
	int startPos = 0;
    
	for(int i=0; i<n; i++) {
		int delta = stations[i].petrol - stations[i].distance;
		if(availablePetrol >= 0)
			availablePetrol += delta;
		else {
			availablePetrol = delta;
			startPos = i;
		}
		total += delta;
	}
 
        return total >= 0 ? startPos : -1;
}
 
int main() {
	int n = 3;
	Station stations[n];
	
	stations[0].petrol = 6;
	stations[1].petrol = 3;
	stations[2].petrol = 7;

	stations[0].distance = 4;
	stations[1].distance = 6;
	stations[2].distance = 3;

	printf("Start point  : %d ", circularTour(stations, n));
      
        return 0;
}

Please share if there is something wrong or missing. If you are interested in contributing to algorithms and me, please contact us and earn money and respect of fellow coders.