# Don't break the bridges!

## Introduction:

You are a worker, who is in charge of managing a set of bridges, connecting a square grid of "nodes":

N - N - N
|   |   |
N - N - N
|   |   |
N - N - N


(the grid here is 3 by 3, but they can be larger).

Each of the bridges has a set capacity from 1 to 10, and each of the bridges has a number of cars over them, also from 1 to 10.

• If a bridge has a higher capacity than the number of cars on that bridge, then it is considered "safe", and you can cross over it.
• If a bridge's capacity and number of cars going over it are equal, then it is considered "stable". It won't collapse, but you can't cross over it.
• If a bridge has a lower capacity than the number of cars on that bridge, then it is considered "collapsing", and you only have a limited amount of time to fix it.

When a bridge has n capacity and m cars, with n smaller than m, the time it takes to collapse is:

      m + n
ceil( ----- )
m - n


You must take materials (and therefore reduce the bridge's capacity) from other bridges and arrive to those bridges on time to fix them! To get materials from a bridge, you must cross over it. For example, take this small arrangement:

A - B


The bridge between A and B (which we'll call AB) has 3 capacity, and let's say you're on A, and want to take 1 material. To take the material, simply cross from A to B.

Note: You don't have to cross the bridge multiple times to get multiple materials, you can take as much material as you want from a bridge in one go, as long as it doesn't cause the bridge to start to collapse.

Now, AB has 2 capacity, and you have 1 material on you. You may only cross over bridges that are "safe", though (or if you're fixing a bridge, which is explained in the next paragraph).

To fix a bridge, you must go over it, thereby depositing all materials needed to fix the bridge. For example, in the example above, if AB had 1 capacity and 2 cars currently on it, and you had 2 material on you, once you cross the bridge you will have 1 material, because that is all that's required to fix the bridge.

You must fully cross a collapsing bridge before the bridge collapses, otherwise it will break. Each crossing of a bridge takes 1 hour, and the time it takes for the bridge to collapse is shown in the formula above. For example:

A
|
B
|
C - D


In this example, if your starting node was A, and CD only had a "lifespan" of 2 hours, the bridge would collapse before you can get to it (crossing AB takes 1 hour, crossing BC takes another hour).

Your task is to make a program that calculates, given a list of bridges, which are represented themselves as lists of two elements (first element is capacity, second element is cars on the bridge), whether or not it's possible to fix all of the bridges. The bridges work from top-to-bottom, left-to-right - so an input of

[[3 2] [3 2] [2 5] [5 1]]


means that the actual grid looks like this:

    3
A --- B
|  2  |
3|2   2|5
|  5  |
C --- D
1


So AB has a capacity of 3 and 2 cars, AC has a capacity of 3 and 2 cars, BD has a capacity of 2 and 5 cars, and CD has a capacity of 5 and 1 car.

## Rules / Specs:

• Your program must work for, at least, 10 * 10 grids.
• Your program may accept the input as either a string with any delimiter, or a list of lists (see example I/O).
• Your program must output the same value for true for all true values, and it must output the same value for false for all false values.
• You can either submit a full program or a function.

## Example I/O:

[[5 5] [5 5] [1 1] [3 3]] => true
[[2 5] [2 2] [3 3] [1 2]] => false
[[3 2] [3 2] [2 5] [5 1]] => true

NOTE, you can take the input like this as well:
[[3, 2], [3, 2], [2, 5], [5, 1]] (Python arrays)
3,2,3,2,2,5,5,1                  (Comma-separated string)
3 2 3 2 2 5 5 1                  (Space-separated string)


This is , so shortest code in bytes wins!

• If you want to take multiple materials from the same bridge, do you have to cross it multiple times? May 22, 2017 at 9:07
• @GregMartin Sorry for the late reply - no, you don't have to cross it multiple times. May 22, 2017 at 9:48
• Can you only fix it to just enough?
– l4m2
May 24, 2018 at 8:01

# Python3, 560 bytes:

R=range
def V(b,x,y,X,Y):
try:return[(b[x][y],b[x+X][y+Y])]
except:return[]
def f(r):
K,w=0,int(len(r)**.5);b=[[K:=K+1for _ in R(w)]for _ in R(w)];e=dict(zip([l for x in R(w)for y in R(w)for l in V(b,x,y,0,1)+V(b,x,y,1,0)],r));q=[(e,0)]
while q:
e,c=q.pop(0);E=e.values()
if all(a>=b for a,b in E):return 1
if c<min(-(-((b+a)/(b-a))//1)for a,b in E if a<b):
for(j,k),(a,b)in e.items():
if a>b:
for J,K in e:
if(j,k)!=(J,K)and{j,k}&{J,K}:
for s in R(a-b):
Q=eval(str(e));Q[j,k][0]-=s;Q[J,K][0]+=s;q+=(Q,c+1),
return 0


Try it online!

• 560 May 21, 2022 at 1:01
• 542 with horrible abuse May 21, 2022 at 1:24
• (j,k)!=(J,K)and{j,k}&{J,K}->len({j,k}&{J,K})==1? Seems fine on the test cases, but I can't follow the logic well enough to tell if there's any case where (j,k)==(K,J) where it would be incorrect May 22, 2022 at 5:48