Created
June 7, 2016 06:13
-
-
Save 0ex-d/44277e4537ec9cb794cbc72218c49cc3 to your computer and use it in GitHub Desktop.
A quick implementation of algorithms in gas stations
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Gas(): | |
"""Gas lookup optimization""" | |
def __init__(self, gas, cost): | |
self.gas = gas | |
self.cost = cost | |
def canCompleteCircuit(self): | |
n = len(self.gas) | |
start = 0 | |
total = 0 | |
tank = 0 | |
for i in range(0, n): | |
dif = self.gas[i] - self.cost[i] | |
tank += dif # extra fuel in tank | |
total += dif | |
if (tank < 0): | |
start = i + 1 # should start from next | |
tank = 0 # empty the tank | |
# if total cost is larger than total gas, then impossible | |
return -1 if total < 0 else start | |
checkStations = Gas([100,10,56], [200, 400, 500]) | |
print (checkStations.canCompleteCircuit()) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment