Derribar la pila de arena

12

(Hay preguntas relacionadas sobre pilas de arena infinitas y la búsqueda de elementos de identidad de pilas de arena ).

Dada una matriz de enteros no negativos, devuelve una matriz de las mismas dimensiones, pero derribada :

  1. Si la matriz no contiene ningún valor mayor que 4, devuélvalo.
  2. Cada "celda" que es mayor que 3 se reduce en 4, y todas las celdas directamente vecinas (arriba, abajo, izquierda y derecha) se incrementan, si existen.
  3. GOTO 1.

Ejemplos:

0 1 0        0 2 0
2 4 0   ->   3 0 1
0 0 3        0 1 3

1 2 3    2 3 4    2 5 1    4 1 2    0 3 3    0 3 3    0 3 3
4 5 6 -> 2 4 4 -> 4 2 3 -> 0 5 4 -> 3 2 1 -> 3 3 1 -> 3 3 2
7 8 9    5 7 7    2 6 5    4 3 2    0 5 3    1 1 4    1 2 0

(Solo necesita devolver el resultado final. La ruta en la que lo alcanza puede diferir de la que se muestra aquí: no importa en qué orden realice las operaciones de caída, todos conducen al mismo resultado).

Para una explicación más profunda y alguna motivación, vea este video de Numberphile o el artículo de Wikipedia sobre el modelo de pila de arena de Abelian .

Reglas:

  • Puede tomar entrada y salida de cualquiera de las formas estándar
  • Las lagunas están prohibidas
  • La entrada y la salida pueden ser:
    • una lista anidada: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
    • una lista simple: [1, 2, 3, 4, 5, 6, 7, 8, 9]y la forma
    • algún tipo de matriz nativa
    • una cadena, por ejemplo 1 2 3\n4 5 6\n7 8 9
    • o cualquier otra cosa que funcione en tu idioma.
  • La entrada y la salida deben estar en la misma forma
  • La entrada puede contener números más grandes que los que se muestran aquí, pero el tamaño puede estar limitado por los límites de su idioma (equivalentes MAXINT, si corresponde)
  • La matriz puede tener cualquier forma (por ejemplo, 1x1, 2x2, 3x3, 4x4, 2x7, 11x3, ...)
  • No necesita manejar el caso donde la forma es 0xN o Nx0.

Casos de prueba

[[2, 5, 4], [8, 6, 4], [1, 2, 3]] -> [[3, 3, 0], [1, 2, 2], [1, 3, 2]]
[[0, 0, 2], [1, 3, 3], [0, 0, 0]] -> [[0, 0, 2], [1, 3, 3], [0, 0, 0]]
[[9, 9, 9], [9, 9, 9], [9, 9, 9]] -> [[1, 3, 1], [3, 1, 3], [1, 3, 1]]
[[4, 5], [2, 3]] -> [[2, 3], [0, 1]]
[[2, 3, 5], [2, 2, 0]] -> [[3, 0, 2], [2, 3, 1]]
[[7]] -> [[3]]

Este es , el código más corto (por idioma).

L3viatán
fuente
¿Está bien mostrar todos los resultados intermedios?
feersum
@feersum supongo que sí, siempre que esté claro cuál es el resultado final.
L3viathan

Respuestas:

8

MATL , 17 bytes

tss:"t3>t1Y6Z+w4*-+

¡Pruébalo en MATL Online! O verificar todos los casos de prueba .

Explicación

El programa itera tantas veces como la suma de la entrada. Este es un límite superior suelto en el número requerido de iteraciones.

Para cada iteración, 3se detectan entradas en la matriz sandpile que exceden , dando una matriz de 1y 0, que está enredada con la máscara de 4 vecinos. Las entradas que exceden 3en la matriz sandpile se reducen 4y se agrega el resultado de la convolución.

Para las últimas iteraciones, en las que la matriz sandpile no tiene ningún número superior 3, los ceros se restan y se agregan a ella, por lo que no se ve afectada.

t       % Implicit input (matrix). Duplicate
ss      % Sum of matrix entries
:"      % Repeat that many times
  t     %   Duplicate
  3>    %   True for matrix entries that exceed 3
  t     %   Duplicate
  1Y6   %   Push predefined literal [0, 1, 0; 1, 0, 1; 0, 1, 0]
  Z+    %   2D convolution, keeping size
  w     %   Swap
  4*    %   Multiply by 4
  -     %   Subtract
  +     %   Add
        % Implicit end. Implicit display
Luis Mendo
fuente
3
Convolución choca esos cinco.
Martin Ender
@MartinEnder Ah, también usaste eso :-) ¡Qué bueno ver a un compañero intrépido! Estoy seguro de que flawr se unirá a nosotros pronto
Luis Mendo
2
@LuisMendo Convolutionista
Suever
4

