Problem 45426. The Tortoise and the Hare - 02

Created by Asif Newaz

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>Previous problem</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://www.mathworks.com/matlabcentral/cody/problems/45425-the-tortoise-and-the-hare-01\"><w:r><w:t>&lt;https://www.mathworks.com/matlabcentral/cody/problems/45425-the-tortoise-and-the-hare-01</w:t></w:r></w:hyperlink><w:r><w:t>&gt;</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Suppose in an infinitely long line, the tortoise is standing in position 0.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>From that place, it can move in both +ve and -ve direction. The condition is that, in i-th jump, it can move i step forward or backward.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>So one possible scenario can be -</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ 0 [i=1] --- 1 step forward\n 1 [i=2] --- 2 step forward\n 3 [i=3] --- 3 step forward\n 6 [i=4] --- 4 step backward\n 2 [i=5] --- 5 step forward\n 7 [i=6] --- 6 step backward\n 1 [i=7] --- 7 step forward\n 8]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>If you look carefully, you'll find that -- If the tortoise moves this way, it'll always be able to reach any destination (x).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The question is what is the minimum number of moves it'll take to reach destination x.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>For example --</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ if x=8\n >> in the above example, it takes 7 steps\n >> but if it moves this way -- [0,-1,1,4,8] -- steps required = 4.]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>So 4 is the optimum way.</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>"}]}

Previous problem <a href = "https://www.mathworks.com/matlabcentral/cody/problems/45425-the-tortoise-and-the-hare-01">https://www.mathworks.com/matlabcentral/cody/problems/45425-the-tortoise-and-the-hare-01</a>Suppose in an infinitely long line, the tortoise is standing in position 0.From that place, it can move in both +ve and -ve direction. The condition is that, in i-th jump, it can move i step forward or backward.So one possible scenario can be -<pre> 0 [i=1] --- 1 step forward
 1 [i=2] --- 2 step forward
 3 [i=3] --- 3 step forward
 6 [i=4] --- 4 step backward
 2 [i=5] --- 5 step forward
 7 [i=6] --- 6 step backward
 1 [i=7] --- 7 step forward
 8</pre>If you look carefully, you'll find that -- If the tortoise moves this way, it'll always be able to reach any destination (x).The question is what is the minimum number of moves it'll take to reach destination x.For example --<pre> if x=8
 &gt;&gt; in the above example, it takes 7 steps
 &gt;&gt; but if it moves this way -- [0,-1,1,4,8] -- steps required = 4.</pre>So 4 is the optimum way.

Solve

Solution Stats

37 Solutions
6 Solvers

Last Solution submitted on Nov 28, 2022

Last 200 Solutions

Problem Comments

2 Comments

2 Comments

Rafael S.T. Vieira on 28 Nov 2022 at 17:06

This problem is not really about DP or GA, but it is still good.

Rafael S.T. Vieira on 28 Nov 2022 at 17:25

DP or GA require few test cases, or it can quickly grow beyond what is computational through current technology. For instance, 400 steps going ve or -ve, would require a tree with 2^401-1 nodes. It doesn't matter how we choose to traverse this tree, greedy or DP, it would only be fast to find a solution if there were many possible solutions (for this problem, there are just a few correct ones).

Problem Recent Solvers6

Problem Tags

Community Treasure Hunt

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

Start Hunting!

Problem 45426. The Tortoise and the Hare - 02

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers6

Suggested Problems

More from this Author165

Problem Tags

Community Treasure Hunt

Problem 45426. The Tortoise and the Hare - 02

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers6

Suggested Problems

More from this Author165

Problem Tags

Community Treasure Hunt

Players