Problem 45470. Count the number of reaction chains achievable in T mins
This problem is related to Problem 45467.
Let's denote a list of N compounds as 1, 2, ..., N. You are then given a list of valid reactions for converting one compound to another (e.g. 1 --> 2), as well as the time it takes to complete them ( completion time ). With this information, we can generate reaction chains. A reaction chain is a series of valid reaction steps taken one after the other. Examples are given below:
Given N = 4 and the following valid reactions: Reaction 1: 1 --> 2 takes 1.5 mins Reaction 2: 1 --> 3 takes 2.5 mins Reaction 3: 2 --> 3 takes 0.6 mins Reaction 4: 3 --> 4 takes 4.1 mins Reaction 5: 4 --> 2 takes 3.2 mins Sample reaction chains: 1 --> 3 --> 4 takes (2.5 + 4.1) mins 1 --> 2 --> 3 --> 4 takes (1.5 + 0.6 + 4.1) mins 4 --> 2 --> 3 takes (3.2 + 0.6) mins
Note that conversion reactions can only move forward. But if the list states that converting to and from the same two compounds is possible, then a reaction chain can take only one of these paths.
Your task is this: Given a starting compound S, can you count how many reaction chains are possible whose total completion time does not exceed T mins?
Note that if multiple valid reaction steps are possible between two compounds (e.g. "1 --> 2 takes 1.5 mins" and "1 --> 2 takes 2.5 mins" both appear in the list), then reaction chains that take either of these paths are distinct. Lastly, for this problem, reaction chains must not contain duplicate compounds; otherwise, they become "cycles" rather than "chains".
The inputs to this problem are R, S, and T. The meanings of S and T are given above. Variable R is a 3-column matrix containing the list of valid reaction steps at each row i:
"Reaction i: R( i, 1) --> R( i, 2) takes R( i, 3) mins"
Output the required number of reaction chains. You are ensured that:
- N and T are integers satisfying: 2 <= N <= 20 and 1 <= T <= 100.
- S and all elements in the first 2 columns of R are integers within [1, N].
- Completion times are decimal numbers within (0,10].
- Each compound 1, ..., N is mentioned at least once in R. Hence, N can be inferred from matrix R.
The following sample test case is the one illustrated above:
>> R = [1 2 1.5; 1 3 2.5; 2 3 0.6; 3 4 4.1; 4 2 3.2]; >> reaction_chain2(R,1,5) ans = 3 >> reaction_chain2(R,1,10) ans = 6
In this example, all the reaction chains starting from Compound 1 are:
(1.50 mins) 1 --> 2 (2.10 mins) 1 --> 2 --> 3 (6.20 mins) 1 --> 2 --> 3 --> 4 (2.50 mins) 1 --> 3 (6.60 mins) 1 --> 3 --> 4 (9.80 mins) 1 --> 3 --> 4 --> 2
Solution Stats
Problem Comments
Solution Comments
Show commentsProblem Recent Solvers13
Suggested Problems
-
6258 Solvers
-
Longest run of consecutive numbers
5613 Solvers
-
255 Solvers
-
203 Solvers
-
349 Solvers
More from this Author19
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!