Una pila de arena abeliana , para nuestros propósitos, es una cuadrícula infinita con coordenadas enteras, inicialmente vacía de arena. Después de cada segundo, se coloca un grano de arena a (0,0). Cada vez que una celda de cuadrícula tiene 4 o más granos de arena, derrama un grano de arena a cada uno de sus cuatro vecinos simultáneamente. Los vecinos de (x, y) son (x-1, y), (x + 1, y), (x, y-1) y (x, y + 1).

Cuando una célula se derrama, puede provocar que sus vecinos se derramen. Algunos hechos:

• Esta cascada finalmente se detendrá.
• El orden en que se derraman las células es irrelevante; El resultado será el mismo.

Ejemplo

Después de 3 segundos, la cuadrícula se ve como

.....
.....
..3..
.....
.....

Después de 4 segundos:

.....
..1..
.1.1.
..1..
.....

Después de 15 segundos:

.....
..3..
.333.
..3..
.....

Y después de 16 segundos:

..1..
.212.
11.11
.212.
..1..

El reto

En el menor número de bytes posible, escriba una función que tome un solo entero positivo t y genere una imagen de la pila de arena después de t segundos.

Entrada

Un solo entero positivo t , en cualquier formato que elija.

Salida

Una imagen de la pila de arena después de t segundos, usando los caracteres

 . 1 2 3

Editar: utilice los cuatro caracteres distintos que desee o dibuje una imagen. Si no está utilizando ".123" o "0123", especifique en su respuesta lo que significan los caracteres.

A diferencia de los ejemplos, su salida debe contener el número mínimo de filas y columnas necesarias para mostrar la parte distinta de cero de la pila de arena.

Es decir, para la entrada 3, la salida debe ser

 3

Para 4, la salida debe ser

 .1.
 1.1
 .1.

Puntuación

Se aplica la puntuación estándar de golf.

Reglas

No se permiten funciones de lenguaje ni bibliotecas que ya sepan qué es un sandpile.

Editar: la sección de salida se ha editado, la restricción del juego de caracteres se ha eliminado por completo. Usa cuatro caracteres o colores distintos que te gusten.

R, 378 343 297 291 bytes

Como generalmente, el usuario proporciona su entrada a través de scan()(ya usé la variable t, así que tomemos en su zlugar), por lo que la segunda línea debe iniciarse por separado y luego el resto:

e=numeric
a=1%*%scan()
x=1
o=a>3
n=1
while(any(o)){
v=which(o,T)
if(any(v==1)){a=rbind(e(n+2),cbind(e(n),a,e(n)),e(n+2));x=x+1;n=n+2;v=which(a>3,T)}
q=nrow(v)
u=cbind(e(q),1)
l=v-u[,1:2];r=v+u[,1:2];t=v-u[,2:1];b=v+u[,2:1]
a[l]=a[l]+1;a[r]=a[r]+1;a[t]=a[t]+1;a[b]=a[b]+1
a[v]=a[v]-4
o=a>3}
a

Emite una matriz que contiene los valores de aen tla generación th (0, 1, 2 o 3).

Casos de prueba:

z=3
     [,1]
[1,]    3
z=4
     [,1] [,2] [,3]
[1,]    0    1    0
[2,]    1    0    1
[3,]    0    1    0
z=16
     [,1] [,2] [,3] [,4] [,5]
[1,]    0    0    1    0    0
[2,]    0    2    1    2    0
[3,]    1    1    0    1    1
[4,]    0    2    1    2    0
[5,]    0    0    1    0    0

Nos ayuda que esta cosa sea simétrica tanto vertical como horizontalmente, lo que significa que el punto más a la izquierda tiene una altura de 4, esto significa que los puntos más altos, más a la derecha y más bajos también son 4.

Ah, y ¿te dije que puedes hacer hermosas visualizaciones?

Después de 1000 gotas:

Después de 50000 gotas (≈4 segundos):

Después de 333333 gotas (≈15 minutos):

¡Tú también puedes dibujarlo!

image(1:n,1:n,a,col=colorRampPalette(c("#FFFFFF","#000000"))(4), axes=F, xlab="", ylab="")

Esto tardó 4 segundos para 10000 iteraciones, pero se ralentiza considerablemente para tamaños de matriz más grandes (por ejemplo, un par de minutos para 100000 iteraciones). Es por eso que se vuelve tan lento ( calculé la tasa de crecimiento como en y obtuve τ (i) ≈689 · i ^ 1.08, por lo que el tiempo promedio por grano adicional hasta que la pila de arena se asiente después del ipaso es ligeramente mayor que uno) , y el tiempo total en función del número de granos crece un poco más lento que cuadráticamente (T (i) ≈0.028 * i ^ 1.74):

