Problem 1494. Hungry Snake

Created by Yaroslav

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>Who hasn't played</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Snake_%28video_game%29\"><w:r><w:t>the Snake game</w:t></w:r></w:hyperlink><w:r><w:t> when they were little? It's quite hard to finish this simple game; nonetheless</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Chuck_Norris_facts\"><w:r><w:t>Chuck Norris</w:t></w:r></w:hyperlink><w:r><w:t> has accomplished the task in the most difficult level, naturally. Now, since the game was</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>too easy</w:t></w:r><w:r><w:t> for him, he did it with the highest number of turns possible. We shall now inspect Chuck Norris' solution.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Suppose you have a 2ª×2ª matrix</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>M</w:t></w:r><w:r><w:t> (with an integer</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>a</w:t></w:r><w:r><w:t> ≥ 0). The path of the snake is denoted with consecutive numbers 1÷4ª. The matrix</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>M</w:t></w:r><w:r><w:t> must obey the following conditions:</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr></w:pPr><w:r><w:t>All the numbers between 1 to 4ª exist</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>once</w:t></w:r><w:r><w:t> in a 2ª×2ª matrix.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr></w:pPr><w:r><w:t>These numbers form a snake; i.e., each number</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> must be adjacent to both</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> -1 and</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> +1 (with the obvious exception of 1 and 4ª).</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"ListParagraph\"/><w:numPr><w:numId w:val=\"2\"/></w:numPr></w:pPr><w:r><w:t>There</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:i/></w:rPr><w:t>cannot</w:t></w:r><w:r><w:t> be more than 4 consecutive numbers in a row or a column.</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=\"ListParagraph\"/><w:numPr><w:numId w:val=\"1\"/></w:numPr></w:pPr><w:r><w:t>Since Chuck Norris can draw an infinite fractal, you may want to check the</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Hilbert_curve\"><w:r><w:t>Hilbert Curve</w:t></w:r></w:hyperlink><w:r><w:t> or other</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/Space-filling_curves\"><w:r><w:t>Space-filling curves</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:rPr><w:b/></w:rPr><w:t>Examples</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ hungry_snake(0)\n ans = \n 1\n\n hungry_snake(1)\n ans = \n 1 2\n 4 3\n\n hungry_snake(2)\n ans = \n 1 4 5 6\n 2 3 8 7\n 15 14 9 10\n 16 13 12 11]]></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>Bad Solutions</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:rFonts w:cs=\"monospace\"/></w:rPr><w:t>a=1; eye(2^a)</w:t></w:r><w:r><w:t> — doesn't have all the numbers 1 to 4.</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:rFonts w:cs=\"monospace\"/></w:rPr><w:t>a=2; reshape(1:4^a,2^a,2^a)</w:t></w:r><w:r><w:t> — 4 and 5 aren't adjacent.</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:rFonts w:cs=\"monospace\"/></w:rPr><w:t>a=3; spiral(2^a)</w:t></w:r><w:r><w:t> — has 8 consecutive numbers in a row.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>The usual cheats</w:t></w:r><w:r><w:t> </w:t></w:r><w:r><w:rPr><w:b/></w:rPr><w:t>are not</w:t></w:r><w:r><w:t> allowed!</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>"}]}

Who hasn't played <a href = "http://en.wikipedia.org/wiki/Snake_%28video_game%29">the Snake game</a> when they were little? It's quite hard to finish this simple game; nonetheless <a href = "http://en.wikipedia.org/wiki/Chuck_Norris_facts">Chuck Norris</a> has accomplished the task in the most difficult level, naturally. Now, since the game was too easy for him, he did it with the highest number of turns possible. We shall now inspect Chuck Norris' solution.Suppose you have a 2&ordf;&times;2&ordf; matrix M (with an integer a &ge; 0). The path of the snake is denoted with consecutive numbers 1&divide;4&ordf;. The matrix M must obey the following conditions:<ol><li>All the numbers between 1 to 4&ordf; exist once in a 2&ordf;&times;2&ordf; matrix.</li><li>These numbers form a snake; i.e., each number n must be adjacent to both n -1 and n +1 (with the obvious exception of 1 and 4&ordf;).</li><li>There cannot be more than 4 consecutive numbers in a row or a column.</li></ol>Hints<ul><li>Since Chuck Norris can draw an infinite fractal, you may want to check the <a href = "http://en.wikipedia.org/wiki/Hilbert_curve">Hilbert Curve</a> or other <a href = "http://en.wikipedia.org/wiki/Space-filling_curves">Space-filling curves</a>.</li></ul>Examples<pre> hungry_snake(0)
 ans = 
 1</pre><pre> hungry_snake(1)
 ans = 
 1 2
 4 3</pre><pre> hungry_snake(2)
 ans = 
 1 4 5 6
 2 3 8 7
 15 14 9 10
 16 13 12 11</pre>Bad Solutions<ul><li><tt>a=1; eye(2^a)</tt> &mdash; doesn't have all the numbers 1 to 4.</li><li><tt>a=2; reshape(1:4^a,2^a,2^a)</tt> &mdash; 4 and 5 aren't adjacent.</li><li><tt>a=3; spiral(2^a)</tt> &mdash; has 8 consecutive numbers in a row.</li></ul>The usual cheats are not allowed!

Solve

Solution Stats

13 Solutions
7 Solvers

Last Solution submitted on Apr 08, 2019

Last 200 Solutions

Problem Recent Solvers7

Problem Tags

Problem 1494. Hungry Snake

Solution Stats

Last 200 Solutions

Problem Recent Solvers7

Suggested Problems

More from this Author18

Problem Tags

Problem 1494. Hungry Snake

Solution Stats

Last 200 Solutions

Problem Recent Solvers7

Suggested Problems

More from this Author18

Problem Tags

Players