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
Show confirming output here, with your example.
- References
Julia
<lang julia>import Base.+, Base.print
struct Sandpile
pile::Matrix{UInt8}
end
function Sandpile(s::String)
arr = [parse(UInt8, x.match) for x in eachmatch(r"\d+", s)] siz = isqrt(length(arr)) return Sandpile(reshape(UInt8.(arr), siz, siz)')
end
const HMAX = 3
function avalanche!(s::Sandpile, lim=HMAX)
nrows, ncols = size(s.pile) while any(x -> x > lim, s.pile) for j in 1:ncols, i in 1:nrows if s.pile[i, j] > lim i > 1 && (s.pile[i - 1, j] += 1) i < nrows && (s.pile[i + 1, j] += 1) j > 1 && (s.pile[i, j - 1] += 1) j < ncols && (s.pile[i, j + 1] += 1) s.pile[i, j] -= 4 end end end s
end
+(s1::Sandpile, s2::Sandpile) = avalanche!(Sandpile((s1.pile + s2.pile)))
function print(io::IO, s::Sandpile)
for row in 1:size(s.pile)[1] for col in 1:size(s.pile)[2] print(io, lpad(s.pile[row, col], 4)) end println() end
end
const s3 = Sandpile("""
3 3 3 3 3 3 3 3 3""")
const s3_id = Sandpile("""
2 1 2 1 0 1 2 1 2""")
const s3a = Sandpile("""
4 3 3 3 1 2 0 2 3""")
println("Avalanche reduction to group:\n", s3a, " =>") println(avalanche!(s3a), "\n")
println("Addition:\n", s3, " +\n", s3_id, " =\n", s3 + s3_id, "\n") println(s3_id, " +\n", s3_id, " =\n", s3_id + s3_id, "\n")
</lang>
- Output:
Avalanche reduction to group: 4 3 3 3 1 2 0 2 3 => 2 1 0 0 3 3 1 2 3 Addition: 3 3 3 3 3 3 3 3 3 + 2 1 2 1 0 1 2 1 2 = 3 3 3 3 3 3 3 3 3 2 1 2 1 0 1 2 1 2 + 2 1 2 1 0 1 2 1 2 = 2 1 2 1 0 1 2 1 2
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]:
Raku
Most of the logic is lifted straight from the Abelian sandpile model task.
<lang perl6>class ASP {
has $.h = 3; has $.w = 3; has @.pile = 0 xx $!w * $!h;
method topple { my $buf = $!w * $!h; my $done; repeat { $done = True; loop (my int $row; $row < $!h; $row = $row + 1) { my int $rs = $row * $!w; # row start my int $re = $rs + $!w; # row end loop (my int $idx = $rs; $idx < $re; $idx = $idx + 1) { if self.pile[$idx] >= 4 { my $grain = self.pile[$idx] div 4; self.pile[ $idx - $!w ] += $grain if $row > 0; self.pile[ $idx - 1 ] += $grain if $idx - 1 >= $rs; self.pile[ $idx + $!w ] += $grain if $row < $!h - 1; self.pile[ $idx + 1 ] += $grain if $idx + 1 < $re; self.pile[ $idx ] %= 4; $done = False; } } } } until $done; self.pile; }
}
- some handy display layout modules
use Terminal::Boxer:ver<0.2+>; use Text::Center;
for 3, (4,3,3,3,1,2,0,2,3), (2,1,2,1,0,1,2,1,2), # 3 square task example
3, (2,1,2,1,0,1,2,1,2), (2,1,2,1,0,1,2,1,2), # 3 square identity 5, (4,1,0,5,1,9,3,6,1,0,8,1,2,5,3,3,0,1,7,5,4,2,2,4,0), (2,3,2,3,2,3,2,1,2,3,2,1,0,1,2,3,2,1,2,3,2,3,2,3,2) # 5 square test -> $size, $pile, $identity {
my $asp = ASP.new(:h($size), :w($size));
$asp.pile = |$pile;
my @display;
my %p = :col($size), :3cw, :indent("\t");
@display.push: rs-box |%p, |$identity;
@display.push: rs-box |%p, $asp.pile;
@display.push: rs-box |%p, $asp.topple;
$asp.pile Z+= $identity.list;
@display.push: rs-box |%p, $asp.pile;
@display.push: rs-box |%p, $asp.topple;
put %p<indent> ~ qww<identity 'test pile' toppled 'plus identity' toppled>».¢er($size * 4 + 1).join: %p<indent>;
.put for [Z~] @display».lines;
put ;
}</lang>
- Output:
identity test pile toppled plus identity toppled ╭───┬───┬───╮ ╭───┬───┬───╮ ╭───┬───┬───╮ ╭───┬───┬───╮ ╭───┬───┬───╮ │ 2 │ 1 │ 2 │ │ 4 │ 3 │ 3 │ │ 2 │ 1 │ 0 │ │ 4 │ 2 │ 2 │ │ 2 │ 1 │ 0 │ ├───┼───┼───┤ ├───┼───┼───┤ ├───┼───┼───┤ ├───┼───┼───┤ ├───┼───┼───┤ │ 1 │ 0 │ 1 │ │ 3 │ 1 │ 2 │ │ 0 │ 3 │ 3 │ │ 1 │ 3 │ 4 │ │ 0 │ 3 │ 3 │ ├───┼───┼───┤ ├───┼───┼───┤ ├───┼───┼───┤ ├───┼───┼───┤ ├───┼───┼───┤ │ 2 │ 1 │ 2 │ │ 0 │ 2 │ 3 │ │ 1 │ 2 │ 3 │ │ 3 │ 3 │ 5 │ │ 1 │ 2 │ 3 │ ╰───┴───┴───╯ ╰───┴───┴───╯ ╰───┴───┴───╯ ╰───┴───┴───╯ ╰───┴───┴───╯ identity test pile toppled plus identity toppled ╭───┬───┬───╮ ╭───┬───┬───╮ ╭───┬───┬───╮ ╭───┬───┬───╮ ╭───┬───┬───╮ │ 2 │ 1 │ 2 │ │ 2 │ 1 │ 2 │ │ 2 │ 1 │ 2 │ │ 4 │ 2 │ 4 │ │ 2 │ 1 │ 2 │ ├───┼───┼───┤ ├───┼───┼───┤ ├───┼───┼───┤ ├───┼───┼───┤ ├───┼───┼───┤ │ 1 │ 0 │ 1 │ │ 1 │ 0 │ 1 │ │ 1 │ 0 │ 1 │ │ 2 │ 0 │ 2 │ │ 1 │ 0 │ 1 │ ├───┼───┼───┤ ├───┼───┼───┤ ├───┼───┼───┤ ├───┼───┼───┤ ├───┼───┼───┤ │ 2 │ 1 │ 2 │ │ 2 │ 1 │ 2 │ │ 2 │ 1 │ 2 │ │ 4 │ 2 │ 4 │ │ 2 │ 1 │ 2 │ ╰───┴───┴───╯ ╰───┴───┴───╯ ╰───┴───┴───╯ ╰───┴───┴───╯ ╰───┴───┴───╯ identity test pile toppled plus identity toppled ╭───┬───┬───┬───┬───╮ ╭───┬───┬───┬───┬───╮ ╭───┬───┬───┬───┬───╮ ╭───┬───┬───┬───┬───╮ ╭───┬───┬───┬───┬───╮ │ 2 │ 3 │ 2 │ 3 │ 2 │ │ 4 │ 1 │ 0 │ 5 │ 1 │ │ 1 │ 3 │ 2 │ 1 │ 0 │ │ 3 │ 6 │ 4 │ 4 │ 2 │ │ 1 │ 3 │ 2 │ 1 │ 0 │ ├───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┤ │ 3 │ 2 │ 1 │ 2 │ 3 │ │ 9 │ 3 │ 6 │ 1 │ 0 │ │ 2 │ 2 │ 3 │ 3 │ 1 │ │ 5 │ 4 │ 4 │ 5 │ 4 │ │ 2 │ 2 │ 3 │ 3 │ 1 │ ├───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┤ │ 2 │ 1 │ 0 │ 1 │ 2 │ │ 8 │ 1 │ 2 │ 5 │ 3 │ │ 1 │ 1 │ 2 │ 0 │ 3 │ │ 3 │ 2 │ 2 │ 1 │ 5 │ │ 1 │ 1 │ 2 │ 0 │ 3 │ ├───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┤ │ 3 │ 2 │ 1 │ 2 │ 3 │ │ 3 │ 0 │ 1 │ 7 │ 5 │ │ 2 │ 0 │ 3 │ 2 │ 0 │ │ 5 │ 2 │ 4 │ 4 │ 3 │ │ 2 │ 0 │ 3 │ 2 │ 0 │ ├───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┤ ├───┼───┼───┼───┼───┤ │ 2 │ 3 │ 2 │ 3 │ 2 │ │ 4 │ 2 │ 2 │ 4 │ 0 │ │ 3 │ 2 │ 3 │ 2 │ 1 │ │ 5 │ 5 │ 5 │ 5 │ 3 │ │ 3 │ 2 │ 3 │ 2 │ 1 │ ╰───┴───┴───┴───┴───╯ ╰───┴───┴───┴───┴───╯ ╰───┴───┴───┴───┴───╯ ╰───┴───┴───┴───┴───╯ ╰───┴───┴───┴───┴───╯
Wren
<lang ecmascript>import "/fmt" for Fmt
class Sandpile {
static init() { __neighbors = [ [1, 3], [0, 2, 4], [1, 5], [0, 4, 6], [1, 3, 5, 7], [2, 4, 8], [3, 7], [4, 6, 8], [5, 7] ] }
// 'a' is a list of 9 integers in row order construct new(a) { _a = a }
a { _a }
+(other) { var b = List.filled(9, 0) for (i in 0..8) b[i] = _a[i] + other.a[i] return Sandpile.new(b) }
isStable { _a.all { |i| i <= 3 } }
// just topples once so we can observe intermediate results topple() { for (i in 0..8) { if (_a[i] > 3) { _a[i] = _a[i] - 4 for (j in __neighbors[i]) _a[j] = _a[j] + 1 return } } }
toString { var s = "" for (i in 0..2) { for (j in 0..2) s = s + "%(a[3*i + j]) " s = s + "\n" } return s }
}
Sandpile.init() System.print("Avalanche of topplings:\n") var s4 = Sandpile.new([4, 3, 3, 3, 1, 2, 0, 2, 3]) System.print(s4) while (!s4.isStable) {
s4.topple() System.print(s4)
}
System.print("Commutative additions:\n") var s1 = Sandpile.new([1, 2, 0, 2, 1, 1, 0, 1, 3]) var s2 = Sandpile.new([2, 1, 3, 1, 0, 1, 0, 1, 0]) var s3_a = s1 + s2 while (!s3_a.isStable) s3_a.topple() var s3_b = s2 + s1 while (!s3_b.isStable) s3_b.topple() Fmt.print("$s\nplus\n\n$s\nequals\n\n$s", s1, s2, s3_a) Fmt.print("and\n\n$s\nplus\n\n$s\nalso equals\n\n$s", s2, s1, s3_b)
System.print("Addition of identity sandpile:\n") var s3 = Sandpile.new(List.filled(9, 3)) var s3_id = Sandpile.new([2, 1, 2, 1, 0, 1, 2, 1, 2]) s4 = s3 + s3_id while (!s4.isStable) s4.topple() Fmt.print("$s\nplus\n\n$s\nequals\n\n$s", s3, s3_id, s4)
System.print("Addition of identities:\n") var s5 = s3_id + s3_id while (!s5.isStable) s5.topple() Fmt.write("$s\nplus\n\n$s\nequals\n\n$s", s3_id, s3_id, s5)</lang>
- Output:
Avalanche of topplings: 4 3 3 3 1 2 0 2 3 0 4 3 4 1 2 0 2 3 1 0 4 4 2 2 0 2 3 1 1 0 4 2 3 0 2 3 2 1 0 0 3 3 1 2 3 Commutative additions: 1 2 0 2 1 1 0 1 3 plus 2 1 3 1 0 1 0 1 0 equals 3 3 3 3 1 2 0 2 3 and 2 1 3 1 0 1 0 1 0 plus 1 2 0 2 1 1 0 1 3 also equals 3 3 3 3 1 2 0 2 3 Addition of identity sandpile: 3 3 3 3 3 3 3 3 3 plus 2 1 2 1 0 1 2 1 2 equals 3 3 3 3 3 3 3 3 3 Addition of identities: 2 1 2 1 0 1 2 1 2 plus 2 1 2 1 0 1 2 1 2 equals 2 1 2 1 0 1 2 1 2