Y ahora con una explicación completa:

e=numeric # Convenient abbreviation for further repeated use
a=1%*%scan() # Creates a 1×1 array with a user-supplied number
x=1 # The coordinate of the centre
o=a>3 # Remember which cells were overflown
n=1 # Array height that is going to change over time
while(any(o)){ # If there is still any overflow
  v=which(o,T) # Get overflown cells' indices
  if(any(v==1)){ # If overflow occurred at the border, grow the array
    a=rbind(e(n+2),cbind(e(n),a,e(n)),e(n+2)) # Growing
    x=x+1 # Move the centre
    n=n+2 # Change the height
    v=which(a>3,T) # Re-index the overflowed cells
    }
  q=nrow(v) # See how many indices are overflown
  u=cbind(e(q),1) # Building block for neighbours' indices
  l=v-u[,1:2];r=v+u[,1:2];t=v-u[,2:1];b=v+u[,2:1] # L, R, T, B neighbours
  a[l]=a[l]+1;a[r]=a[r]+1;a[t]=a[t]+1;a[b]=a[b]+1 # Increment neighbours
  a[v]=a[v]-4 # Remove 4 grains from the overflown indices
  o=a>3} # See if still overflown indices remain
a # Output the matrix

Esta es la primera vez en mi vida cuando el crecimiento de objetos (como a <- c(a, 1)) funciona mucho más rápido que preasignar una matriz grande vacía para valores y llenarla gradualmente con una tonelada de ceros sin usar.

Actualizar. Golfed 18 bytes mediante la eliminación arr.inden whichdebido a Billywob y reemplazar rep(0,n)con e=numeric;e(n)en 5 casos debido a JDL , y 17 bytes más debido a JDL .

Actualización 2. Como la pila de arena es abeliana, puede comenzar con una pila de altura deseada, por lo que eliminé el bucle redundante y obtuve un gran impulso en la productividad.

MATL , 55 53 48 43 42 bytes

Inspirado por la respuesta de @ flawr .

Salida gráfica :

0i:"Gto~+XytP*+t"t4=t1Y6Z+b+w~*]]tat3$)1YG

¡Pruébalo en MATL Online! . La entrada tarda unos 10 segundos 30. Es posible que deba actualizar la página y presionar "Ejecutar" nuevamente si no funciona.

Aquí hay un resultado de ejemplo para la entrada 100:

Salida ASCII (43 bytes) :

0i:"Gto~+XytP*+t"t4=t1Y6Z+b+w~*]]tat3$)48+c

Pruébalo en línea!

Explicación

0          % Push a 0. This is the initial array. Will be resized in first iteration
i:         % Take input n. Generate range [1 2 ... n]
"          % For each, i.e. repeat n times
  Gto~+    %   Push input and add negate parity. This "rounds up" n to odd number
           %   m = n or n+1
  Xy       %   Identity matrix with that size
  tP*      %   Multiply element-wise by vertically flipped copy. This produces a
           %   matrix with a 1 in the center and the rest entries equal to 0
  +        %   Add to previous array. This updates the sandpile array
  t        %   Duplicate
  "        %   For each column (i.e. repeat m times)
    t4=    %     Duplicate. Compare with 4 element-wise. This gives a 2D mask that
           %     contains 1 for entries of the sandpile array that equal 4, and 0
           %     for the rest
    t      %     Duplicate
    1Y6    %     Predefined literal: [0 1 0; 1 0 1; 0 1 0]
    Z+     %     2D convolution, maintaining size
    b      %     Bubble up to bring sandpile array to top
    +      %     Element-wise addition. This adds 1 to the neighbours of a 4
    w      %     Swap to bring copy of mask to top
    ~*     %     Multiply bu negated mask. This removes all previous 4
  ]        %  End
]          % End
t          % Duplicate the updated sandpile array
a          % 1D mask that contains 1 for columns that contain a 1. This will be
           % used as a logical index to select columns
t          % Duplicate. This will be used as logical index to select rows (this
           % can be done because of symmetry)
3$)        % Keep only those rows and columns. This trims the outer zeros in the
           % sandpile array
1YG        % Display as scaled image

Matlab, 160 156 148 bytes

n=input('');z=zeros(3*n);z(n+1,n+1)=n;for k=1:n;x=z>3;z=z+conv2(+x,1-mod(spiral(3),2),'s');z(x)=z(x)-4;end;v=find(sum(z));z=z(v,v);[z+48-(z<1)*2,'']

Primero se crea una matriz demasiado grande, con nel medio en alguna parte. Luego, la cascada se calcula con una convolución 2D muy conveniente. Al final, el exceso se recorta y todo se convierte en una cadena.

Ejemplo de salida para t=100

