Codegolf — Найди Идентичную Песочницу

Этот вопрос о абелевы песочницы. Читать это предыдущее испытание и посмотри это нумерофильское видео чтобы узнать больше.

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

Например, я добавляю две песочницы размером 3 на 3 (что приводит к довольно экстремальной цепной реакции):

 
 0, 1, 2, 3 
 

В этой задаче нас интересует подмножество всех возможных н к н песчаные кучи. Это подмножество содержит любую песочницу, которую вы можете получить, добавив произвольную песочницу к «всем тройкам». н к н песочница. Например, чуть выше мы видели, что 2 2 2 2 1 2 4 3 4 0 5 0 2 1 2 2 2 2 2 2 2 + 1 0 1 = 3 2 3 -> 5 2 5 -> 1 6 1 -> 2 2 2 2 2 2 2 1 2 4 3 4 0 5 0 2 1 2 2 2 2 is in the subset, because we got it by adding something to the all-3 sandpile.

Теперь в этом подмножестве есть интересный элемент: личность элемент. Если вы возьмете этот элемент и добавите его в любой другой элемент в подмножество, сумма не изменится. Другими словами, эта куча песка действует как ноль этого подмножества. Так уж получилось, что 212 | 101 | 212 is the zero element for the subset of 3 by 3. For example:

Теперь это ваша задача: данный н, найдите единичный элемент подмножества н к н сетка. Выведите его, назначив каждому из цветов уникальный цвет с достаточным контрастом по вашему выбору. 3 3 3 1 2 1 4 5 4 4 6 4 6 2 6 6 3 6 2 5 2 4 1 4 4 2 4 0 4 0 2 0 2 2 1 2 3 3 3 + 2 1 2 = 5 4 5 -> 6 0 6 -> 2 4 2 -> 3 0 3 -> 5 0 5 -> 1 4 1 -> 2 0 2 -> 4 0 4 -> 0 4 0 -> 1 0 1 3 3 3 1 2 1 4 5 4 4 6 4 6 2 6 6 3 6 2 5 2 4 1 4 4 2 4 0 4 0 2 0 2 2 1 2 and outputting an n by n image. Ваш код должен быть в состоянии создать корпус 50 на 50 менее чем за минуту на разумном современном ПК.

Например, элемент идентификации 500 на 500:

Вот синий = 3, зеленый = 2, красный = 1, белый = 0. Но вам не обязательно использовать эту цветовую схему в своем ответе.

#код-гольф #графический вывод #клеточные автоматы

Математика, 177 157 135 133 байт

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 import numpy as np
from PIL import Image

# Compute the identity element

n = int(input('Size of the sandpile: '))

def reduce_pile(sandpile):

while any(element >= 4 for element in np.nditer(sandpile)):

for x, y in np.ndindex((n, n)):

if sandpile[x, y] >= 4:

sandpile[x, y] -= 4

if x > 0: sandpile[x - 1, y] += 1

if y > 0: sandpile[x, y - 1] += 1

if x < n - 1: sandpile[x + 1, y] += 1

if y < n - 1: sandpile[x, y + 1] += 1

s = np.full((n, n), 6, dtype=np.int32)
s_prime = np.copy(s)

reduce_pile(s_prime)

identity = s - s_prime
reduce_pile(identity)

# Output it to identity.png as an image

colours = [[255, 255, 255], [255, 0, 0], [0, 255, 0], [0, 0, 255]]
img_array = np.vectorize(lambda x: colours[x], otypes=[object])(identity)
img_array = np.array(img_array.tolist(), dtype=np.uint8)

img = Image.fromarray(img_array)
img.save('identity.png')
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Принимает номер from numpy import* . The output is the identity sandpile. 0 is black, 1 is light gray, 2 is magenta, and 3 is blue-gray.

К сожалению, в Mathematica нет встроенной функции для этого...

Использует алгоритм, изложенный в статье Скотта Корри и Дэвида Перкинсона.

На моем пятилетнем ноутбуке требуется 91,7 секунды, чтобы вычислить песочницу для идентификации 50x50. Я уверен, что современный настольный компьютер более чем на 50% быстрее. (У меня также есть более быстрый код в конце).

Объяснение

Определить функцию R (the input is a sandpile matrix): a function that ...

... повторяет I operation until the output does not change. I = R(S - R(S)) операция: ...

... дополнить входной массив одним слоем из 0...

... разбейте его на матрицы 3х3 со смещением 1...

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

то есть вывод 0 1 0 1 0 1 0 1 0 is the stabilized version of the input.

Определять f(M-f(M)) as an н к н массив из 6 с.

Вычислите f(k - f(k)).

Примените цвета к результату.

Более быстрая версия (142 байта)

Тот же код, но вместо него используется встроенная ротация списка. f(ones(n)*6 - f(ones(n)*6) . Computes n=50 in 4.0 seconds on my laptop.

Октава, 120 113 байт

Благодаря ЮнгХван Мин за предоставление ссылки на справочный документ в его ответе Mathematica.
Благодаря Стьюи Гриффин сэкономил мне 7 байт 0.0844409 seconds

Здесь используются две функции:

1. n : for stabilization of a matrix
2. Анонимная функция, принимающая f as input and shows the identity matrix.

Попробуйте на ректестере! для генерации матрицы 50*50

Затраченное время на вычисление матрицы: [any(any(x)) -> nnz(x)] .

Объяснение:

Рассмотрим функцию function a=W(a);while nnz(b=a>3);a+=conv2(b,[t=[0 1 0];!t;t],'same')-b*4;end;end;@(n)imagesc(W((x=ones(n)*6)-W(x))) that stabilizes a matrix the task of finding the identity is simply

BlockMap .

что Colorize[r=RotateLeft;a=ArrayPad;f=a[b=#~a~1;b+r[g=⌊b/4⌋,s={0,1}]+g~r~-s+r[g,1-s]+r[g,s-1]-4g,-1]&~FixedPoint~#&;k=Table[6,#,#];f[k-f@k]]& means a n*n matrix of 6.

так что для Colorize[ ... ] :

Результат будет k

Для стабилизации используется функция 2D-свертки для ускорения задачи; k=Table[6,#,#] with the same size of the input matrix and set it to 1 if corresponding element of the input matrix is >3. Then we apply a 2D convolution of the binary matrix with the following mask

На каждой итерации мы создаем двоичную матрицу
представляющие четырех прямых соседей.

Результат свертки добавляется к матрице и из него вычитается 4-кратная двоичная матрица.

Цикл продолжался до тех пор, пока все элементы матрицы не стали <= 3.:

Версия без гольфа

Python 3 + Numpy + PIL, 385 370 364 байта #~ArrayPad~1 . Black corresponds to 0, dark grey to 1, light grey to 2, and white to 0.

Принимает входные данные на STDIN. Выводит изображение в оттенках серого BlockMap , where BlockMap Использует формулу BlockMap[ ... ]~FixedPoint~#& is the matrix filled with sixes, and f является элементом идентификации,

– функция редукции. f= ... , but (1) I don't have Numpy installed on Python 2 and (2) the program wasn't terminating with n .

Вероятно, я мог бы сэкономить несколько байтов, переключившись на Python 2 и выполнив