We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Data Structures
  3. Queues
  4. Truck Tour
  5. Discussions

Truck Tour

Sort by

recency

|

364 Discussions

|

  • jakubsliwice
     + 0 comments
    def truckTour(petrolpumps):
    ln = len(petrolpumps)
    
    petrolpumps = [x - y for x, y in petrolpumps]
    
    for i in range(ln):
        sm = 0
        for j in range(ln):
            sm += petrolpumps[(i + j) % ln]
            if sm < 0:
                break
        else:
            return i
    return -1

  • al_bayona
     + 0 comments

    The problem is misleading, as it does not crearly states that there will always be a solution. You are led to believe to check if you go the full circle. You usually are taught to think of all scenarios, including no solution. So this was a very vague problem description. Finally, I was able to do it by using a prefix list in O(n) time, by using tabulation to optimize checking all the posible circles. 

    def truckTour(petrolpumps):
    _prefix = [ x[0] - x[1] for x in petrolpumps]
    _min = [0] * len(_prefix)
    _min2 = [0] * len(_prefix)

    print(_prefix)

    for i in range(1, len(_prefix)):
        _prefix[i] += _prefix[i-1]

    for i in range(len(_prefix)):
        if i == 0:
            _min[-(i+1)] = _prefix[-(i+1)]
            _min2[i] = _prefix[i]
        else:
            _min[-(i+1)] = min(_min[-i], _prefix[-(i+1)])
            _min2[i] = min(_min2[i-1], _prefix[i])

    # print(_prefix)
    # print(_min)
    # print(_min2)



    if _min[0] > 0:
        return 0

    for i, n in enumerate(_prefix):
        if i > 0:
            if _min[i] - _prefix[i-1] > 0 and _min2[i] + _prefix[-1] - _prefix[i-1] > 0:
                print(i)
                return i

  • manceraaxel
     + 0 comments
    def truckTour(petrol_pumps):
    start_index = 0
    total_liters = 0
    total_distance = 0

    for i in range(len(petrol_pumps)):
        liters, distance = petrol_pumps[i]
        total_liters += liters
        total_distance += distance
        # Arriving to next petrol pump

        if total_liters - total_distance < 0:
            # Initialize start index before restarting in start index
            start_index = i + 1
            total_liters = 0
            total_distance = 0
    
    return start_index

  • zyzz15620
     + 1 comment

    Imo this is very easy

    1. Loop through every pump
    2. Check if a pump has more petrol than the kilometer (1st condition)
    3. Test that pump. If during the tour, the remaining fuel >= 0 (2nd condition)
    4. Return index of the pump that passed 2 conditions note: remaining fuel = fuel - distance (kilometer)

    The challenge is how to test 2nd condition. If you want to test a pump number 2, than it need to go through [2 > 3 > 4 > 5 > 1] if there is 5 pumps. If during testing and that specific pump's remaining fuel get to below 0 than skip that pump

  • sivasubramaniy24
     + 0 comments

    def truckTour(petrolpumps):

    petrolRest = [pump[0]-pump[1] for pump in petrolpumps] * 2

for i in range(len(petrolpumps)):

    tank = 0

    for j in range(i, i + len(petrolpumps)):

        tank += petrolRest[j]

        if tank < 0: break     

    if tank < 0: continue

    else: return i

return -1