Construir una pila de arena

59

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.

Eric Tressler
fuente
2
¿Puede la entrada t ser 0? ¿Cuál es la salida entonces?
Luis Mendo
1
¿Es correcto que en un paso de tiempo dado puedan tener lugar varias cascadas seguidas? Entonces, ¿en ese paso de tiempo las cascadas siguen sucediendo hasta que cada celda vuelva a ser 3 o menos?
flawr
2
@flawr: Sí, eso sería correcto. Mira la diferencia entre t = 15 y t = 16.
El'endia Starman el
@LuisMendo La entrada se especifica como t positiva , por lo que cero no es una entrada válida.
Eric Tressler
1
¿Es REALMENTE eso necesario tener .celdas vacías? ¿Podemos tener 0como una celda vacía válida?
Andreï Kostyrka

Respuestas:

56

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:

Pila de arena abeliana después de 1000 pasos

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

Pila de arena de Abelian después de 50000 pasos

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

Pila de arena abeliana después de 100000 pasos

¡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 ( Tasa de crecimientocalculé 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):

Iteración promedio hasta que la pila se asiente

Tiempo aproximado de cálculo

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.

Andreï Kostyrka
fuente
1
Entiendo su punto sobre la columna adicional, los índices de fila que está generando, pero creo que quiero restringir el resultado a solo ser "la respuesta", y nada más. Sin embargo, me alegra que hayas incluido fotos.
Eric Tressler
1
Buena respuesta Andreï! Sin embargo, definitivamente podría jugar unos pocos bytes, por ejemplo rep(), predefiniendo , dado que lo usa 6 veces. En segundo lugar, no creo que necesite escribir la arr.ind=Topción para la which()función. Simplemente use which(...,T).
Billywob
1
Puede ser más golfoso definir n=numericy usar eso en su lugar, ya que n(k)tiene menos caracteres que r(0,k). Aunque me gustan las fotos.
JDL
1
Otra sugerencia: 1%*%0tiene menos caracteres que array(0,c(1,1)). Además, el segundo argumento para u <- cbindsolo puede ser 1, cbindlo extenderá a la longitud del primer argumento por defecto.
JDL
1
@GregMartin Solucionó esto. Lo siento por eso; en mi primer idioma, usamos la palabra "self's" y nunca nos preocupamos por el género de la persona en cuestión (como "un pequeño paso para un hombre"); aún así, a veces, en muy raras ocasiones, llamo a un perro "ella" o "él", mientras que debería ser "eso", a menos que, como, usted sea el dueño y realmente quiera enfatizar el sexo de su animal ( a pesar de que diferenciar a un hombre de una mujer no es tan difícil).
Andreï Kostyrka
13

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:

ingrese la descripción de la imagen aquí

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
Luis Mendo
fuente
3
Estoy celoso de 1Y6.
flawr
1
@flawr Pero tu ~mod(spiral(3),2)es mucho más inteligente :-)
Luis Mendo
11

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.

falla
fuente
v=any(z)en lugar de v=find(sum(z))(estoy usando eso en mi respuesta). Además, en 2*~zlugar de(z<1)*2
Luis Mendo
Mi computadora se congeló en la entrada n=500... Se había estado procesando n=400durante varios segundos. ¿Estoy haciendo algo mal?
Andreï Kostyrka
@ AndreïKostyrka Funciona para mí (Matlab R2015b)
Luis Mendo
1
@ AndreïKostyrka Para una entrada de neste programa genera una 3*n x 3*nmatriz, por lo que necesita almacenar sobre los 9*n^2números. También es totalmente ineficiente, porque también tenemos una iteración larga totalmente innecesaria desde 1 hasta n. Pero, de nuevo, esto es código golf , hacer que un programa sea eficiente es una taza de té diferente.
flawr
@ AndreïKostyrka Puede hacer que su memoria sea más eficiente utilizando matrices dispersas (segunda línea:) z=sparse(zeros(2*n+1))y cambiando el bucle for a while any(z(:)>3). A continuación, puede calcular también quizás el núcleo de convolución sólo una vez: kern = 1-mod(spiral(3),2).
flawr
9

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

n = 100

DenDenDo
fuente
Me sale el siguiente error al ejecutar el código: ImportError: No module named convolve2d. Cambiar import scipy.signal.convolve2d as ca from scipy.signal import convolve2d as cresuelve el problema. Estoy usando la versión 0.16.1 de scipy, ¿necesito una versión anterior o anterior? ¿O el problema es algo más?
Andrew Epstein
raro, ahora que mencionas que ya no funciona para mí. Probablemente lo hice bien la primera vez en modo interactivo, luego lo acorté e ignoré el error, pero la función permaneció en la memoria
DenDenDo
6

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$_}{
Ton Hospel
fuente
5

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.

Andrew Epstein
fuente
Creo que puedes mover la asignación de a,x,ra los argumentos de la función.
Loovjo
1
He descifrado tu código unos pocos bytes ... no es mucho, pero tendrá que funcionar. ¿Te importa si pongo una edición en tu respuesta y si cambio la versión de Python a Python 2?
clismique
@ Qwerp-Derp: ¡Siéntete libre! Me encantaría ver lo que has hecho.
Andrew Epstein
3

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)">

hetzi
fuente
1
Advertencia: presioné 'ejecutar' sin entrada, y mi pantalla se bloqueó (bucle infinito). No seas tan tonto como yo.
roberrrt-s
1
@Roberrrt Actualicé mi respuesta para evitar esto.
hetzi
3

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
Danny Kirchmeier
fuente
3

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
AmazingDreams
fuente
Mi programa sugiere que, centrada en (0,0), la pila de arena primero alcanza un radio de 15 en t = 1552. Eso requeriría una matriz de 31x31 para almacenar (coordenadas -15 a 15 inclusive). ¿Estás seguro de que esto es correcto a través de t = 5000?
Eric Tressler
No estoy seguro de que esto sea correcto, aunque creo que tengo la lógica correcta? Obtengo una excepción de índice de matriz fuera de límites en t> 5593
AmazingDreams
Cuando incremente y luego verifique inmediatamente si hay derrames, se sale de los límites en t = 1552. Yo diría que esa es la implementación correcta. Actualicé el código.
AmazingDreams
Su rendimiento solo se puede superar mediante la manipulación directa de la matriz en C o Fortran con la optimización del compilador. Te envidio.
Andreï Kostyrka
@ AndreïKostyrka, sí, ¡aquí es donde brilla la escala! Sin embargo, mi salida no se ajusta a las especificaciones, así que tendría que trabajar en eso
AmazingDreams
2

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.

figura

millas
fuente
2

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]));}
Jerry Jeremiah
fuente
Bien, me rindo: ¿por qué su matriz es 99 por 98?
Eric Tressler
@EricTressler ¿Cómo no encontré eso en las pruebas?
Jerry Jeremiah
1

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.

Titus
fuente