gistfile1.py

def canComplete(gas, cost):
    
    # number of stations
    total = len(gas)
    
    # Overall iteration count
    iteration = 0
    
    # Current eligible racer
    racer = None
    
    # Cache of required gas
    cache = {}
    
    while True:
        
        # Index of current and next station
        current = iteration       % total
        next    = (iteration + 1) % total
        
        # If there's no current racer, set one off from the current station
        if not racer:
            racer = {
                'start':   current,
                'station': current,
                'gas':     0
            }
            
        # Can we use a previous calculation to skip a few iterations?
        if (racer['station'], racer['start']) in cache:
            next     = racer['start']
            nextCost = cache[(racer['station'], racer['start'])]
        
        # Otherwise calculate cost to the very next index
        else:
            nextCost = gas[current] - cost[current]
        
        # Update the racer's gas level to reach the next station
        racer['gas'] += nextCost
        
        # Update the cache
        cache[(racer['start'], next)] = racer['gas']
        
        # If our racer has gas, he can continue to the next station 
        if racer['gas'] >= 0:
            racer['station'] = next
            
            # If we're back at the start of the race, we won
            if racer['station'] == racer['start']:
                return racer['start']
        
        # Otherwise, we find a new starting position
        else:
            racer = None
            
            # If we reached the final station without a racer, the race is not completable
            if next == 0:
                return -1
                
        # Onwards to the next iteration
        iteration += 1