...121...
..32.23..
.3.323.3.
123.3.321
2.23.32.2
123.3.321
.3.323.3.
..32.23..
...121...

Como siempre:

La convolución es la clave del éxito.

Pitón 2, 195 +1 +24 = 220217

from pylab import*
ifrom scipy.signal import convolve2d as c
k=(arange(9)%2).reshape(3,3)
def f(n):g=zeros((n,n),int);g[n/2,n/2]=n;exec"g=c(g/4,k,'same')+g%4;"*n;return g[any(g,0)].T[any(g,0)]

salida para n = 16

array([[0, 0, 1, 0, 0],
       [0, 2, 1, 2, 0],
       [1, 1, 0, 1, 1],
       [0, 2, 1, 2, 0],
       [0, 0, 1, 0, 0]])

hay MUCHO relleno e iteraciones innecesarias, al usar ncomo límite superior "suficientemente bueno", pero n = 200 aún se completa en un segundo yn = 500 en aproximadamente 12 segundos

sin golf

from pylab import*
from scipy.signal import convolve2d as c
k=array([0,1,0],
        [1,0,1],
        [0,1,0])
def f(n):
  g=zeros((n,n))                 # big grid of zeros, way bigger than necessary
  g[n/2,n/2]=n                   # put n grains in the middle
  exec"g=c(g/4,k,'same')+g%4;"*n # leave places with <4 grains as is, convolve the rest with the kernel k, repeat until convergence (and then some more)
  return g[any(g,0)].T[any(g,0)] # removes surrounding 0-rows and columns

reemplazar return xpor imshow(x)agrega un carácter y genera una imagen interpolada fea, agregando imshow(x,'gray',None,1,'nearest')elimina la interpolación borrosa que lleva la salida a las especificaciones

Perl, 157 147 bytes

Incluye +1 para -p

Ejecutar con el recuento en STDIN, imprime el mapa con 0123STDOUT:

sandpile.pl <<< 16

sandpile.pl:

