Car Fueling Problem by Greedy Algorithm (getting list index out of range)

Question

I have a small problem solving the Car fueling problem using the Greedy Algorithm.

Problem Introduction

You are going to travel to another city that is located 𝑑 miles away from your home city. Your car can travel at most 𝑚 miles on a full tank and you start with a full tank. Along your way, there are gas stations at distances stop1, stop2, ... , stopN from your home city. What is the minimum number of refills needed?

Input:

950
400
4
200 375 550 750

Output:

2

What I've tried as of now

def car_fueling(dist,miles,n,gas_stations):
  num_refill, curr_refill, last_refill = 0,0,0
  while curr_refill <= n:
    last_refill = curr_refill
    while (curr_refill <= n-1) & (gas_stations[curr_refill + 1] - gas_stations[last_refill] <= miles):
        curr_refill += 1
    if curr_refill == last_refill:  
      return -1
    if curr_refill <= n:
      num_refill += 1
  return num_refill

What is the problem I'm facing

In the statement

while (curr_refill <= n-1) & (gas_stations[curr_refill + 1] - gas_stations[last_refill] <= miles)

I am getting the error IndexError: list index out of range. It is because of gas_stations[curr_refill + 1]. So when I try to separate it as a while loop and an if statement as in

while (curr_refill <= n-1):
    if (gas_stations[curr_refill + 1] - gas_stations[last_refill] <= miles):
        curr_refill += 1
    else:
        break

It is entering an infinite loop.

Can you kindly point out the mistake I'm facing?

Answer 1

A few issues:

• & is not the boolean and-operator. Use and
• curr_refill + 1 can be n, and hence produce the error you got. Note that the distance after the last gas station can be determined using dist
• The value of last_refill is wrong from the start: you did not refill (yet) at station 0, so it should not be initialised as 0. Instead use another variable that represents how far you can currently drive.

Corrected code:

def car_fueling(dist,miles,n,gas_stations):
    num_refill, curr_refill, limit = 0,0,miles
    while limit < dist:  # While the destination cannot be reached with current fuel
        if curr_refill >= n or gas_stations[curr_refill] > limit:
            # Cannot reach the destination nor the next gas station
            return -1
        # Find the furthest gas station we can reach
        while curr_refill < n-1 and gas_stations[curr_refill+1] <= limit:
            curr_refill += 1
        num_refill += 1  # Stop to tank
        limit = gas_stations[curr_refill] + miles  # Fill up the tank 
        curr_refill += 1
    return num_refill

# Test cases
print(car_fueling(950, 400, 4, [200, 375, 550, 750]))  # 2
print(car_fueling(10, 3, 4, [1, 2, 5, 9]))  # -1