The Gas Station Problem

July 17, 2015

It is convenient to think of the excess gallons of gasoline at each station beyond what is required to reach the next station. Thus the excess at each station is 7, 2, -28, -3, 3, -12, 19, and 12.

Obviously the route must begin at a point where the excess is positive; otherwise, the solution would immediately fail. By inspection of the sample data, the route begins at the seventh stop, with 21 gallons available. Starting there, the truck has 19 gallons at the end of the first leg, 31 gallons at the end of the second leg, 38 gallons at the end of the third leg, 40 gallons at the end of the fourth leg, 12 gallons at the end of the fifth leg, 9 gallons at the end of the sixth leg, 12 gallons at the end of the seventh leg, and 0 gallons at the end of the eighth leg, when it completes the route.

With that introduction, we provide our first solution, which calculates the accumulated excess starting from each station, moving on to the next station if the accumulated excess ever becomes negative and reporting a solution if all the stations have been visited:

(define (solve1 stations gasoline)
  (let ((len (vector-length stations)))
    (define (excess n)
      (let ((m (modulo n len)))
        (- (vector-ref stations m) (vector-ref gasoline m))))
    (let loop ((s 0) (i 0) (exs 0))
      (cond ((= s len) #f) ; no solution
            ((and (= i len) (not (negative? exs))) s) ; solution
            ((negative? exs) (loop (+ s 1) 0 0))
            (else (loop s (+ i 1) (+ exs (excess (+ s i)))))))))

> (solve1 '#(15 8 2 6 18 9 21 30) '#(8 6 30 9 15 21 2 18))
6
> (solve1 '#(15 8 2 6 18 9 21 29) '#(8 6 30 9 15 21 2 18))
#f

Here s is the starting station, i is the current number of stations visited, and exs is the amount of gasoline remaining in the tank. That works; counting from 0, station 6 is the one with 21 gallons of gasoline, and the solution returns #f when the total available gasoline is less than necessary. But it takes quadratic time to compute each route from each station. Here’s a solution that takes linear time, with stations and gasoline given as lists instead of vectors:

(define (solve2 stations gasoline)
  (let ((len (length stations)))
    (let loop ((tank 0) ; gallons in tank
               (min-tank #e1e100) ; minimum gallons so far
               (start 0) ; current starting position
               (pos 1) ; current position
               (stations stations) (gasoline gasoline))
      (if (null? stations)
          (if (negative? tank) #f start)
          (let ((tank (+ tank (car stations) (- (car gasoline)))))
            (if (< tank min-tank)
                (loop tank tank (modulo pos len) (+ pos 1)
                      (cdr stations) (cdr gasoline))
                (loop tank min-tank start (+ pos 1)
                      (cdr stations) (cdr gasoline))))))))

> (solve2 '(15 8 2 6 18 9 21 30) '(8 6 30 9 15 21 2 18))
6
> (solve2 '(15 8 2 6 18 9 21 29) '(8 6 30 9 15 21 2 18))
#f

We index through the stations, keeping track of how much gasoline is in the tank, with the initial starting position at the first station. When we have a new minimum amount of gasoline in the tank, we reset the minimum and record a new starting position; otherwise, we keep the current minimum and starting position and move to the next station. If there is gasoline in the tank after we have indexed all the stations, we report the current starting position, otherwise we report failure.

This solution is obviously linear in time, as it indexes each station once, and constant in space, with only four variables in addition to the input. You can run the program at http://ideone.com/UIFtOW.

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 )

Google photo

You are commenting using your Google 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 )

Connecting to %s

%d bloggers like this: