make the full circular path, shortest path exercis

Question

I got this question in an interview and I was not able to solve it.

You have a circular road, with N number of gas stations. You know the ammount of gas that each station has. You know the ammount of gas you need to GO from one station to the next one. Your car starts with 0 gas. The question is: Create an algorithm, to know from which gas station you must start driving to COMPLETE the circular PATH. It does not specify that you must visit all stations. You can only drive clockwise.

I had to do it in c#

The only code I started is with a GasStation entity

class GasStation
  int gasAtStation;
  int gasToMoveToNextStationNeeded;
  string nameOfGasStation;


GasTation wheretoStart(List<GasStation> list)
{

}

I did it this way:

static void Main(string[] args)
        {
            int[] gasOnStation = {1, 2, 0, 4};
            int[] gasDrivingCostTonNextStation = {1, 1,2, 1};

            FindStartingPoint(gasOnStation, gasDrivingCostTonNextStation);

        }

        static void FindStartingPoint(int[] gasOnStation, int[] gasDrivingCosts)
        {
            // Assume gasOnStation.length == gasDrivingCosts.length
            int n = gasOnStation.Length;
            int[] gasEndValues = new int[n];
            int gasValue = 0;
            for (int i = 0; i < n; i++)
            {
                gasEndValues[i] = gasValue;
                gasValue += gasOnStation[i];
                gasValue -= gasDrivingCosts[i];
            }

            if (gasValue < 0)
            {
                Console.WriteLine("Instance does not have a solution");
                Console.ReadLine();
            }
            else
            {
                // Find the minimum in gasEndValues:
                int minI = 0;
                int minEndValue = gasEndValues[0];
                for (int i = 1; i < n; i++)
                {
                    if (gasEndValues[i] < minEndValue)
                    {
                        minI = i;
                        minEndValue = gasEndValues[i];
                    }
                }

                Console.WriteLine("Start at station: " + minI);
                Console.ReadLine();
            }
        }

Thanks

Answer 1

One easy way of solving this is using a brute force method. i.e. try every posibility and throw out ones that don't work.

i.e. Start at each gas station in turn (repeat below for each starting station).

• Have a varible that defines current gas level.
• Loop through each gas station, in a clockwise order.
  1. Fill up your gas (increment gas by gas station amount).
  2. Check you can move to the next station (gas >= gasToMoveToNextStationNeeded)
     • If not, this isn't a solution, so move to the next starting location.
     • If so, subtract that amount of gas used, then keep going until you reach the start again.
  3. If you get back to the starting gas station you have an answer.

---

Edit As per @Vash's answer, As an improvement when deciding where to start, discount stations that don't have enough gas themselves to get to the next station and working through starting stations in order of amount of gas (descending).

---

Note, this assumes we visit all gas stations. Will need refinement for skipping gas stations if you need an optimal solution (question doesn't specify this).

Answer 2

Find the gas station with the most gas but for when the gas for the next station when added to the tank does not exceed the capacity of the tank.

Answer 3

This perhaps?

• Find the gas station with the largest amount of gas
• List all gas stations, and take their fuel value, subtract the cost of driving there
• Drive to the gas station with the highest value
• Repeat until all gas stations are visited

Answer 4

Make circular list of stations. Find any station with positive value of

Excess = (gasAtStation - gasToMoveToNextStationNeeded)

This is current base.

While next station has negative Excess value, add it's gasAtStation and gasToMoveToNextStationNeeded to current base fields, and remove this station from list.

Repeat for all positive stations circularly.

When no more stations to remove:

If one or some non-negative stations remains in list - any of them is suitable as starting point.

Example:

A(-50) B(100) C(-20) D(-90) E(60) [C->B]

A(-50) B(80) D(-90) E(60) [D->B]

A(-50) B(-10) E(60) [A->E]

B(-10) E(10) [B->E]

E(0)

Answer 5

While trying each start station of course works fine, it takes quadratic time, while there is a simple linear-time algorithm.

Use a magic car that can keep going if the fuel level runs into the negative. Start at an arbitrary station and do a full tour, visiting every station. If you return with less than zero fuel, there is no solution. Otherwise, the best station to start is the one where the fuel level on arrival was lowest.

This works because the fuel levels of all possible tours are identical except for a constant offset.

Answer 6

The task is really open. As you do a cycle, so the best option is to start from the station that have largest enough fuel amount. This mean that you will be able to tank your car and drive to next nearest station.

When we have a place to start we only have to decide on which gas station we need to stop. For the first run we can stop an every station.

EDIT.

Small improvement that came up after discussion with Lasse V. Karlsen.

If the selected first station will not succeed to make the cycle. Then select next one in the same way with smaller* fuel/road proportion.

*Smaller then first selected station proportion.