First Circular Tour to Visit all the Petrol Bunks

In the first circular tour to visit all the petrol bunks problem the statement is such that there is a circle with n petrol pumps on the circle. Every petrol pump has a pair of data. The first value is the amount of petrol pump has and the second is distance from that petrol pump to the next petrol pump.

Calculate the first point from where a vehicle will be able to complete a full circle. The vehicle should stop at each petrol pump and it has an infinite capacity to store petrol.

Note: With 1 litre of petrol, vehicle can go 1 unit of distance.

Example

lnput:

data = [ {4, 6}, {6, 3}, {6, 7} ]

Output:

1

Explanation:

Tour starts from index 2: (6-3) + (6-7) + (4-6) > 0, Tour starts from index 2

Algorithm for First Circular Tour to Visit all the Petrol Bunks

Here we use a Queue to store the current tour. We create a struct to store the pair of data(petrol, distance)

1. We first enqueue the first petrol pump to the Queue.

2. We keep enqueuing petrol pumps till we either complete the tour or the current amount of petrol becomes negative.

3. If the amount becomes negative, then we keep de-queueing petrol pumps until the current amount of petrol becomes positive or the queue becomes empty.

4. Here we use the same array as a queue, we maintain two index variables start and end that represent the rear and front of the queue.

C++ Program for First Circular Tour to Visit all the Petrol Bunks

#include <bits/stdc++.h>
using namespace std;
 
struct PetrolPumpData
{
  int petrol;
  int distance;
};
//function returns start point of tour
int StartPointOfTour(struct PetrolPumpData array[], int n)
{
    //Initialize start as first petrol bunk
    int start_point = 0;
    int end_point =  1;
    int curr_petrol = array[start_point].petrol - array[start_point].distance;
    while (end_point != start_point || curr_petrol < 0)
    {
        //If current petrol is negitive
        //remove first petrol pump and update start
        while (curr_petrol < 0 && start_point != end_point)
        {
            curr_petrol = curr_petrol - (array[start_point].petrol - array[start_point].distance);
            start_point = (start_point + 1)%n;
            //if zero is coming again as start point.
            //No solution
            //loop starting again
            if (start_point == 0)
               return -1;
        }
        //update current_petrol and end point
        //adding next petrol pump to Queue
        curr_petrol = curr_petrol + array[end_point].petrol - array[end_point].distance;
        end_point = (end_point + 1)%n;
    }
    //final start point
    return start_point;
}
 
//Main function
int main()
{
    struct PetrolPumpData input_array[] = { {4, 6}, {6, 3}, {6, 7} };
    int size = sizeof(input_array)/sizeof(input_array[0]);
    int result = StartPointOfTour(input_array,size);
    if(result == -1)
    {
        cout<<"No possible Tour"<<endl;
    }
    else
    {
        cout<<"Start point of tour is: "<<result<<endl;
    }
    return 0;
}

Java Program for First Circular Tour to Visit all the Petrol Bunks

import java.util.Scanner;
class sum
{
    static int printTour(int arr[][], int n) 
    {   
        int start = 0; 
        int end = 1; 
        int curr_petrol = arr[start][0] - arr[start][1]; 
        while(end != start || curr_petrol < 0) 
        { 
            while(curr_petrol < 0 && start != end) 
            { 
                curr_petrol -= arr[start][0] - arr[start][1]; 
                start = (start + 1) % n; 
                if(start == 0) 
                    return -1; 
            } 
            curr_petrol += arr[end][0] - arr[end][1]; 
              
            end = (end + 1)%n; 
        } 
        return start; 
    } 
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[][] = new int[n][2];
        for(int i=0;i<n;i++)
        {
            arr[i][0] = sr.nextInt();
            arr[i][1] = sr.nextInt();
        } 
        int start = printTour(arr, n); 
        System.out.println(start == -1 ? "No Solution" : + start);  
    } 
}

3
4 6
6 3
6 7

1