The Gas Station Problem

July 17, 2015

Today’s exercise is a classic problem in computer science courses:

There is a truck driving clockwise on a circular route; the truck has a gas tank with infinite capacity, initially empty. Along the route are gas stations with varying amounts of gas available: you are given a list of gas stations with the amounts of gas they have available and the amounts of gas required to drive to the next gas station. You must find a gas station that, for a trip starting from that gas station, will be able to return to that gas station.

For instance, consider a route with eight gas stations having 15, 8, 2, 6, 18, 9, 21, and 30 gallons of gas; from each of those gas stations to the next requires 8, 6, 30, 9, 15, 21, 2, and 18 gallons of gas. Obviously, you can’t start your trip at the third gas station, with 2 gallons of gas, because getting to the next gas station requires 30 gallons of gas and you would run out of gas reaching it.

Your task is to write a program that determines a suitable starting point for the truck; your algorithm should be linear in the number of gas stations and require constant space. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

9 Responses to “The Gas Station Problem”

  1. Paul said

    A brute force solution in Python.

    from collections import deque
    from itertools import accumulate
    
    def solve_bf(G, D):
        G, D = deque(G), deque(D)
        G.rotate(1), D.rotate(1)
        for start in range(len(G)):
            G.rotate(-1), D.rotate(-1)
            fuel, dist = accumulate(G), accumulate(D)
            if all(d <= f for d, f in zip(dist, fuel)):
                return start
    
  2. Paul said

    And a better solution. Gives the same answer as the previous post.

    def solve(fuel, dist):
        e = [f - d for f, d in zip(fuel, dist)]
        return max(zip(e, count()))[1]
    
  3. Paul said

    Oops. Forget my last post. It is wrong.

  4. Mike said

    Python solution:

    Start at the first gas station.

    If the gas in the tank plus the gas at the station is enough, then go to the next station (current += 1).

    If there isn’t enough gas, then try moving the start gas station to the previous station (start -= 1).

    Repeat until the truck makes it back to the start.

    Only passes through the list of gas stations once and uses three variables, so it meets the O(n) time and O(1) space constraints.

    def gas_station(gas, dist):
        start = len(gas)
        current = 0
        gas_in_tank = 0
        
        while current < start:
            if gas_in_tank + gas[current] >= dist[current]:
                gas_in_tank += gas[current] - dist[current]
                current += 1
            else:
                start -= 1
                gas_in_tank += gas[start] - dist[start]
                
        return start % len(gas)
    
  5. Paul said

    Another Python solution. Take the cumulative sum of the excess fuel. The solution is the station after the station where the excess fuel is most negative.

    def solve(fuel, dist):
        e = list(accumulate(f - d for f, d in zip(fuel, dist)))
        if e[-1] >= 0: # otherwise there is not enough fuel
            minindex = min(enumerate(e), key=itemgetter(1))[0]
            return (minindex + 1) % len(fuel) 
    
  6. Raaj said

    Can Someone Name which classic problem is this..

  7. mcmillhj said

    Similar counting solution in SML:

    fun findStartingStation stations required_gasoline = let
        val len = length(stations)
        fun loop(current_tank,min_tank,starting_position,current_position,[],required_gasoline) = if current_tank < 0 then ~1
                                                                                                  else starting_position
          | loop(current_tank,min_tank,starting_position,current_position,(s::ss),(g::gs)) = let
              val new_tank = current_tank + s - g
          in
              if new_tank < min_tank
              then loop(new_tank,new_tank,(current_position mod len),current_position + 1,ss,gs)
              else loop(new_tank,min_tank,starting_position,current_position + 1,ss,gs)
          end
            
    in
        loop(0,1000000,0,1,stations,required_gasoline)
    end
    
    val result1 = findStartingStation [15,8,2,6,18,9,21,30] [8,6,30,9,15,21,2,18]
    (* 6 *) 
    val result2 = findStartingStation [15,8,2,6,18,9,21,29] [8,6,30,9,15,21,2,18]
    (* -1 *)
    
  8. matthew said

    This is much like Paul’s solution, ie. find the point with the smallest cumulative increase from the start, but written as single loop:

    def solve(a,b):
        last = 0; least = 0; start = 0
        for i in range(len(a)):
            last += a[i]-b[i] # Cumulative increase
            if last < least: least = last; start = i
        return -1 if last < 0 else start+1
    
    print(solve ([ 15, 8, 2, 6, 18, 9, 21, 30 ],
                 [ 8, 6, 30, 9, 15, 21, 2, 18 ]));
    
  9. […] Racket solution to the gas station problem: […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: