Problem 42639. Find the Final State of an Abelian Sandpile
Let us define an 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.
So
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 ]
Solution Stats
Problem Comments
-
1 Comment
Very nice. Here's an updated link for the Nautilus article: https://nautil.us/the-math-of-the-amazing-sandpile-238320/
Solution Comments
Show commentsProblem Recent Solvers65
Suggested Problems
-
Remove all the words that end with "ain"
2224 Solvers
-
Return a list sorted by number of occurrences
2753 Solvers
-
Replace NaNs with the number that appears to its left in the row.
2957 Solvers
-
Remove the polynomials that have positive real elements of their roots.
1661 Solvers
-
1395 Solvers
More from this Author50
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!