Problem 1506. Maximum Intra-Vector Swaps

Created by Richard Zapor

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 Challenge, based upon a contest in which Rokicki came in 2nd, is to find sequences containing 1:N that require maximum iterations prior to the value 1 appearing in the first position.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The processing rule is that positions 1 thru Vector(1) are swapped. Processing stops when Vector(1) is 1.</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 Sequences:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[[3 1 2], [2 1 3], [1 2 3] Score 2\n[3 1 4 5 2][4 1 3 5 2][5 3 1 4 2][2 4 1 3 5][4 2 1 3 5][3 1 2 4 5][2 1 3 4 5][1 2 3 4 5]]]></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>Input:</w:t></w:r><w:r><w:t> n (Integer from 1 to 31) (16 Actual Cases 2:11 13 17 19 23 29 31)</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>Output:</w:t></w:r><w:r><w:t> Vector of values 1:n</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Example:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Input: 5 Output: [3 1 4 5 2]</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Score: 7</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>A minimum cumulative score of 531 for the 17 cases is required to Pass.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Final Score = 2531 - sum(scores)</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>Hints:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Usage of perms for 10 or higher may cause Cody Memory/Time issues. Random subsets are suggested for n&gt;9.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Request: If Code is implemented external then please post as a block comment.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Faster Code Block than fliplr:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[function count=process_seq(seq)\n count=0;\n while seq(1)>1\n count=count+1;\n seq(1:seq(1))=seq(seq(1):-1:1);\n end\nend]]></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 Challenge, based upon a contest in which Rokicki came in 2nd, is to find sequences containing 1:N that require maximum iterations prior to the value 1 appearing in the first position.The processing rule is that positions 1 thru Vector(1) are swapped. Processing stops when Vector(1) is 1.Example Sequences:<pre class="language-matlab">[3 1 2], [2 1 3], [1 2 3] Score 2
[3 1 4 5 2][4 1 3 5 2][5 3 1 4 2][2 4 1 3 5][4 2 1 3 5][3 1 2 4 5][2 1 3 4 5][1 2 3 4 5]
</pre>Input: n (Integer from 1 to 31) (16 Actual Cases 2:11 13 17 19 23 29 31)Output: Vector of values 1:nExample:Input: 5 Output: [3 1 4 5 2]Score: 7A minimum cumulative score of 531 for the 17 cases is required to Pass.Final Score = 2531 - sum(scores)Hints:Usage of perms for 10 or higher may cause Cody Memory/Time issues. Random subsets are suggested for n>9.Request: If Code is implemented external then please post as a block comment.Faster Code Block than fliplr:<pre class="language-matlab">function count=process_seq(seq)
 count=0;
 while seq(1)>1
 count=count+1;
 seq(1:seq(1))=seq(seq(1):-1:1);
 end
end
</pre>

Solve

Solution Stats

42 Solutions
7 Solvers

Last Solution submitted on Jul 16, 2019

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

Jean-Marie Sainthillier on 17 Jul 2013

Wonderful problem

Problem Recent Solvers7

Problem Tags

contest fliplr perms randperm sequence uint8 vector

Community Treasure Hunt

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

Start Hunting!

Problem 1506. Maximum Intra-Vector Swaps

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers7

Suggested Problems

More from this Author246

Problem Tags

Community Treasure Hunt

Problem 1506. Maximum Intra-Vector Swaps

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers7

Suggested Problems

More from this Author246

Problem Tags

Community Treasure Hunt

Players