Cody

Problem 45462. Propagate the effects of a blockage in a chemical plant

From the perspective of flow, a chemical plant can be described by a collection of nodes and edges. Nodes are points where multiple flows meet, such as mixing points, splitting points, or plant equipment that process the flows, whereas edges are the pipe connections between the nodes.

For a chemical plant with N nodes, we can use an adjacency matrix of size N x N to represent the topology. For any adjacency matrix M,

M(i,j) = 1, if a pipe connection exists between Node i and Node j;
       = 0, otherwise.

M is always a symmetric matrix because if a pipe exists from Node i to Node j, then the same pipe exists from Node j to Node i. Also, elements in the diagonal are always zero since a node cannot connect to itself. Not shown in matrix M are the edges that connect the plant to the outside world. Here, we will simply assume that these edges exist to provide continuous flow to all the nodes.

However, the plant does not need to be fully connected; some nodes may be unreachable from other nodes by piping. Hence, if the flow was suddenly blocked inside the equipment at Node P, then it may affect only the nodes reachable from P. The effect of blockage can propagate from one node to another node if and only if there exists a series of piping that connects them (i.e., blockage effects have no regard for the direction of flow in a pipe).

Given an adjacency matrix M and the value of P, can you tell how much of the plant may be affected when a blockage occurs at Node P? Write a function that accepts variables M and P. You are ensured that 2 <= N <= 30, and 1 <= P <= N. Output a string (with no newline characters) with the format:

Node P blocked! It may affect X% of the plant.

where P is the given value of P and X is a floating-point number rounded to 2 decimal places, which is computed as the "number of affected nodes" divided by the "total number of nodes", and given as a percentage. Note that if Node P happens to be isolated from all other nodes, then there is exactly 1 affected node.

See sample test cases:

>> M = [0 0 1 0 0 0 0 0 0 0
        0 0 0 0 0 0 1 0 0 0
        1 0 0 0 1 0 0 0 0 0
        0 0 0 0 1 1 0 0 0 0
        0 0 1 1 0 0 0 0 0 0
        0 0 0 1 0 0 0 0 0 1
        0 1 0 0 0 0 0 1 0 0
        0 0 0 0 0 0 1 0 1 0
        0 0 0 0 0 0 0 1 0 0
        0 0 0 0 0 1 0 0 0 0];
>> propagate_blockage(M,2)
ans = 
   'Node 2 blocked! It may affect 40.00% of the plant.'
>> M = [0 1 0 0 0 0 0 0 0 0
        1 0 0 0 0 0 0 0 0 0
        0 0 0 0 0 0 0 0 1 0
        0 0 0 0 1 0 0 0 0 0
        0 0 0 1 0 1 0 0 0 0
        0 0 0 0 1 0 0 0 0 0
        0 0 0 0 0 0 0 1 0 0
        0 0 0 0 0 0 1 0 1 0
        0 0 1 0 0 0 0 1 0 1
        0 0 0 0 0 0 0 0 1 0];
>> propagate_blockage(M,4)
ans = 
   'Node 4 blocked! It may affect 30.00% of the plant.'

For a visualization of the above cases, see figure here: https://drive.google.com/open?id=1g63o4tvoF_89fNKuoCOs2YzfezktjD3Z

Solution Stats

87.5% Correct | 12.5% Incorrect
Last Solution submitted on May 15, 2020

Problem Comments