Calculate if the train can pass over the bridge

Question

The bridge's length and load-carrying capacity are known. Each of the train's wagons has a given length and weight. Program must determine whether the train can safely cross the bridge, i.e. whether the total weight of wagons that will simultaneously be on the bridge exceeds the bridge's carrying capacity. To be safe, if any part of a wagon is on the bridge, we will count the entire weight of that wagon in computing the total weight at that moment.

Input format:

The first input line contains two integers: the length of the bridge and its carrying capacity.

The following input line(s) contain a sequence of pairs indicating the length and weight of each wagon in sequence. Each wagon's length and weight will always appear on the same line. Each input line will be at most 200 characters long.

Output:

If the train can safely cross the bridge, write the number -1. Otherwise, write the number of the first wagon that will cause the weight to exceed the bridge's carrying capacity. Wagons are numbered from 1.

Sample input #1:

10 100

10 90 10 10 9 80 1 10 9 10 9 80

5 10 5 10

1 10 1 10 1 10 1 10 1 40

Output:

-1

Sample input #2:

7 20

3 4 3 5

3 5 3 7

3 7 3 7

3 6

Output:

4

Some more examples:

Input:

5 10

5 5 5 5 5 5 5 5 5 5 5 100 5 100 5 100

Output:

6

My code is

def bridge(p, k,  n):
    if p or n == 0:
        print(-1)
    else:
        wagon_length(lenght, wagon_lenght, p, n, k)
        
def wagon_length(lenght, wagon_lenght, p, n, k):
    lenght = lenght - wagon_lenght[n]
    wagon_lenght.remove(wagon_lenght[n])
    k = k+1
    if lenght > 0:
        n = n-1
        wagon_length(lenght, wagon_lenght, p, k, n)
       
    elif lenght <= 0:
        n = n-k
        wagon_mass(weight, wagon_weight, p, k, n)
        
              
def wagon_mass(weight, wagon_weight, p, k, n):
    res = sum(wagon_weight[-k:])
    weight = weight - res
    p = p - k
    wagon_weight.remove(wagon_weight[p])
    k = 0
    if weight < 0:
        print(p)
    if weight >= 0:
        bridge(p, k, n)        

a = input()
lines = []
while True:
    line = input()
    if line:
        lines.append(line)
    else:
        break
text = '\n'.join(lines)
bbh = [int(t) for t in text.split()]
arr = [int(d) for d in a.split()]

k = 0
weight = arr[1]
lenght = arr[0]
wagon_weight = bbh[1::2]
wagon_lenght = bbh[0::2]
n = len(wagon_lenght)-1
p = len(wagon_weight)-1


bridge(p, k, n)

I tried to make it so that every time a wagon hits the bridge, we add one to the number k, which means the number of wagons that are currently on the bridge, and then just calculate the total weight of this number of wagons and subtract them from the maximum values ​​- if the weight is greater than or equal to zero, then these wagons have passed.

But the mistake of my code is that when operations are performed with list, instead of the last wagons (I go from the last to the first), it deletes the smallest values ​​and the code does not work as I intended

Answer 1

To avoid excessive memory use, you should not go for a solution where each unit of length is checked (like each meter if the unit if measure is meter). Instead go through the process of adding wagons at the end and removing them from the start.

As the weight of a wagon also counts when it is only touching the bridge, it will be useful to keep track of the the length and load with the following definitions:

• length: represents the total length of a range of wagons that fit entirely on the bridge
• load: represents the total weight of a range of wagons where the first and last wagon might not be completely on the bridge.

I would adapt the loading of data such that you don't need to zip to lists. Instead keep each wagon's length and weight together in a tuple. I would promote the use of named tuples here, since that improves the readability of the code.

As both the bridge and each wagon have a length and something that relates to weight, I would use the same named tuple class for both.

Here is the proposed code:

from collections import namedtuple

# Use named tuple to improve readability of the code
Item = namedtuple("Item", "length, weight")

