Problem 45467. Find the fastest reaction chain to reach a target compound

Created by Karl Ezra Pilario

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>This problem is related to Problem</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"45470\"><w:r><w:t>45470</w:t></w:r></w:hyperlink><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Let's denote a list of</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>N</w:t></w:r><w:r><w:t> compounds as 1, 2, ...,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>N</w:t></w:r><w:r><w:t>. You are then given a list of valid reactions for converting one compound to another (e.g. 1 --&gt; 2), as well as the time it takes to complete them (</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>completion time</w:t></w:r><w:r><w:t> ). With this information, we can generate</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>reaction chains</w:t></w:r><w:r><w:t>. A reaction chain is a series of valid reaction steps taken one after the other. Examples are given below:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[Given N = 4 and the following valid reactions:\nReaction 1: 1 --> 2 takes 1.5 mins\nReaction 2: 1 --> 3 takes 2.5 mins \nReaction 3: 2 --> 3 takes 0.6 mins\nReaction 4: 3 --> 4 takes 4.1 mins \nReaction 5: 4 --> 2 takes 3.2 mins\nSample reaction chains: 1 --> 3 --> 4 takes (2.5 + 4.1) mins\n 1 --> 2 --> 3 --> 4 takes (1.5 + 0.6 + 4.1) mins \n 4 --> 2 --> 3 takes (3.2 + 0.6) mins]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>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.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Your task is this: Given a starting compound</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>S</w:t></w:r><w:r><w:t> and a target compound</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>T</w:t></w:r><w:r><w:t>, can you find a reaction chain between them with the smallest</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>total completion time</w:t></w:r><w:r><w:t>?</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The inputs to this problem are</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>R</w:t></w:r><w:r><w:t>,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>S</w:t></w:r><w:r><w:t>, and</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>T</w:t></w:r><w:r><w:t>. Variable</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>R</w:t></w:r><w:r><w:t> is a 3-column matrix containing the list of valid reaction steps at each row</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>i</w:t></w:r><w:r><w:t>:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>\"Reaction</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>i</w:t></w:r><w:r><w:t>:</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>R</w:t></w:r><w:r><w:t>(</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>i</w:t></w:r><w:r><w:t>,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>1</w:t></w:r><w:r><w:t>) --&gt;</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>R</w:t></w:r><w:r><w:t>(</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>i</w:t></w:r><w:r><w:t>,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>2</w:t></w:r><w:r><w:t>) takes</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>R</w:t></w:r><w:r><w:t>(</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>i</w:t></w:r><w:r><w:t>,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>3</w:t></w:r><w:r><w:t>) mins\"</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Output the total time of the fastest reaction chain from</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>S</w:t></w:r><w:r><w:t> to</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>T</w:t></w:r><w:r><w:t>, rounded to 2 decimal places. If a solution does not exist, then output</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:rFonts w:cs=\"monospace\"/></w:rPr><w:t>Inf</w:t></w:r><w:r><w:t>. You are ensured that:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>2 &lt;=</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>N</w:t></w:r><w:r><w:t> &lt;= 20</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>S</w:t></w:r><w:r><w:t>,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>T</w:t></w:r><w:r><w:t>, and all elements in the first 2 columns of</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>R</w:t></w:r><w:r><w:t> are integers within [1,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>N</w:t></w:r><w:r><w:t>].</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Completion times are decimal numbers within (0,10].</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>S</w:t></w:r><w:r><w:t> is not equal to</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>T</w:t></w:r><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Each compound 1, ...,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>N</w:t></w:r><w:r><w:t> is mentioned at least once in</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>R</w:t></w:r><w:r><w:t>. Hence,</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>N</w:t></w:r><w:r><w:t> can be inferred from matrix</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>R</w:t></w:r><w:r><w:t>.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The following sample test case is the one illustrated above:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[>> R = [1 2 1.5; 1 3 2.5; 2 3 0.6; 3 4 4.1; 4 2 3.2];\n>> reaction_chain(R,1,4)\nans = \n 6.20]]></w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

This problem is related to Problem <a href = "45470">45470</a>.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 --&gt; 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:<pre class="language-matlab">Given N = 4 and the following valid reactions:
Reaction 1: 1 --&gt; 2 takes 1.5 mins
Reaction 2: 1 --&gt; 3 takes 2.5 mins 
Reaction 3: 2 --&gt; 3 takes 0.6 mins
Reaction 4: 3 --&gt; 4 takes 4.1 mins 
Reaction 5: 4 --&gt; 2 takes 3.2 mins
Sample reaction chains: 1 --&gt; 3 --&gt; 4 takes (2.5 + 4.1) mins
 1 --&gt; 2 --&gt; 3 --&gt; 4 takes (1.5 + 0.6 + 4.1) mins 
 4 --&gt; 2 --&gt; 3 takes (3.2 + 0.6) mins
</pre>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 and a target compound T, can you find a reaction chain between them with the smallest total completion time?The inputs to this problem are R, S, and T. Variable R is a 3-column matrix containing the list of valid reaction steps at each row i:"Reaction i: R( i, 1) --&gt; R( i, 2) takes R( i, 3) mins"Output the total time of the fastest reaction chain from S to T, rounded to 2 decimal places. If a solution does not exist, then output <tt>Inf</tt>. You are ensured that:<ul><li>2 &lt;= N &lt;= 20</li><li>S, T, and all elements in the first 2 columns of R are integers within [1, N].</li><li>Completion times are decimal numbers within (0,10].</li><li>S is not equal to T.</li><li>Each compound 1, ..., N is mentioned at least once in R. Hence, N can be inferred from matrix R.</li></ul>The following sample test case is the one illustrated above:<pre class="language-matlab">&gt;&gt; R = [1 2 1.5; 1 3 2.5; 2 3 0.6; 3 4 4.1; 4 2 3.2];
&gt;&gt; reaction_chain(R,1,4)
ans = 
 6.20
</pre>

This problem is related to Problem <45470>.

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* and a target compound *T*, can you find a reaction chain between them with the smallest _total completion time_?

The inputs to this problem are *R*, *S*, and *T*. 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 total time of the fastest reaction chain from *S* to *T*, rounded to 2 decimal places. If a solution does not exist, then output |Inf|. You are ensured that:

* 2 <= *N* <= 20
* *S*, *T*, and all elements in the first 2 columns of *R* are integers within [1, *N*].
* Completion times are decimal numbers within (0,10].
* *S* is not equal to *T*.
* 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_chain(R,1,4)
  ans = 
       6.20

Solve

Solution Stats

19 Solutions
12 Solvers

Last Solution submitted on Jul 28, 2022

Last 200 Solutions

Problem Comments

Problem Recent Solvers12

Problem Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 45467. Find the fastest reaction chain to reach a target compound

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers12

Suggested Problems

More from this Author19

Problem Tags

Community Treasure Hunt

Problem 45467. Find the fastest reaction chain to reach a target compound

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers12

Suggested Problems

More from this Author19

Problem Tags

Community Treasure Hunt

Players