Abelian sandpile model/Identity: Difference between revisions

===Object Oriented===

===Functional===

<lang python>'''Abelian Sandpile'''

from operator import add

# -------------------------- TEST --------------------------

# main :: IO ()

def main():

'''Tests of cascades and additions'''

s0 = [[4, 3, 3], [3, 1, 2], [0, 2, 3]]

s1 = [[1, 2, 0], [2, 1, 1], [0, 1, 3]]

s2 = [[2, 1, 3], [1, 0, 1], [0, 1, 0]]

s3 = [[3, 3, 3], [3, 3, 3], [3, 3, 3]]

s3_id = [[2, 1, 2], [1, 0, 1], [2, 1, 2]]

for expr in [

'Cascaded outcome:',

f' {s0}',

f'-> {cascaded(s0)}',

'',

f's1 + s2 == s2 + s1 -> {addSand(s1)(s2) == addSand(s2)(s1)}',

f's1 + s2: {addSand(s1)(s2)}',

f's2 + s1: {addSand(s2)(s1)}',

'',

f's3 + s3_id == s3 -> {addSand(s3)(s3_id) == s3}',

f's3 + s3_id: {addSand(s3)(s3_id)}',

f' s3: {s3}',

'',

f's3_id + s3_id == s3_id -> {addSand(s3_id)(s3_id) == s3_id}',

f's3_id + s3_id: {addSand(s3_id)(s3_id)}',

f' s3_id: {s3_id}',

]:

print(expr)

# ----------------------- SANDPILES ------------------------

# addSand :: [[Int]] -> [[Int]] -> [[Int]]

def addSand(xs):

'''The stabilised sum of two sandpiles.

'''

def go(ys):

return cascaded(

chunksOf(len(xs))(

map(

add,

concat(xs),

concat(ys)

)

)

)

return go

# cascaded :: [[Int]] -> [[Int]]

def cascaded(rows):

'''The stable final state of a sand-pile.

'''

def p(xs):

return all([4 > x for x in xs])

xs = list(rows)

w = len(xs)

return list(chunksOf(w)(

until(p)(

nextState(w)

)(concat(xs))

))

# nextState Int -> Int -> [Int] -> [Int]

def nextState(w):

'''The next state of a (potentially unstable)

flattened sand-pile matrix of row length w.

'''

def go(xs):

mbi = findIndex(lambda x: 3 < x)(xs)

if None is mbi:

return xs

else:

neighbours = indexNeighbours(w)(mbi)

return [

1 + k if i in neighbours else (

k - 4 if mbi == i else k

) for (i, k) in enumerate(xs)

]

return go

# indexNeighbours :: Int -> Int

def indexNeighbours(w):

'''Indices vertically and horizontally adjoining the

given index in a flattened matrix of dimension w.

'''

def go(i):

lastCol = w - 1

iSqr = (w * w)

col = i % w

return [

j for j in [i - w, i + w]

if -1 < j < iSqr

] + ([i - 1] if 0 != col else []) + (

[1 + i] if lastCol != col else []

)

return go

# ------------------------ GENERIC -------------------------

# chunksOf :: Int -> [a] -> [[a]]

def chunksOf(n):

'''A series of lists of length n, subdividing the

contents of xs. Where the length of xs is not evenly

divible, the final list will be shorter than n.

'''

def go(xs):

ys = list(xs)

return (

ys[i:n + i] for i in range(0, len(ys), n)

) if 0 < n else None

return go

# concat :: [[a]] -> [a]

def concat(xs):

'''The concatenation of all

elements in a list.

'''

return [x for lst in xs for x in lst]

# findIndex :: (a -> Bool) -> [a] -> Maybe Int

def findIndex(p):

'''Just the first index at which an

element in xs matches p,

or Nothing if no elements match.

'''

def go(xs):

return next(

(ix[0] for ix in enumerate(xs) if p(ix[1])),

None

)

return go

# until :: (a -> Bool) -> (a -> a) -> a -> a

def until(p):

'''The result of repeatedly applying f until p holds.

The initial seed value is x.

'''

def go(f):

def g(x):

v = x

while not p(v):

v = f(v)

return v

return g

return go

# MAIN ---

if __name__ == '__main__':

main()</lang>

{{Out}}

<pre>Cascaded outcome:

[[4, 3, 3], [3, 1, 2], [0, 2, 3]]

-> [[2, 1, 0], [0, 3, 3], [1, 2, 3]]

s1 + s2 == s2 + s1 -> True

s1 + s2: [[3, 3, 3], [3, 1, 2], [0, 2, 3]]

s2 + s1: [[3, 3, 3], [3, 1, 2], [0, 2, 3]]

s3 + s3_id == s3 -> True

s3 + s3_id: [[3, 3, 3], [3, 3, 3], [3, 3, 3]]

s3: [[3, 3, 3], [3, 3, 3], [3, 3, 3]]

s3_id + s3_id == s3_id -> True

s3_id + s3_id: [[2, 1, 2], [1, 0, 1], [2, 1, 2]]

s3_id: [[2, 1, 2], [1, 0, 1], [2, 1, 2]]</pre>