def support(bridge, wagons):
    # Deal with boundary cases
    if not bridge.length or not wagons:
        return -1

    # initialise the total length of wagons that are completely on the bridge 
    length = 0
    # .... and the total weight of wagons that touch the bridge
    load = wagons[0].weight
    # Some more boundary cases
    if load > bridge.weight:
        return 1
    if len(wagons) == 1:
        return -1
    load += wagons[1].weight
    if load > bridge.weight:
        return 2

    # The following loop has this invariant:
    #    load = sum( wagon.weight for wagon in wagons[start-1:end+1] )
    #    length = sum ( wagon.length for wagon in wagons[start:end] )
    start = 1
    for end in range(1, len(wagons) - 1):
        # Remove first wagon(s) as long there is no room for the next wagon to 
        #    be partly on the bridge while also the first is still partly on the bridge
        while length + wagons[end].length >= bridge.length:
            load -= wagons[start - 1].weight
            length -= wagons[start].length
            start += 1
        # Now there is room for the next wagon...
        length += wagons[end].length
        load += wagons[end + 1].weight
        if load > bridge.weight:  # Exceeded the capacity of the bridge
            return end + 2
    
    return -1


# Helper functions to parse the input
def read_words_until_empty_line():
    line = input()
    while line:
        yield from line.split()
        line = input()

def words_to_items(words):
    it = map(int, words)
    for length in it:
        yield Item(length, next(it))

# Driver code
bridge, *wagons = words_to_items(read_words_until_empty_line())
print(support(bridge, wagons)) 

Answer 2

You could convert the sequence of wagons into sequences of added and removed weights for each meter of the train's length. The two sequences would be offset by the length of the bridge so that you can add them together and get the total load on the bridge every time the train moves by one meter. The accumulate function from itertools can help with computing the total load at each meter:

from itertools import accumulate

def support(bridge,capacity,wagons):
    index  = [i for i,(wl,_) in enumerate(wagons,1) for _ in range(wl)]
    start  = accumulate(w for wl,ww in wagons 
                        for w in [ww]+[0]*(wl-1))
    end    = accumulate(-w for wl,ww in [(bridge,0)]+wagons 
                        for w in [0]*(wl-1)+[ww])
    load   = map(sum,zip(start,end))
    return next((index[m] for m,w in enumerate(load) if w>capacity),-1)

Output:

bridge   = 10
capacity = 100
wagons   = [(10,90),(10,10),(9,80),(1,10),(9,10),(9,80),(5,10),(5,10),
            (1,10),(1,10),(1,10),(1,10),(1,40)]
print(support(bridge,capacity,wagons)) # -1

bridge   = 7
capacity = 20
wagons   = [(3,4),(3,5),(3,5),(3,7),(3,7),(3,7),(3,6)]
print(support(bridge,capacity,wagons)) # 6

bridge   = 5
capacity = 10
wagons   = [(5,5),(5,5),(5,5),(5,5),(5,5),(5,100),(5,100),(5,100)]
print(support(bridge,capacity,wagons)) # 6

For example:

bridge   = 7
capacity = 20
wagons   = [(3,4),(3,5),(3,5),(3,7),(3,7),(3,7),(3,6)]

• index will contain the id of the wagon that is added on the bridge at the corresponding meter position
• start is the cumulative sum of wagon weights for wagons that are added on the bridge
• end is the cumulative sum of wagon weights for wagons that leave the bridge (negative)
• load is the actual load (added - leaving) on the bridge when the corresponding meter of the train reaches the bridge.
• After the last wagon is added on the bridge, is is not necessary to further check capacity as the load will only decrease thereafter

...

