

 This page uses content from Wikipedia. The original article was at Abelian sandpile model. The list of authors can be seen in the page history. As with Rosetta Code, the text of Wikipedia is available under the GNU FDL. (See links for details on variance)



Implement the Abelian sandpile model also known as Bak–Tang–Wiesenfeld model. Its history, mathematical definition and properties can be found under its wikipedia article.

The task requires the creation of a 2D grid of arbitrary size on which "piles of sand" can be placed. Any "pile" that has 4 or more sand particles on it collapses, resulting in four particles being subtracted from the pile and distributed among its neighbors.

It is recommended to display the output in some kind of image format, as terminal emulators are usually too small to display images larger than a few dozen characters tall. As an example of how to accomplish this, see the Bitmap/Write a PPM file task.

Examples up to 2^30, wow!
javascript running on web
Examples:

0 0 0 0 0    0 0 0 0 0
0 0 0 0 0    0 0 1 0 0
0 0 4 0 0 -> 0 1 0 1 0
0 0 0 0 0    0 0 1 0 0
0 0 0 0 0    0 0 0 0 0

0 0 0 0 0    0 0 0 0 0
0 0 0 0 0    0 0 1 0 0
0 0 6 0 0 -> 0 1 2 1 0
0 0 0 0 0    0 0 1 0 0
0 0 0 0 0    0 0 0 0 0

0  0 0  0  0    0 0 1 0 0
0  0 0  0  0    0 2 1 2 0
0  0 16 0  0 -> 1 1 0 1 1
0  0 0  0  0    0 2 1 2 0
0  0 0  0  0    0 0 1 0 0

 
/* ARM assembly Raspberry PI  or android 32 bits */
/*  program abelian.s   */ 
 
/* run : abelian 256 12 12  */
 
/* REMARK 1 : this program use routines in a include file 
   see task Include a file language arm assembly 
   for the routine affichageMess conversion10 
   see at end of this program the instruction include */
/* for constantes see task include a file in arm assembly */
/************************************/
/* Constantes                       */
/************************************/
.include "../constantes.inc"
.equ MAXI, 25
 
/*********************************/
/* Initialized data              */
/*********************************/
.data
szMessValue:        .asciz "@ "
szMessErrParam:     .asciz "error : command line = abelian size posx posy  \n"
szMessFin:          .asciz "End display :\n"
szCarriageReturn:   .asciz "\n"
 
/*********************************/
/* UnInitialized data            */
/*********************************/
.bss
sZoneConv:        .skip 24
iSandPile:        .skip 4 * MAXI * MAXI
/*********************************/
/*  code section                 */
/*********************************/
.text
.global main 
main:                            @ entry of program 
    mov fp,sp
    ldr r4,[fp]                  @ load number of parameters commend line
    cmp r4,#3                    @ < 4 -> error
    ble 99f
    add r0,fp,#16                @ load address param 4 = pos y
    ldr r0,[r0]
    bl conversionAtoD            @ conversion ascii -> numeric
    mov r3,r0
    add r0,fp,#12                @ load address param 3 = pos x
    ldr r0,[r0]
    bl conversionAtoD
    mov r2,r0
    add r0,fp,#8                 @ load address param 2 = size begin pile
    ldr r0,[r0]
    bl conversionAtoD
    ldr r4,iAdriSandPile
    mov r5,#MAXI
    mul r5,r3,r5                 @ compute offset = maxi * y
    add r5,r2                    @ + x
    str r0,[r4,r5,lsl #2]        @ and store size in pos x,y
    //mov r0,r4                    @ display start position
    //bl displaySandPile
 
    mov r0,r4                   @ sandpile address
    mov r1,r2                   @ pos x to start
    mov r2,r3                   @ pos y to start
    bl addSand
 
    ldr r0,iAdrszMessFin
    bl affichageMess
    mov r0,r4
    bl displaySandPile
    b 100f
99:                                  @ line command error
   ldr r0,iAdrszMessErrParam
   bl affichageMess
100:                                  @ standard end of the program 
    mov r0, #0                        @ return code
    mov r7, #EXIT                     @ request to exit program
    svc #0                            @ perform the system call
 
iAdrszCarriageReturn:     .int szCarriageReturn
iAdrsZoneConv:            .int sZoneConv
iAdrszMessErrParam:       .int szMessErrParam
iAdrszMessFin:            .int szMessFin
iAdriSandPile:            .int iSandPile
/***************************************************/
/*     display  sandpile               */
/***************************************************/
// r0 contains address to sandpile
displaySandPile:
    push {r1-r6,lr}             @ save  registers 
    mov r6,r0
    mov r3,#0                   @ indice y
    mov r4,#MAXI
1:
    mov r2,#0                   @ indice x
2:
    mul r5,r3,r4
    add r5,r2                   @ compute offset
    ldr r0,[r6,r5,lsl #2]       @ load value at pos x,y
    ldr r1,iAdrsZoneConv
    bl conversion10             @ call decimal conversion
    add r1,#1
    mov r7,#0
    strb r7,[r1,r0]
    ldr r0,iAdrszMessValue
    ldr r1,iAdrsZoneConv        @ insert value conversion in message
    bl strInsertAtCharInc
    bl affichageMess
    add r2,#1
    cmp r2,#MAXI
    blt 2b
    ldr r0,iAdrszCarriageReturn
    bl affichageMess
    add r3,#1
    cmp r3,#MAXI
    blt 1b
 
100:
    pop {r1-r6,lr}             @ restaur registers
    bx lr                      @ return
iAdrszMessValue:       .int szMessValue
/***************************************************/
/*     display  sandpile               */
/***************************************************/
// r0 contains address to sanspile
// r1 contains position x
// r2 contains position y
addSand:
    push {r1-r5,lr}             @ save  registers 
    mov r3,#MAXI
    mul r4,r3,r2
    add r4,r1
    ldr r5,[r0,r4,lsl #2]
1:
    cmp r5,#4                   @ 4 grains ?
    blt 100f
    sub r5,#4                   @ yes sustract
    str r5,[r0,r4,lsl #2]
    cmp r1,#MAXI-1              @ right position ok ?
    beq 2f
    add r1,#1                   @ yes
    bl add1Sand                 @ add 1 grain
    bl addSand                  @ and compute new pile
    sub r1,#1
2:
    cmp r1,#0                   @ left position ok ?
    beq 3f
    sub r1,#1
    bl add1Sand
    bl addSand
    add r1,#1
3:
    cmp r2,#0                   @ higt position ok ?
    beq 4f
    sub r2,#1
    bl add1Sand
    bl addSand
    add r2,#1
4:
    cmp r2,#MAXI-1               @ low position ok ?
    beq 5f
    add r2,#1
    bl add1Sand
    bl addSand
    sub r2,#1
5:
   ldr r5,[r0,r4,lsl #2]       @ reload value
   b 1b                        @ and loop
100:
    pop {r1-r5,lr}             @ restaur registers
    bx lr                      @ return
/***************************************************/
/*     add 1 grain of sand              */
/***************************************************/
// r0 contains address to sanspile
// r1 contains position x
// r2 contains position y
add1Sand:
    push {r3-r5,lr}           @ save  registers 
    mov r3,#MAXI
    mul r4,r3,r2
    add r4,r1                 @ compute offset
    ldr r5,[r0,r4,lsl #2]     @ load value at pos x,y
    add r5,#1
    str r5,[r0,r4,lsl #2]     @ and store 
100:
    pop {r3-r5,lr}            @ restaur registers
    bx lr                     @ return
/***************************************************/
/*      ROUTINES INCLUDE                           */
/***************************************************/
.include "../affichage.inc"
 