Alternative solution to 18.7 Gasup problem

#1

I had problems solving and understanding the solution to Gasup problem. I came up with an alternative O(n) solution, which I find more simple to understand (at least for me).

The idea is to start at some city and try to advance the head to the next city if we have enough fuel. If we can’t advance the head, we move the tail. Anyway we have to adjust the current fuel we have. This way we move like a caterpillar until we reach our own tail:

public static City findGasup(City city) {
    int currentGallons = 0;

    City head = city;
    City tail = city;
    while (true) {
        if (currentGallons + head.gallons >= head.miles / 20) {
            currentGallons += head.gallons;                      
            currentGallons -= head.miles / 20;

            if (head.next == tail) {
                return tail;
            }

            head = head.next;
        } else {
            currentGallons -= tail.gallons;
            currentGallons += tail.miles / 20;
            if (tail == head) {
                head = head.next;
            }

            tail = tail.next;
        }
    }
}

It requires at most 2 passes around the cities and we could also add a condition to terminate after those 2 passes in case there is no ample city.

0 Likes