index 1 1 1 2 2 2  3  3  3  4  4  4  5  5  5   6   6   6   7   7   7
enter 4 0 0 5 0 0  5  0  0  7  0  0  7  0  0   7   0   0   6   0   0
(leaving)                   1  1  1  2  2  2   3   3   3   4   4   4 ...
leave 0 0 0 0 0 0  0  0  0 -4  0  0 -5  0  0  -5   0   0  -7   0   0 ...
start 4 4 4 9 9 9 14 14 14 21 21 21 28 28 28  35  35  35  41  41  41
end   0 0 0 0 0 0  0  0  0 -4 -4 -4 -9 -9 -9 -14 -14 -14 -21 -21 -21 ...
load  4 4 4 9 9 9 14 14 14 17 17 17 19 19 19  21  21  21  20  20  20

                                               ^
                          Overload here _______|

without libraries (same logic)

def support(bridge,capacity,wagons):
    index = (i for i,(wl,_) in enumerate(wagons,1) for _ in range(wl))
    enter = (w for wl,ww in wagons for w in [ww]+[0]*(wl-1))
    leave = (w for wl,ww in [(bridge,0)]+wagons for w in [0]*(wl-1)+[ww])
    load = 0                                   # current load on bridge
    for i,more,less in zip(index,enter,leave): # examine each meter
        load += more-less                      # track total weigth
        if load>capacity: return i             # detect overload
    return -1

memory efficient solution using a queue

def support(bridge,capacity,wagons):
    onBridge = deque([(bridge,0)])         # wagons/weights on bridge
    load = 0                               # current load
    for i,(wl,ww) in enumerate(wagons,1):  
        load += ww                         # combined load (continuous)
        if load>capacity: return i         # check overload
        onBridge.append((wl,ww))           # add wagon on bridge
        while wl>0:                        # advance to end of wagon
            bl,bw = onBridge[0]            
            if wl>=bl:                     # reduce load for exiting
                load -= onBridge.popleft()[1]
            else:                          # reduce length for partial
                onBridge[0] = (bl-wl,bw)
            wl -= bl                       # up to new wagon's length
    return -1 

Answer 3

I haven't proved my solution. There might be some redundant code.

My code will return the index (0 based indexing) of 1st wagon which will cause the issue if you want the last just update the recursion:

• my code will return -1 if bridge is not destroyed.
• my code will return (index,'s') means the partial wagon at start will cause the destruction
• my code will return (index,'e') means the partial wagon at end will cause the destruction
• my code will return (index,'f') means the full wagon at start will cause the destruction

My code :

""" 
    - either wagon is fully on the bridge
    - or partially placed on the bridge
        - if partially place on the bridge:
            * wagon is at starting point
            * wagon is at last point
"""
import sys
sys.setrecursionlimit(10**8)

def move(wagonList, n , wagon , maxL, i, counter):
    weight = wagon[1]
    for j in range(i, n if counter > 0 else -1, counter):
        if((maxL - wagonList[j][0])  <= 0):
            weight += wagonList[j][1]
            break
        maxL -= wagonList[j][0]
        weight += wagonList[j][1]
    return weight
def moveCombo(wagonList, n , w , maxL, i,j):
    if(i < 0 or j >= n or maxL <= 0):
        return w
    #return max(moveCombo(wagonList, n , w+wagonList[j][1] , maxL-wagonList[j][0], i,j+1),moveCombo(wagonList, n , w+wagonList[i][1] , maxL-wagonList[i][0], i-1,j))    
    return max(moveCombo(wagonList, n , w+wagonList[j][1] , maxL-wagonList[j][0], i,j+1),
        max(moveCombo(wagonList, n , w+wagonList[i][1] , maxL-wagonList[i][0], i-1,j),
        moveCombo(wagonList, n , w+wagonList[j][1]+wagonList[i][1] , maxL-wagonList[j][0]-wagonList[i][0], i-1,j+1)
        ))
