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

Problem 1506. Maximum Intra-Vector Swaps

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers7

Suggested Problems

More from this Author236

Problem Tags

Problem 1506. Maximum Intra-Vector Swaps

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers7

Suggested Problems

More from this Author236

Problem Tags

Players