Abelian sandpile model/Identity: Difference between revisions
Content added Content deleted
(→{{header|Lua}}: added Lua solution) |
(add task to Arm assembly) |
||
Line 57: | Line 57: | ||
* https://www.youtube.com/watch?v=1MtEUErz7Gg |
* https://www.youtube.com/watch?v=1MtEUErz7Gg |
||
* https://en.wikipedia.org/wiki/Abelian_sandpile_model |
* https://en.wikipedia.org/wiki/Abelian_sandpile_model |
||
=={{header|ARM Assembly}}== |
|||
{{works with|as|Raspberry Pi <br> or android 32 bits with application Termux}} |
|||
<lang ARM Assembly> |
|||
/* ARM assembly Raspberry PI or android 32 bits */ |
|||
/* program abelianSum.s */ |
|||
/* 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, 3 |
|||
/*********************************/ |
|||
/* Initialized data */ |
|||
/*********************************/ |
|||
.data |
|||
szMessValue: .asciz "@ " |
|||
szMessAdd1: .asciz "Add sandpile 1 to sandpile 2 \n" |
|||
szMessAdd2: .asciz "Add sandpile 2 to sandpile 1 \n" |
|||
szMessAdd2A: .asciz "Add sandpile 2A to sandpile result \n" |
|||
szMessAdd3: .asciz "Add sandpile 3 to sandpile 3ID \n" |
|||
szMessAdd3ID: .asciz "Add sandpile 3ID to sandpile 3ID \n" |
|||
szMessFin: .asciz "End display :\n" |
|||
szCarriageReturn: .asciz "\n" |
|||
iSandPile1: .int 1,2,0 |
|||
.int 2,1,1 |
|||
.int 0,1,3 |
|||
iSandPile2: .int 2,1,3 |
|||
.int 1,0,1 |
|||
.int 0,1,0 |
|||
iSandPile2A: .int 1,0,0 |
|||
.int 0,0,0 |
|||
.int 0,0,0 |
|||
iSandPile3: .int 3,3,3 |
|||
.int 3,3,3 |
|||
.int 3,3,3 |
|||
iSandPile3ID: .int 2,1,2 |
|||
.int 1,0,1 |
|||
.int 2,1,2 |
|||
/*********************************/ |
|||
/* UnInitialized data */ |
|||
/*********************************/ |
|||
.bss |
|||
sZoneConv: .skip 24 |
|||
iSandPileR1: .skip 4 * MAXI * MAXI |
|||
iSandPileR2: .skip 4 * MAXI * MAXI |
|||
/*********************************/ |
|||
/* code section */ |
|||
/*********************************/ |
|||
.text |
|||
.global main |
|||
main: @ entry of program |
|||
ldr r0,iAdriSandPile1 @ sandpile1 address |
|||
ldr r1,iAdriSandPile2 @ sandpile2 address |
|||
ldr r2,iAdriSandPileR1 @ sandpile result address |
|||
bl addSandPile |
|||
ldr r0,iAdrszMessAdd1 @ display message |
|||
bl affichageMess |
|||
ldr r0,iAdriSandPileR1 @ display sandpile |
|||
bl displaySandPile |
|||
ldr r0,iAdriSandPile2 @ sandpile2 address |
|||
ldr r1,iAdriSandPile1 @ sandpile1 address |
|||
ldr r2,iAdriSandPileR1 @ sandpile result address |
|||
bl addSandPile |
|||
ldr r0,iAdrszMessAdd2 |
|||
bl affichageMess |
|||
ldr r0,iAdriSandPileR1 |
|||
bl displaySandPile |
|||
ldr r0,iAdriSandPileR1 @ sandpile1 address |
|||
ldr r1,iAdriSandPile2A @ sandpile2A address |
|||
ldr r2,iAdriSandPileR2 @ sandpile result address |
|||
bl addSandPile |
|||
ldr r0,iAdrszMessAdd2A |
|||
bl affichageMess |
|||
ldr r0,iAdriSandPileR2 |
|||
bl displaySandPile |
|||
ldr r0,iAdriSandPile3 @ sandpile3 address |
|||
ldr r1,iAdriSandPile3ID @ sandpile3ID address |
|||
ldr r2,iAdriSandPileR2 @ sandpile result address |
|||
bl addSandPile |
|||
ldr r0,iAdrszMessAdd3 |
|||
bl affichageMess |
|||
ldr r0,iAdriSandPileR2 |
|||
bl displaySandPile |
|||
ldr r0,iAdriSandPile3ID @ sandpile3 address |
|||
ldr r1,iAdriSandPile3ID @ sandpile3ID address |
|||
ldr r2,iAdriSandPileR2 @ sandpile result address |
|||
bl addSandPile |
|||
ldr r0,iAdrszMessAdd3ID |
|||
bl affichageMess |
|||
ldr r0,iAdriSandPileR2 |
|||
bl displaySandPile |
|||
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 |
|||
iAdrszMessFin: .int szMessFin |
|||
iAdrszMessAdd1: .int szMessAdd1 |
|||
iAdrszMessAdd2: .int szMessAdd2 |
|||
iAdrszMessAdd2A: .int szMessAdd2A |
|||
iAdrszMessAdd3: .int szMessAdd3 |
|||
iAdrszMessAdd3ID: .int szMessAdd3ID |
|||
iAdriSandPile1: .int iSandPile1 |
|||
iAdriSandPileR1: .int iSandPileR1 |
|||
iAdriSandPileR2: .int iSandPileR2 |
|||
iAdriSandPile2: .int iSandPile2 |
|||
iAdriSandPile2A: .int iSandPile2A |
|||
iAdriSandPile3: .int iSandPile3 |
|||
iAdriSandPile3ID: .int iSandPile3ID |
|||
/***************************************************/ |
|||
/* add two sandpile */ |
|||
/***************************************************/ |
|||
// r0 contains address to sandpile 1 |
|||
// r1 contains address to sandpile 2 |
|||
// r2 contains address to sandpile result |
|||
addSandPile: |
|||
push {r1-r7,lr} @ save registers |
|||
mov r6,r1 @ save addresse sandpile2 |
|||
mov r1,r2 @ and copy sandpile 1 to sandpile result |
|||
bl copySandPile |
|||
mov r0,r2 @ sanspile result |
|||
mov r2,#0 @ indice y |
|||
mov r4,#MAXI |
|||
1: |
|||
mov r1,#0 @ indice x |
|||
2: |
|||
mla r5,r2,r4,r1 @ compute offset |
|||
ldr r7,[r0,r5,lsl #2] @ load value at pos x,y sanspile result |
|||
ldr r3,[r6,r5,lsl #2] @ load value at pos x,y sandpile 2 |
|||
add r7,r3 |
|||
str r7,[r0,r5,lsl #2] @ store sum on sandpile result |
|||
bl avalancheRisk |
|||
add r1,r1,#1 |
|||
cmp r1,#MAXI |
|||
blt 2b |
|||
add r2,r2,#1 |
|||
cmp r2,#MAXI |
|||
blt 1b |
|||
100: |
|||
pop {r1-r7,lr} @ restaur registers |
|||
bx lr @ return |
|||
/***************************************************/ |
|||
/* copy sandpile */ |
|||
/***************************************************/ |
|||
// r0 contains address to sandpile |
|||
// r1 contains address to sandpile result |
|||
copySandPile: |
|||
push {r1-r6,lr} @ save registers |
|||
mov r2,#0 @ indice y |
|||
mov r3,#MAXI |
|||
1: |
|||
mov r4,#0 @ indice x |
|||
2: |
|||
mla r5,r2,r3,r4 @ compute offset |
|||
ldr r6,[r0,r5,lsl #2] @ load value at pos x,y sanspile |
|||
str r6,[r1,r5,lsl #2] @ store value at pos x,y sandpile result |
|||
add r4,r4,#1 |
|||
cmp r4,#MAXI |
|||
blt 2b |
|||
add r2,r2,#1 |
|||
cmp r2,#MAXI |
|||
blt 1b |
|||
100: |
|||
pop {r1-r6,lr} @ restaur registers |
|||
bx lr @ return |
|||
/***************************************************/ |
|||
/* 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 |
|||
/***************************************************/ |
|||
/* avalanche risk */ |
|||
/***************************************************/ |
|||
// r0 contains address to sanspile |
|||
// r1 contains position x |
|||
// r2 contains position y |
|||
avalancheRisk: |
|||
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 avalancheRisk @ and compute new pile |
|||
sub r1,#1 |
|||
2: |
|||
cmp r1,#0 @ left position ok ? |
|||
beq 3f |
|||
sub r1,#1 |
|||
bl add1Sand |
|||
bl avalancheRisk |
|||
add r1,#1 |
|||
3: |
|||
cmp r2,#0 @ higt position ok ? |
|||
beq 4f |
|||
sub r2,#1 |
|||
bl add1Sand |
|||
bl avalancheRisk |
|||
add r2,#1 |
|||
4: |
|||
cmp r2,#MAXI-1 @ low position ok ? |
|||
beq 5f |
|||
add r2,#1 |
|||
bl add1Sand |
|||
bl avalancheRisk |
|||
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" |
|||
</lang> |
|||
{{Output}} |
|||
<pre> |
|||
Add sandpile 1 to sandpile 2 |
|||
3 3 3 |
|||
3 1 2 |
|||
0 2 3 |
|||
Add sandpile 2 to sandpile 1 |
|||
3 3 3 |
|||
3 1 2 |
|||
0 2 3 |
|||
Add sandpile 2A to sandpile result |
|||
2 1 0 |
|||
0 3 3 |
|||
1 2 3 |
|||
Add sandpile 3 to sandpile 3ID |
|||
3 3 3 |
|||
3 3 3 |
|||
3 3 3 |
|||
Add sandpile 3ID to sandpile 3ID |
|||
2 1 2 |
|||
1 0 1 |
|||
2 1 2 |
|||
</pre> |
|||
=={{header|C++}}== |
=={{header|C++}}== |