Skip to content

Instantly share code, notes, and snippets.

@0ex-d
Created June 7, 2016 06:13
Show Gist options
  • Save 0ex-d/44277e4537ec9cb794cbc72218c49cc3 to your computer and use it in GitHub Desktop.
Save 0ex-d/44277e4537ec9cb794cbc72218c49cc3 to your computer and use it in GitHub Desktop.
A quick implementation of algorithms in gas stations
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