Problem 42498. Pancake sorting - minimum flips.

Created by Jan Orwat

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>Sort a stack of pancakes by flipping them using spatula.</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>There are</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>N</w:t></w:r><w:r><w:t> pancakes with diameters</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>1: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>Spatula can be inserted anywhere in the stack and used to flip all the pancakes above.</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>Sort pancakes in increasing order.</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>Return a vector of places where spatula was inserted.</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>Minimize number of flips, your score will depend on the number of flips in the last few tests.</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>References:</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://www.math.illinois.edu/~dwest/openp/pancake.html\"><w:r><w:t>math.illinois.edu</w:t></w:r></w:hyperlink><w:r><w:t>,</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"https://en.wikipedia.org/wiki/Pancake_sorting\"><w:r><w:t>wikipedia</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>Example (horizontal view):</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[Initial stack: 6 4 2 5 3 1, (\",\" indicates position of spatula)\nfirst flip: 1 3 5,2 4 6\nsecond: 5 3 1 2 4,6\n... 4 2 1 3,5 6\n 3 1 2,4 5 6\n 2 1,3 4 5 6\nsorted! 1 2 3 4 5 6\n\npositions of spatula from the begining: 6 3 5 4 3 2]]></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>"}]}

Sort a stack of pancakes by flipping them using spatula.<ul><li>There are N pancakes with diameters 1:N.</li><li>Spatula can be inserted anywhere in the stack and used to flip all the pancakes above.</li><li>Sort pancakes in increasing order.</li><li>Return a vector of places where spatula was inserted.</li><li>Minimize number of flips, your score will depend on the number of flips in the last few tests.</li><li>References: <a href = "http://www.math.illinois.edu/~dwest/openp/pancake.html">math.illinois.edu</a>, <a href = "https://en.wikipedia.org/wiki/Pancake_sorting">wikipedia</a>.</li></ul>Example (horizontal view):<pre class="language-matlab">Initial stack: 6 4 2 5 3 1, ("," indicates position of spatula)
first flip: 1 3 5,2 4 6
second: 5 3 1 2 4,6
... 4 2 1 3,5 6
 3 1 2,4 5 6
 2 1,3 4 5 6
sorted! 1 2 3 4 5 6
</pre><pre class="language-matlab">positions of spatula from the begining: 6 3 5 4 3 2
</pre>

Solve

Solution Stats

54 Solutions
40 Solvers

Last Solution submitted on Sep 07, 2020

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

Muthu Annamalai on 7 Aug 2015

William Gates and Christos Papadimitrou solved this problem, before the former left to co-found Microsoft. Very interesting problem indeed.

Problem Recent Solvers40

Problem Tags

pancakes sorting

Problem 42498. Pancake sorting - minimum flips.

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers40

Suggested Problems

More from this Author41

Problem Tags

Problem 42498. Pancake sorting - minimum flips.

Solution Stats

Last 200 Solutions

Problem Comments

Problem Recent Solvers40

Suggested Problems

More from this Author41

Problem Tags

Players