Styjun

The problem is the following :

• You are going to travel to another city that is located d miles away
  from your home city.


• You can travel at most m 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?

So far I have come up with the following:

def min_refills(distance, tank, stops):
 i = 0 # counter for the current stop
 distance_driven = 0
 count_stops = 0
 stops.append(100000000000) # using this to avoid an out of index error for the second while loop
 while tank + distance_driven < distance: # check if goal state is achieved
 if tank + distance_driven < stops[i + 1]:
 return -1 # returned if a distance is unreachable
 else:
 while tank + distance_driven >= stops[i]: # greedy assumption to "full-up" at the furthest reachable gas station
 i = i + 1
 i = i - 1
 distance_driven = stops[i]
 count_stops = count_stops + 1
 return count_stops

This is my implementation of a greedy algorithm.

The Input is read from the command line in the following format:

950 400 4 200 375 550 750

where the first the first number refers to d (distance), the second refers to t (the tank), the third to n (the number of gas stations on the way) and the other numbers show the locations of n gas stations.

The output will return an integer with the minimum refills needed to reach the distance:

2

In the example the distance between the cities is 950, the car can travel at most 400 miles on a full tank. It suffices to make two refills: at points 375 and 750. This is the minimum number of refills as with a single refill one would only be able to travel at most 800 miles.

Maybe the real question is how can I test my algortihm for mistakes ?