Calculate if the train can pass over the bridge-CodePudding

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

CodePudding user response：

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

CodePudding user response：

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