^{(Existem perguntas relacionadas sobre arquivos de areia infinitos e a localização de elementos de identidade de arquivos de areia .)}

Dada uma matriz de números inteiros não negativos, retorne uma matriz das mesmas dimensões, mas tombou :

1. Se a matriz não contiver valores maiores que 4, retorne-a.
2. Cada "célula" maior que 3 é reduzida em 4 e todas as células vizinhas diretamente (acima, abaixo, esquerda e direita) são incrementadas, se existirem.
3. GOTO 1.

Exemplos:

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

(Você só precisa retornar o resultado final. O caminho em que você o alcança pode diferir do mostrado aqui: não importa em que ordem você executa as operações de tombamento, todos eles levam ao mesmo resultado.)

Para uma explicação mais profunda e alguma motivação, consulte este vídeo do Numberphile ou o artigo da Wikipedia sobre o modelo de pilha de areia abeliana .

Regras:

• Você pode receber entrada e saída de qualquer uma das maneiras padrão
• As brechas são proibidas
• Entrada e saída podem ser:
  • uma lista aninhada: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
  • uma lista simples: [1, 2, 3, 4, 5, 6, 7, 8, 9]e a forma
  • algum tipo de matriz nativa
  • uma string, por exemplo 1 2 3\n4 5 6\n7 8 9
  • ou qualquer outra coisa que funcione no seu idioma.
• Entrada e saída devem estar na mesma forma
• A entrada pode conter números maiores que os mostrados aqui, mas o tamanho pode estar limitado pelos limites do seu idioma (equivalentes MAXINT, se aplicável)
• A matriz pode ter qualquer formato (por exemplo, 1x1, 2x2, 3x3, 4x4, 2x7, 11x3, ...)
• Você não precisa lidar com o caso em que a forma é 0xN ou Nx0.

Casos de teste

[[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 é o codegolf , o código mais curto (por idioma) vence.

MATL , 17 bytes

tss:"t3>t1Y6Z+w4*-+

Experimente no MATL Online! Ou verifique todos os casos de teste .

Explicação

O programa itera quantas vezes for a soma da entrada. Esse é um limite superior frouxo no número necessário de iterações.

Para cada iteração, 3são detectadas entradas na matriz de pilha de areia excedentes , fornecendo uma matriz de 1e 0, que é convoluída com a máscara de 4 vizinhos. As entradas que excedem 3a matriz de pilha de areia são reduzidas 4e o resultado da convolução é adicionado.

Nas últimas iterações, nas quais a matriz de pilha de areia não possui números excedentes 3, os zeros são subtraídos e adicionados a ela, portanto, não são afetados.

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

Mathematica, 65 bytes

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

Explicação

#//.s_:>...&

Transforme a entrada repetidamente, derrubando todas as pilhas maiores que 3. Esse processo para automaticamente quando a transformação falha na alteração da matriz (ou seja, quando não existem mais pilhas grandes). Na expressão a seguir, a matriz é chamada s.

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

Crie uma matriz que tenha um 1sempre que a matriz atual tiver um 4ou maior e um zero caso contrário. Esta é essencialmente uma máscara que indica quais pilhas precisam ser derrubadas. Ligue para a máscara x.

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

Primeiro, calculamos o número de areia que é adicionada a cada pilha devido a pilhas vizinhas tombadas. Isso é feito com uma convolução da seguinte matriz x:

0 1 0
1 0 1
0 1 0

Essencialmente, ele adiciona um à célula atual para cada um de seus vizinhos von-Neumann na máscara.

s+...-4x

Adicionamos o resultado anterior se subtraímos quatro vezes a máscara para reduzir as pilhas derrubadas.

Oitava, 65 bytes

Isso não parece muito bom, devo estar perdendo alguns truques ...

m=input(0);do;m+=conv2(m>3,[0 1 0;1 -4 1;0 1 0],"same")
until m<4

JavaScript (ES6), 101 95 bytes

Pega a largura da matriz we uma matriz de valores ana sintaxe de curry (w)(a). Retorna uma 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)

Formatado e 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 teste

let f =

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)

console.log(JSON.stringify(f(3)([2, 5, 4, 8, 6, 4, 1, 2, 3]))); // -> [3, 3, 0, 1, 2, 2, 1, 3, 2]
console.log(JSON.stringify(f(3)([0, 0, 2, 1, 3, 3, 0, 0, 0]))); // -> [0, 0, 2, 1, 3, 3, 0, 0, 0]
console.log(JSON.stringify(f(3)([9, 9, 9, 9, 9, 9, 9, 9, 9]))); // -> [1, 3, 1, 3, 1, 3, 1, 3, 1]
console.log(JSON.stringify(f(2)([4, 5, 2, 3]))); // -> [2, 3, 0, 1]
console.log(JSON.stringify(f(3)([2, 3, 5, 2, 2, 0]))); // -> [3, 0, 2, 2, 3, 1]
console.log(JSON.stringify(f(1)([7]))); // -> [3]

JavaScript (ES6), 118 114 104 bytes

Guardado 2 bytes graças 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

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;}

Pega a entrada como referência a um vetor de vetores e a modifica diretamente.

Experimente online!