Abelian sandpile model/Identity
Our sandpiles are based on a 3 by 3 rectangular grid giving nine areas that contain a number from 0 to 3 inclusive. (The numbers are said to represent grains of sand in each area of the sandpile).
E.g. s1 =
1 2 0
2 1 1
0 1 3
Or s2 =
2 1 3
1 0 1
0 1 0
Addition on sandpiles is done by adding numbers in corresponding grid areas, so for the above:
1 2 0 2 1 3 3 3 3
s1 + s2 = 2 1 1 + 1 0 1 = 3 1 2
0 1 3 0 1 0 0 2 3
If the addition would result in more than 3 "grains of sand" in any area then those areas cause the whole sandpile to become "unstable" and the sandpile areas are "toppled" in an "avalanche" until the "stable" result is obtained.
Any unstable area (with a number >= 4), is "toppled" by loosing one grain of sand to each of its four horizontal or vertical neighbours. Grains are lost at the edge of the grid, but otherwise increase the number in neighbouring cells by one, whilst decreasing the count in the toppled cell by four in each toppling.
A toppling may give an adjacent area more than four grains of sand leading to a chain of topplings called an "avalanche". E.g.
4 3 3 0 4 3 1 0 4 1 1 0 2 1 0
3 1 2 ==> 4 1 2 ==> 4 2 2 ==> 4 2 3 ==> 0 3 3
0 2 3 0 2 3 0 2 3 0 2 3 1 2 3
The final result is the stable sandpile on the right.
Note: The order in which cells are toppled does not affect the final result.
- Task
- Create a class or datastructure and functions to represent and operate on
sandpiles.
- Confirm the result of the avalanche of topplings shown above
- Confirm that s1 + s2 == s2 + s1 # Show the stable results
- If s3 is the sandpile with number 3 in every grid area, and s3_id is the
following sandpile:
2 1 2
1 0 1
2 1 2
- * Show that
s3 + s3_id == s3 - * Show that
s3_id + s3_id == s3_id
- References
Python
<lang python>from itertools import product from collections import defaultdict
class Sandpile():
def __init__(self, gridtext):
array = [int(x) for x in gridtext.strip().split()]
self.grid = defaultdict(int,
{(i //3, i % 3): x
for i, x in enumerate(array)})
_border = set((r, c)
for r, c in product(range(-1, 4), repeat=2)
if not 0 <= r <= 2 or not 0 <= c <= 2
)
_cell_coords = list(product(range(3), repeat=2))
def topple(self):
g = self.grid
for r, c in self._cell_coords:
if g[(r, c)] >= 4:
g[(r - 1, c)] += 1
g[(r + 1, c)] += 1
g[(r, c - 1)] += 1
g[(r, c + 1)] += 1
g[(r, c)] -= 4
return True
return False
def stabilise(self):
while self.topple():
pass
# Remove extraneous grid border
g = self.grid
for row_col in self._border.intersection(g.keys()):
del g[row_col]
return self
__pos__ = stabilise # +s == s.stabilise()
def __eq__(self, other):
g = self.grid
return all(g[row_col] == other.grid[row_col]
for row_col in self._cell_coords)
def __add__(self, other):
g = self.grid
ans = Sandpile("")
for row_col in self._cell_coords:
ans.grid[row_col] = g[row_col] + other.grid[row_col]
return ans.stabilise()
def __str__(self):
g, txt = self.grid, []
for row in range(3):
txt.append(' '.join(str(g[(row, col)])
for col in range(3)))
return '\n'.join(txt)
def __repr__(self):
return f'{self.__class__.__name__}(""""\n{self.__str__()}""")'
unstable = Sandpile(""" 4 3 3 3 1 2 0 2 3""") s1 = Sandpile("""
1 2 0 2 1 1 0 1 3
""") s2 = Sandpile("""
2 1 3 1 0 1 0 1 0
""") s3 = Sandpile("3 3 3 3 3 3 3 3 3") s3_id = Sandpile("2 1 2 1 0 1 2 1 2") </lang>
- Command line session to complete task.
In [2]: unstable
Out[2]:
Sandpile(""""
4 3 3
3 1 2
0 2 3""")
In [3]: unstable.stabilise()
Out[3]:
Sandpile(""""
2 1 0
0 3 3
1 2 3""")
In [4]: s1 + s2
Out[4]:
Sandpile(""""
3 3 3
3 1 2
0 2 3""")
In [5]: s2 + s1
Out[5]:
Sandpile(""""
3 3 3
3 1 2
0 2 3""")
In [6]: s1 + s2 == s2 + s1
Out[6]: True
In [7]: s3
Out[7]:
Sandpile(""""
3 3 3
3 3 3
3 3 3""")
In [8]: s3_id
Out[8]:
Sandpile(""""
2 1 2
1 0 1
2 1 2""")
In [9]: s3 + s3_id
Out[9]:
Sandpile(""""
3 3 3
3 3 3
3 3 3""")
In [10]: s3 + s3_id == s3
Out[10]: True
In [11]: s3_id + s3_id
Out[11]:
Sandpile(""""
2 1 2
1 0 1
2 1 2""")
In [12]: s3_id + s3_id == s3_id
Out[12]: True
In [13]: