Problem 42639. Find the Final State of an Abelian Sandpile

Created by Ned Gulley

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>Let us define an</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://nautil.us/issue/23/dominoes/the-amazing-autotuning-sandpile\"><w:r><w:t>Abelian sand pile</w:t></w:r></w:hyperlink><w:r><w:t> as a matrix that is only in a stable and final state when all of its elements are less than 4. When any of its elements is greater than 4, distribute four sand grains, one each to the elements above, below, to the left, and to the right of the offending element. Continue doing this until the matrix is stable.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>So</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ 0 0 0 \n 0 4 1\n 1 0 0]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>would become</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ 0 1 0\n 1 0 2\n 1 1 0]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>because the 4 in the middle is unstable and gets distributed.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>What makes this process Abelian is that the order in which you distribute the \"sand grains\" doesn't matter. This gives you considerable algorithmic freedom.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>So, given an input matrix A, return the resulting stable Abelian sand pile matrix B.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Note: you won't have to worry about sand grains \"falling off the edge of the table.\" The given matrix A will always be big enough to handle the resulting stable matrix B.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><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[ A = [ 0 0 0 0\n 0 4 4 0\n 0 0 0 0 ]\n\n B = [ 0 1 1 0\n 1 1 1 1\n 0 1 1 0 ]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>and</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ A = [ 0 0 0\n 0 9 0\n 0 0 0 ] \n\n B = [ 0 2 0\n 2 1 2\n 0 2 0 ]]]></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>"}]}

Let us define an <a href = "http://nautil.us/issue/23/dominoes/the-amazing-autotuning-sandpile">Abelian sand pile</a> as a matrix that is only in a stable and final state when all of its elements are less than 4. When any of its elements is greater than 4, distribute four sand grains, one each to the elements above, below, to the left, and to the right of the offending element. Continue doing this until the matrix is stable.So<pre> 0 0 0 
 0 4 1
 1 0 0</pre>would become<pre> 0 1 0
 1 0 2
 1 1 0</pre>because the 4 in the middle is unstable and gets distributed.What makes this process Abelian is that the order in which you distribute the "sand grains" doesn't matter. This gives you considerable algorithmic freedom.So, given an input matrix A, return the resulting stable Abelian sand pile matrix B.Note: you won't have to worry about sand grains "falling off the edge of the table." The given matrix A will always be big enough to handle the resulting stable matrix B.Examples<pre> A = [ 0 0 0 0
 0 4 4 0
 0 0 0 0 ]</pre><pre> B = [ 0 1 1 0
 1 1 1 1
 0 1 1 0 ]</pre>and<pre> A = [ 0 0 0
 0 9 0
 0 0 0 ] </pre><pre> B = [ 0 2 0
 2 1 2
 0 2 0 ]</pre>

Let us define an <http://nautil.us/issue/23/dominoes/the-amazing-autotuning-sandpile Abelian sand pile> as a matrix that is only in a stable and final state when all of its elements are less than 4. When any of its elements is greater than 4, distribute four sand grains, one each to the elements above, below, to the left, and to the right of the offending element. Continue doing this until the matrix is stable.

0 0 0 
 0 4 1
 1 0 0

would become

0 1 0
 1 0 2
 1 1 0

because the 4 in the middle is unstable and gets distributed.

What makes this process Abelian is that the order in which you distribute the "sand grains" doesn't matter. This gives you considerable algorithmic freedom.

So, given an input matrix A, return the resulting stable Abelian sand pile matrix B.

Note: you won't have to worry about sand grains "falling off the edge of the table." The given matrix A will always be big enough to handle the resulting stable matrix B.

Examples

A = [ 0 0 0 0
       0 4 4 0
       0 0 0 0 ]

B = [ 0 1 1 0
       1 1 1 1
       0 1 1 0 ]

and

A = [ 0 0 0
       0 9 0
       0 0 0 ]

B = [ 0 2 0
       2 1 2
       0 2 0 ]

Solve

Solution Stats

121 Solutions
53 Solvers

Last Solution submitted on Apr 14, 2023

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

Christian Schröder on 7 Oct 2022

Very nice. Here's an updated link for the Nautilus article: https://nautil.us/the-math-of-the-amazing-sandpile-238320/

Solution Comments

Show comments

Problem Recent Solvers53

Problem Tags

Community Treasure Hunt

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

Start Hunting!

Problem 42639. Find the Final State of an Abelian Sandpile

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers53

Suggested Problems

More from this Author50

Problem Tags

Community Treasure Hunt

Problem 42639. Find the Final State of an Abelian Sandpile

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers53

Suggested Problems

More from this Author50

Problem Tags

Community Treasure Hunt

Players