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
10, and each of the bridges has a number of cars over them, also from
- 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
B (which we'll call
3 capacity, and let's say you're on
A, and want to take
1 material. To take the material, simply cross from
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.
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
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
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
AB has a capacity of
AC has a capacity of
BD has a capacity of
5 cars, and
CD has a capacity of
Rules / Specs:
- Your program must work for, at least,
10 * 10grids.
- 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.
[[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 code-golf, so shortest code in bytes wins!