^{(Есть связанные вопросы о бесконечных песчаных кучах и поиске элементов идентичности песочных куч .)}

Если задана матрица неотрицательных целых чисел, верните матрицу тех же размеров, но свергнутую :

1. Если матрица не содержит значений больше 4, верните ее.
2. Каждая «ячейка», которая больше 3, уменьшается на 4, и все непосредственно соседние ячейки (сверху, снизу, слева и справа) увеличиваются, если они существуют.
3. GOTO 1.

Примеры:

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

(Вам нужно только вернуть конечный результат. Путь, по которому вы его достигнете, может отличаться от показанного здесь: не имеет значения, в каком порядке вы выполняете операции свертывания, все они приводят к одному и тому же результату.)

Более подробное объяснение и некоторую мотивацию см. В этом видео Numberphile или в статье в Википедии об абелевой модели песочных куч .

Правила:

• Вы можете взять ввод и вывод любым из стандартных способов
• Лазейки запрещены
• Вход и выход могут быть:
  • вложенный список: [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
  • простой список: [1, 2, 3, 4, 5, 6, 7, 8, 9]и форма
  • какой-то родной тип матрицы
  • строка, например 1 2 3\n4 5 6\n7 8 9
  • или что еще работает на вашем языке.
• Вход и выход должны быть в одинаковой форме
• Входные данные могут содержать большие числа, чем показанные здесь, но размер может быть ограничен пределами вашего языка (эквиваленты MAXINT, если применимо)
• Матрица может иметь любую форму (например, 1x1, 2x2, 3x3, 4x4, 2x7, 11x3, ...)
• Вам не нужно обрабатывать случай, когда форма 0xN или Nx0.

Testcases

[[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]]

Это Codegolf , самый короткий код (на язык) выигрывает.

MATL , 17 байт

tss:"t3>t1Y6Z+w4*-+

Попробуйте это в MATL Online! Или проверьте все тестовые случаи .

объяснение

Программа повторяется столько раз, сколько сумма ввода. Это свободная верхняя граница необходимого количества итераций.

Для каждой итерации 3обнаруживаются записи в превышении матрицы песочницы , дающей матрицу 1и 0, которая свернута с маской с 4 соседями. Записи, превышающие 3в матрице песочницы, уменьшаются на 4, и результат свертки добавляется.

Для последних итераций, в которых матрица песочницы не имеет превышающих чисел чисел 3, из нее вычитаются нули и добавляются к ней, поэтому это не затрагивается.

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 байт

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

объяснение

#//.s_:>...&

Повторно преобразуйте входные данные, свергнув все кучи, превышающие 3. Этот процесс останавливается автоматически, когда преобразование не может изменить матрицу (т. Е. Когда больше нет больших кучи). В следующем выражении матрица называется s.

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

Создайте матрицу, которая имеет 1всякий раз, когда текущая матрица имеет 4или больше, и ноль в противном случае. По сути, это маска, которая указывает, какие сваи нужно свергнуть. Назови маску x.

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

Сначала мы вычисляем количество песка, которое добавляется в каждую кучу из-за свалившихся соседних куч. Это делается с помощью свертки следующей матрицы над x:

0 1 0
1 0 1
0 1 0

По сути, он добавляет один к текущей ячейке для каждого из своих соседей фон Неймана в маске.

s+...-4x

Мы добавляем предыдущий результат sи затем четыре раза вычитаем из него маску, чтобы уменьшить количество свернутых свай.

Октава, 65 байт

Это не очень хорошо, я, должно быть, упускаю некоторые уловки ...

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 байт

Принимает ширину матрицы wи массив значений aв синтаксисе карри (w)(a). Возвращает массив значений.

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)

Отформатировано и прокомментировано

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

Контрольные примеры

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 байта

Сохранено 2 байта благодаря @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 байтов

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

Принимает ввод как ссылку на вектор векторов и изменяет его напрямую.

Попробуйте онлайн!