Mathematica, 65 bytes

#//.s_:>s+ListConvolve[{v={0,1,0},1-v,v},x=UnitStep[s-4],2,0]-4x&

Explicación

#//.s_:>...&

Transforme repetidamente la entrada derribando todas las pilas mayores que 3. Este proceso se detiene automáticamente cuando la transformación no puede cambiar la matriz (es decir, cuando ya no existen pilas grandes). En la siguiente expresión se llama matriz s.

...x=UnitStep[s-4]...

Cree una matriz que tenga 1siempre que la matriz actual tenga uno 4o más, y un cero en caso contrario. Esto es esencialmente una máscara que indica qué pilas deben ser derribadas. Llama a la máscara x.

ListConvolve[{v={0,1,0},1-v,v},x=UnitStep[s-4],2,0]

Primero calculamos el número de arena que se agrega a cada pila debido a las pilas vecinas derribadas. Esto se hace con una convolución de la siguiente matriz sobre x:

0 1 0
1 0 1
0 1 0

Esencialmente, agrega uno a la celda actual para cada uno de sus vecinos von-Neumann en la máscara.

s+...-4x

Agregamos el resultado anterior sy luego le restamos cuatro veces la máscara para reducir las pilas derribadas.

Martin Ender
fuente
3

Octava, 65 bytes

Esto no parece muy bueno, debo estar perdiendo algunos trucos ...

m=input(0);do;m+=conv2(m>3,[0 1 0;1 -4 1;0 1 0],"same")
until m<4
Feersum
fuente
¿Qué versión de Octave estás usando que permita input(0)?
Suever
@Suever>> version ans = 4.0.1
feersum
2

JavaScript (ES6), 101 95 bytes

Toma el ancho de la matriz wy una matriz de valores aen la sintaxis de curry (w)(a). Devuelve una matriz de valores.

w=>g=a=>(b=a.map((n,i)=>n%4+(F=d=>~m|i%w&&a[i+d]>>2)(m=w)+F(-w)+F(m=-1)+F(!++i)))+0==a+0?a:g(b)

Formateado y comentado

w =>                      // main function: takes w as input, returns g
  g = a =>                // recursive function g: takes a as input
    (                     //
      b = a.map((n, i) => // for each element n at position i in a:
        n % 4 + (         //   keep only n MOD 4
          F = d =>        //   define F(): function that takes d as input
            ~m |          //     if m is not equal to -1
            i % w &&      //     or i MOD w is not null:
            a[i + d] >> 2 //       return a fourth of the value of the cell at i + d
        )(m = w) +        //   test the cell below the current cell
        F(-w) +           //   test the cell above
        F(m = -1) +       //   test the cell on the left
        F(!++i)           //   test the cell on the right
      )                   // end of map(): assign the result to b
    ) + 0 == a + 0 ?      // if b is equal to a:
      a                   //   stop recursion and return a
    :                     // else:
      g(b)                //   do a recursive call with b

Casos de prueba

Arnauld
fuente
1

JavaScript (ES6), 118 114 104 bytes

Guardado 2 bytes gracias a @Neil

f=a=>a.find(b=>++y&&b.find(c=>++x&&c>3,x=0),y=0)?f(a.map(b=>b.map(c=>c+=--i|y?i*i+y*y==1:-4,i=x,--y))):a
ETHproductions
fuente
Ciervas (i-=x)|y-j?i*i+ayuda?
Neil
@Neil De hecho, gracias!
ETHproductions
... Estaba hablando por teléfono pero también estaba considerando a.find(...b.find(...c>3&&a.map(...)))&&f(a).
Neil
@Neil, no creo que funcione, ya .mapque no muta ...
ETHproductions
Parece que hacer que mute cuesta un poco menos que mover el mapa dentro de las búsquedas guardadas:f=a=>a.find((b,x)=>b.find((c,y)=>c>3&&a.map(b=>b.map((_,j)=>b[j]+=x|(j-=y)?x*x+j*j==1:-4)&x--)))&&f(a)
Neil
1

C ++, 261 258 250 bytes

#import<vector>
#define S size()
void f(std::vector<std::vector<int>>&m){s:int i,j,r;for(i=r=0;i<m.S;++i)for(j=0;j<m[i].S;++j){if(m[i][j]>3){r=1;m[i][j]-=4;j>0&&m[i][j-1]++;i>0&&m[i-1][j]++;j<m[i].S-1&&m[i][j+1]++;i<m.S-1&&m[i+1][j]++;}}if(r)goto s;}

Toma la entrada como referencia a un vector de vectores y lo modifica directamente.

Pruébalo en línea!

Steadybox
fuente