#!/usr/bin/perl -p
map{++substr$_,y///c/2-1,1;/4
/?$.+=s%^|\z%0 x$..$/%eg+!s/\b/0/g:s^.^$&%4+grep{3<substr$\,0|$_+"@+",1}-$.-2,-2,0,$.^eg while/[4-7]/}($\="0
")x$_}{

Python 3 2, 418 385 362 342 330 bytes

w='[(i,j)for i in r(n)for j in r(n)if a[i][j]>3]'
def f(z):
 a,x,r=[[z]],0,range
 for _ in[0]*z:
  n=len(a);v=eval(w)
  if[1for b,c in v if(b==0)+(c==0)]:n+=2;a=[[0]*n]+[[0]+a[i]+[0]for i in r(n-2)]+[[0]*n];x+=1;v=eval(w)
  for c,d in v:exec'a[c+%s][d+%s]+=1;'*4%(-1,0,1,0,0,-1,0,1);a[c][d]-=4
 for i in a:print''.join(map(str,i))

Editar: guardado 6 bytes gracias a @ Qwerp-Derp

Todo el crédito a @ Andreï Kostyrka, ya que esta es una traducción directa de su código R a Python.

JavaScript, 418 416 406 400 393 bytes

Crea una función anónima que muestra el resultado en la consola.

var f =
    t=>{a=(q,w)=>Math.max(q,w);c=_=>{x=a(p[0],x);y=a(p[1],y);m[p]=(g(p)+1)%4;if(!m[p]){s.push([p[0],p[1]]);}};x=y=0,m={};g=k=>{v=m[k];return!v?0:v;};m[o=[0,0]]=1;s=[];while(--t){m[o]=(m[o]+1)%4;if(!m[o]){s.push(o);}while(s.length){p=s.pop();p[0]++;c();p[0]-=2;c();p[0]++;p[1]++;c();p[1]-=2;c();p[1]++;}}s='';for(i=-x;i<=x;i++){for(j=-y;j<=y;j++){v=g([i,j]);s+=v==0?'.':v;}s+='\n';}console.log(s);}

<input id="i" type="number"><input type="button" value="Run" onclick="var v = +document.getElementById('i').value; if (v>0) f(v)">

Nim, 294 caracteres

import os,math,sequtils,strutils
var
 z=parseFloat paramStr 1
 y=z.sqrt.toInt+1
 w=y/%2
 b=y.newSeqWith newSeq[int] y
 x=0
proc d(r,c:int)=
 b[r][c]+=1;if b[r][c]>3:b[r][c]=0;d r-1,c;d r,c+1;d r+1,c;d r,c-1
for i in 1..z.toInt:d w,w
while b[w][x]<1:x+=1
for r in b[x..< ^x]:echo join r[x..< ^x]

Compilar y ejecutar:

nim c -r sandbox.nim 1000

Notas:

1. Pude crear una versión más corta que usa un tamaño de tabla fijo, pero la edité a favor de la dinámica.
2. Una vez que se calcula el sandbox, xse calcula como el número de columnas cero al comienzo de la fila central.
3. Para la visualización, la tabla se divide al excluir xfilas y columnas de cada extremo.

Actuación

nim c --stackTrace:off --lineTrace:off --threads:off \ 
      --checks:off --opt:speed sandbox.nim

time ./sandbox   10000       0.053s
time ./sandbox   20000       0.172s
time ./sandbox   30000       0.392s
time ./sandbox   40000       0.670s
time ./sandbox  100000       4.421s
time ./sandbox 1000000    6m59.047s

Scala, 274 bytes

val t=args(0).toInt
val s=(Math.sqrt(t)+1).toInt
val (a,c)=(Array.ofDim[Int](s,s),s/2)
(1 to t).map{_=> ?(c,c)}
println(a.map{_.mkString}.mkString("\n"))
def?(b:Int,c:Int):Unit={
a(b)(c)+=1
if(a(b)(c)<4)return
a(b)(c)=0
?(b+1,c)
?(b-1,c)
?(b,c+1)
?(b,c-1)
}

Uso:

scala sandpile.scala <iterations>

No creo que haya mucho que explicar sobre este. Básicamente solo agrega un grano de arena al centro. Luego verifica si es mayor que 4, si es así, se desbordará y verificará si todos los vecinos tienen más de 4, se desbordarán, etc. Es bastante rápido.

Actuación:

• t = 10000 72ms
• t = 20000 167 ms
• t = 30000 419 ms
• t = 40000 659 ms
• t = 100000 3413 ms
• t = 1000000 aproximadamente 6 minutos

J, 76 bytes

p=:0,.~0,.0,~0,]
p`(4&|+3 3([:+/@,*&(_3]\2|i.9));._3[:<.4%~p)@.([:*/4>{.)^:_

Defino un verbo pque rellena un borde de ceros alrededor de la entrada. El verbo principal toma una matriz como entrada. Luego verifica la primera fila por cualquier pila de arena que contenga 4 o más granos. Si uno lo hace, genera la misma matriz, excepto que se usa con relleno p, y de lo contrario realiza una convolución 2D para simular la caída de granos. El verbo principal se repite hasta la convergencia usando el operador de potencia ^:_.

Uso

   p =: 0,.~0,.0,~0,]
   f =: p`(4&|+3 3([:+/@,*&(_3]\2|i.9));._3[:<.4%~p)@.([:*/4>{.)^:_
   f 15
0 3 0
3 3 3
0 3 0
   f 50
0 0 0 1 0 0 0
0 0 3 1 3 0 0
0 3 2 2 2 3 0
1 1 2 2 2 1 1
0 3 2 2 2 3 0
0 0 3 1 3 0 0
0 0 0 1 0 0 0
   timex 'r =: f 50000'
46.3472
   load 'viewmat'
   ((256#.3&#)"0<.255*4%~i._4) viewmat r

Se tarda unos 46 segundos en calcular el resultado para n = 50000, y el resultado se puede mostrar usando el viewmatcomplemento con un esquema de color monocromo.

C 229 (con muchas advertencias)

G[99][99],x,y,a=99,b=99,c,d;S(x,y){if(++G[y][x]>3)G[y][x]=0,S(x+1,y),S(x-1,y),S(x,y+1),S(x,y-1);a=x<a?x:a;b=y<b?y:b;c=x>c?x:c;d=y>d?y:d;}F(t){for(;t--;)S(49,49);for(y=b;y<=d;y++){for(x=a;x<=c;x++)printf("%d ",G[y][x]);puts("");}}

/* call it like this */
main(_,v)char**v;{F(atoi(v[1]));}

APL (Dyalog Unicode) , ^{SBCS de} 51 bytes

{m⌿r/⍨m←⌈/×r←(4∘|+{+/⊢/4 2⍴⌊⍵÷4}⌺3 3)0,∘⍉∘⌽⍣4⊢⍵}⍣≡⍪

Pruébalo en línea!

PHP, 213 bytes

function d($x,$y){global$p,$m;$m=max($m,$x);$q=&$p[$y][$x];if(++$q>3){$q=0;d($x+1,$y);d($x-1,$y);d($x,$y+1);d($x,$y-1);}}while($argv[1]--)d(0,0);for($y=-$m-1;$y++<$m;print"\n")for($x=-$m;$x<=$m;)echo+$p[$y][$x++];

recursivamente crea la pila adentro $p, recordando el tamaño adentro $m; luego imprime con bucles anidados.
Corre con -r.