[ADSx] - PetrolPumps Queue

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * https://www.geeksforgeeks.org/find-a-tour-that-visits-all-stations/
 * <p>
 * Suppose there is a circle. There are n petrol pumps on that circle. You are given two sets of data.
 * <p>
 * 1. The amount of petrol that every petrol pump has.
 * 2. Distance from that petrol pump to the next petrol pump.
 * <p>
 * Calculate the first point from where a truck will be able to complete the circle
 * (The truck will stop at each petrol pump and it has infinite capacity).
 * Expected time complexity is O(n). Assume for 1 litre petrol, the truck can go 1 unit of distance.
 * <p>
 * For example, let there be 4 petrol pumps with amount of petrol and distance to next petrol pump value pairs as {4, 6}, {6, 5}, {7, 3} and {4, 5}. The first point from where truck can make a circular tour is 2nd petrol pump. Output should be “start = 1” (index of 2nd petrol pump).
 */

class PetrolPump {
    int petrol;
    int distance;

    public PetrolPump(int petrol, int distance) {
        this.petrol = petrol;
        this.distance = distance;
    }

    public int getPetrol() {
        return petrol;
    }

    public int getDistance() {
        return distance;
    }

    @Override
    public String toString() {
        return String.format("<P:%d, D:%d>", petrol, distance);
    }
}

class Node {

    int position;
    int petrol;
    int distance;
    Node next;

    public Node(int pos, int a, int b) {
        position = pos;
        petrol = a;
        distance = b;
        next = null;
    }
}

public class PetrolPumpsQueue {

    public static int solveQueue(int length, Queue<PetrolPump> queue) {

        for (int i = 0; i < length; i++) {

            int petrolSum = 0;
            boolean valid = true;

            for (int j = 0; j < length; j++) {

                PetrolPump current = queue.poll();
                queue.add(current);

                petrolSum += current.getPetrol();

                if (petrolSum < current.getDistance()) valid = false;
                else petrolSum -= current.getDistance();

                /*System.out.printf("petrolSum: %d, distance: %d, valid: %b \n",
                        petrolSum, current.getDistance(), valid);
                System.out.println(queue);*/
            }

            if (valid) return i;

            PetrolPump poll = queue.poll();
            queue.add(poll);
        }

        return -1;
    }

    public static int solveArray(PetrolPump array[], int n) {
        /**
         * https://www.geeksforgeeks.org/find-a-tour-that-visits-all-stations/
         * */

        int start = 0;
        int end = 1;
        int curr_petrol = array[start].petrol - array[start].distance;

        // If current amount of petrol in truck becomes less than 0, then
        // remove the starting petrol pump from tour
        while (end != start || curr_petrol < 0) {

            // If current amount of petrol in truck becomes less than 0, then
            // remove the starting petrol pump from tour
            while (curr_petrol < 0 && start != end) {
                // Remove starting petrol pump. Change start
                curr_petrol -= array[start].petrol - array[start].distance;
                start = (start + 1) % n;

                // If 0 is being considered as start again, then there is no
                // possible solution
                if (start == 0)
                    return -1;
            }
            // Add a petrol pump to current tour
            curr_petrol += array[end].petrol - array[end].distance;

            end = (end + 1) % n;
        }

        // Return starting point
        return start;
    }

    public static int solveSLL(Node head) {
        /**
         * https://ideone.com/Muk97k
         * */

        Node start = head;
        do {
            Node curr = start;            // Storing the starting node
            int petrol_left = 0;

            // if petrol is left and the current node is not the starting node
            do {
                petrol_left += curr.petrol - curr.distance;
                curr = curr.next;
            }
            while (petrol_left >= 0 && curr != start);

            if (petrol_left >= 0)
                return start.position;

            start = start.next;

        } while (start != head);

        return -1;
    }

    public static void main(String args[]) {
        PetrolPump array[] = {
                new PetrolPump(6, 4),
                new PetrolPump(3, 6),
                new PetrolPump(7, 3)
        };

        int result;

        result = solveArray(array, array.length);
        System.out.println("Array: " + result);

        Queue<PetrolPump> queue = new LinkedList<>();
        queue.addAll(Arrays.asList(array));

        result = solveQueue(queue.size(), queue);
        System.out.println("Queue: " + result);

        Node head = new Node(1, 4, 6);
        head.next = new Node(2, 6, 5);
        head.next.next = new Node(3, 7, 3);
        head.next.next.next = new Node(4, 4, 5);
        head.next.next.next.next = head;

        result = solveSLL(head);
        System.out.println("SLL: " + result);
    }
}