Problem 203. fly fly away

Created by Alfonso Nieto-Castanon

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>A fly moves following a predefined sequence of discrete jumps (defined by the vectors</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>dx</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:i/></w:rPr><w:t>dy</w:t></w:r><w:r><w:t>) repeating the same sequence over and over (note that after each sequence of movements the fly may or may not be at the same position where it started).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The fly always starts at the coordinates</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>(0,0)</w:t></w:r><w:r><w:t> and your job is to determine whether it will ever reach a target coordinate (</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>x</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>y</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>note:</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>dx</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:i/></w:rPr><w:t>dy</w:t></w:r><w:r><w:t> are always equal-sized row vectors and</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>x</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:i/></w:rPr><w:t>y</w:t></w:r><w:r><w:t> are always scalars. Your function should return</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>true</w:t></w:r><w:r><w:t> if the trajectory passes through the target.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:rPr><w:b/></w:rPr><w:t>Example</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[dx = [0,1,0,-1];\n\ndy = [1,0,1,0];\n\nx = 1;\n\ny = 5;]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The fly follows the trajectory:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ (0,0) (0,1) (1,1) (1,2) (0,2) (0,3) (1,3) (1,4) (0,4) (0,5) (1,5) (1,6) ...]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The trajectory passes through the target point (1,5) so the function should return</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>true</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>note: in the test suite, if the target is reachable it will be reachable in at most 100 repetitions of the movement sequence. You get</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>unscored bonus points</w:t></w:r><w:r><w:t> if your solution does not require this limit to be relatively small (i.e. if the algorithm computational time does not increase linearly with the number of repetitions)</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>"}]}

A fly moves following a predefined sequence of discrete jumps (defined by the vectors dx and dy) repeating the same sequence over and over (note that after each sequence of movements the fly may or may not be at the same position where it started).The fly always starts at the coordinates (0,0) and your job is to determine whether it will ever reach a target coordinate ( x , y ).note: dx and dy are always equal-sized row vectors and x and y are always scalars. Your function should return true if the trajectory passes through the target.Example<pre class="language-matlab">dx = [0,1,0,-1];
</pre><pre class="language-matlab">dy = [1,0,1,0];
</pre><pre class="language-matlab">x = 1;
</pre><pre class="language-matlab">y = 5;
</pre>The fly follows the trajectory:<pre> (0,0) (0,1) (1,1) (1,2) (0,2) (0,3) (1,3) (1,4) (0,4) (0,5) (1,5) (1,6) ...</pre>The trajectory passes through the target point (1,5) so the function should return true.note: in the test suite, if the target is reachable it will be reachable in at most 100 repetitions of the movement sequence. You get unscored bonus points if your solution does not require this limit to be relatively small (i.e. if the algorithm computational time does not increase linearly with the number of repetitions)

Solve

Solution Stats

173 Solutions
99 Solvers

Last Solution submitted on May 28, 2020

Last 200 Solutions

Problem Comments

Solution Comments

Solution 1327578

1 Comment

1 Comment

yurenchu on 4 Nov 2017

Flawed solution (same flaw as Solution 1327329).

Solution 1327354

1 Comment

1 Comment

yurenchu on 4 Nov 2017

This is an incorrect solution. For example, suppose dx = [0,1,0,-1], dy = [2,0,2,0], x = 1 and y = 5 (which is the same situation as test #1 but with a slightly different dy); then this code would return 'True' when in fact the correct answer would obviously be 'False'.

Solution 1327329

1 Comment

1 Comment

yurenchu on 4 Nov 2017

[Based on solution 1227987] Although this solution passes the test suite, it (and several others like it) is an incorrect solution. For example, suppose dx = [-1,-1,-1,2,-1,6], dy = [-1,-2,-3,1,1,-1], x = 53 and y = -71 (which is the same situation as test #5 but with a slightly different dy); then this code would return 'True' when in fact the correct answer is 'False'.

Solution 498139

1 Comment

1 Comment

Matt Wolinsky on 10 Sep 2014

I still don't understand the scoring system I guess.
Seems odd to me that the commented solution had size 43 ... but doing extra computation reduced this solution to size 33.
(unless JIT is at the level to implicitly convert?)

Solution 48503

1 Comment

1 Comment

David Young on 22 Feb 2012

Although this has passed the tests, I don't think it is correct, since it allows the fly to go backwards in time as well as forwards.

Solution 20677

1 Comment

1 Comment

@bmtran (Bryant Tran) on 1 Feb 2012

no bonus points for me :(

Problem Recent Solvers99

Problem Tags

math

Problem 203. fly fly away

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers99

Suggested Problems

More from this Author38

Problem Tags

Problem 203. fly fly away

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers99

Suggested Problems

More from this Author38

Problem Tags

Players