make the full circular path, shortest path exercise?

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

If we define that a trip from station A to B comprises of the GasAtStation A and TripCost. Then for each trip we have that TripBalance = GasAtStation-TripCost

The sum of all the trip balances must be greater or equal to zero, otherwise a solution does not exist. The solution consists of having a list with the trip balances for each gas station and iterate through the items keeping a variable for the tripBalance, if the tripBalance becomes negative, then the trip should start at the next gas station, if so, we reset the tripBalance and we keep processing until we check the last entry in the list:

public int FindFirstStation(List<int> tripBalances)
{
  if (tripBalances.Sum() < 0) return -1;
  var firstStation = 0;
  var tripBalance = 0;

  for (int i = 0; i < tripBalances.Count; i++)
  {
    tripBalance += tripBalances[i];
    if (tripBalance < 0)
    {
      tripBalance = 0;
      firstStation = i + 1; // next station
    }
  }
  return firstStation;
}

I tested it using the following code:

[TestMethod]
public void Example()
{
  var tripBalances = new List<int> { 0, 1, -2, 3 };
  var resolver = new GasStationResolver();
  var indexOfGasStation = resolver.FindFirstStation(tripBalances);
  Assert.AreEqual(3, indexOfGasStation);
}

See that the passed values are the ones worked out from the example given at the question header. In this case, the answer is that the last gas station in our list should be the first gas station. Finally, if there is not solution, the method returns -1.

Another example to cover where the stations with higher gas are not the solution:

/// <summary>
/// Station 1 - Gas: 3   Cost: 4
/// Station 2 - Gas: 10  Cost: 11
/// Station 3 - Gas: 8   Cost: 9
/// Station 4 - Gas: 6   Cost: 3
/// Station 5 - Gas: 4   Cost: 2
/// 
/// Then - Trip Balances are:
/// Station 1 - -1
/// Station 2 - -1
/// Station 3 - -1
/// Station 4 -  3
/// Station 5 -  2
/// </summary>
[TestMethod]    
public void SecondExample()
{
  var tripBalances = new List<int> { -1, -1, -1, 3, 2 };
  var resolver = new GasStationResolver();
  var indexOfGasStation = resolver.FindFirstStation(tripBalances);
  Assert.AreEqual(3, indexOfGasStation);
}

Answer 2

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 3

This is optimized case of @George Duckett's answer.

• Choose and remember your start station.
• Loop(1) through stations clockwise.
  • Get a fuel.
  • If you have enough fuel, go to next station, decrease remaining fuel amount, continue loop(1)

If you reached your start station - problem solved.

If on some station you do not have enough fuel to reach next one

• Remember your end station.
• Distance_to_start = 0, fuel_to_start = 0
• Loop(2) from your start station counterclockwise.
  • Add available fuel and distance to next station to your counters
  • If fuel_to_start > distance_to_start, you have some excess fuel. Mark this station as your new start and go to loop(1) again - may be you can go ahead now.
  • Otherwise, continue loop(2)

If you had gone counterclockwise to already visited station - bad luck, there is not enough fuel on stations to go full circle.

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

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.

Answer 6

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 7

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 8

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.