def Gwagon(wagonList, n , maxL, maxW):
    res = []
    for i in range(n):
        wagon = wagonList[i]
        end = move(wagonList, n, wagon, maxL, i-1, -1) 
        start = move(wagonList, n, wagon, maxL, i+1, 1)
        full = moveCombo(wagonList, n , wagon[1] , maxL-wagon[0], i-1, i+1)
        if(start > maxW):
            res.append((i,'s'))
        if(end > maxW):
            res.append((i,'e'))
        if(full > maxW):
            res.append((i,'f'))
        if(res):
            break
    return res

def result(wagonList,n,maxL,maxW):
    res = Gwagon(wagonList,n,maxL,maxW)
    if(res):
        print(*res)
    else:
        print(-1)

wagonList=[(10,90),(10,10),(9,80),(1,10),(9,10),(9,80),(5,10),(5,10),(1,10),(1,10),(1,10),(1,10),(1,40)]
result(wagonList,13,10,100)
wagonList=[(3,4),(3,5),(3,5),(3,7),(3,7),(3,7),(3,6)]
result(wagonList,7,7,20)
    

    

My Output:

-1
(0, 's')

• our case 1 the bridge will not be destroyed so -1.
• our case 2 the bridge will be destroyed, 1st wagon will be wagon no-1 {4,5,5,7}. wagon -1 will be the starting point and bridge will be destroyed if wagon is partial on the bridge.

New Code:

""" 
    - either wagon is fully on the bridge
    - or partially placed on the bridge
        - if partially place on the bridge:
            * wagon is at starting point
            * wagon is at last point
"""
import sys
sys.setrecursionlimit(10**8)

def move(wagonList, n , wagon , maxL, i, counter):
    weight = wagon[1]
    obj = (weight,i-counter)
    for j in range(i, n if counter > 0 else -1, counter):
        if((maxL - wagonList[j][0])  <= 0):
            weight += wagonList[j][1]
            obj = (weight, j)
            break
        maxL -= wagonList[j][0]
        weight += wagonList[j][1]
    return obj
def moveCombo(wagonList, n , w , maxL, i,j, maxW):
    if(i < 0 or j >= n or maxL <= 0 or maxW < w):
        return (w,j-1)
        
    o1 = moveCombo(wagonList, n , w+wagonList[j][1] , maxL-wagonList[j][0], i,j+1, maxW)
    o2 = moveCombo(wagonList, n , w+wagonList[i][1] , maxL-wagonList[i][0], i-1,j ,maxW)
    o3 = moveCombo(wagonList, n , w+wagonList[j][1]+wagonList[i][1] , maxL-wagonList[j][0]-wagonList[i][0], i-1,j+1, maxW)
    res = (0,n+1)
    if(o1[0] > maxW):
        res = o1
    if(o2[0] > maxW):
        if(res[1] > o2[1]):
            res = o2
    if(o3[0] > maxW):
        if(res[1] > o3[1]):
            res = o3
    return res
    
def Gwagon(wagonList, n , maxL, maxW):
    res = []
    for i in range(n):
        wagon = wagonList[i]
        end = move(wagonList, n, wagon, maxL, i-1, -1) 
        start = move(wagonList, n, wagon, maxL, i+1, 1)
        full = moveCombo(wagonList, n , wagon[1] , maxL-wagon[0], i-1, i+1, maxW)
        if(start[0] > maxW):
            res.append((start[1],'s'))
        if(end[0] > maxW):
            res.append((end[1],'e'))
        if(full[0] > maxW):
            res.append((full[1],'f'))
        if(res):
            break
    return res

def result(wagonList,n,maxL,maxW):
    res = Gwagon(wagonList,n,maxL,maxW)
    if(res):
        res.sort()
        print(res[0][0]+1)
    else:
        print(-1)

wagonList=[(10,90),(10,10),(9,80),(1,10),(9,10),(9,80),(5,10),(5,10),(1,10),(1,10),(1,10),(1,10),(1,40)]
result(wagonList,13,10,100)
wagonList=[(3,4),(3,5),(3,5),(3,7),(3,7),(3,7),(3,6)]
result(wagonList,7,7,20)

OUTPUT:

-1
4