Последняя стадия загрязнения

10

Внутри получателя 5х5 есть вирус. Поскольку мы знаем, как он распространяет свое загрязнение, ваша миссия состоит в том, чтобы вывести последний этап заражения.

Получатель

Он будет представлен в виде двумерного массива 5x5:

0 0 0 0 1
0 0 0 0 1
0 0 0 1 1
0 0 1 1 1
0 1 1 1 1

Где 1означает позицию, где вирус уже загрязнен, и 0позицию, которая не загрязнена.

Как распространяется вирус

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

Образец

Используя в качестве этапа 1 заражения получателя, описанного выше, этап 2 будет:

0 0 0 0 1
0 0 0 1 1
0 0 1 1 1
0 1 1 1 1
0 1 1 1 1

Этап 3 загрязнения будет:

0 0 0 1 1
0 0 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1

Этап 4 загрязнения будет:

0 0 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1

И этап 5 (в этом примере, последний) будет:

0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1

Вызов

Учитывая в качестве входных данных одну стадию загрязнения, вы должны вывести последнюю стадию загрязнения.

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

Самый короткий ответ в байтах побеждает!

Еще один тест

Input:
1 1 0 0 1
0 0 0 0 0
0 1 0 0 1
0 0 0 0 0
1 0 0 0 1

Output:
1 1 0 0 1
1 1 0 0 1
1 1 0 0 1
1 1 0 0 1
1 1 0 0 1

Input:
1 0 0 0 0
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1

Output:
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Input:
1 0 0 1 0
0 0 1 0 1
0 0 0 0 0
1 0 0 0 0
0 0 1 0 0

Output:
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Input:
0 1 0 0 0
0 0 0 0 1
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0

Output:
0 1 0 0 0
0 0 0 0 1
0 0 1 0 0
1 0 0 0 0
0 0 0 1 0
удален
источник
1
Как может 1 0 1появиться на выходе? Разве центральный ноль не соседствует с двумя 1s?
Линн
@ Линн .. Я обновил;) ... извините за это
удалено
1
Не могли бы вы добавить 1 0 0 1 0 \ 0 0 1 0 1 \ 0 0 0 0 0 \ 1 0 0 0 0 \ 0 0 1 0 0в качестве теста?
Конор О'Брайен
@ CᴏɴᴏʀO'Bʀɪᴇɴ. Добавлено спасибо
удалено
2
Все тестовые случаи до сих пор содержат только полные строки и столбцы, заканчивающиеся пустыми. Я бы предложил 0 1 0 0 0 \ 0 0 0 0 1 \ 0 0 1 0 0 \ 1 0 0 0 0 \ 0 0 0 1 0, который остается неизменным.
xnor

Ответы:

12

Так как это в основном говорит о клеточном автомате, я даю вам ..

Правило Golly Quicklife, 10 байтов

01234/234V

Введите правило, вставьте сетку в Golly, запустите шаблон. Результирующий шаблон является выходным.

Объяснение:

01234 Survive on any number of neighbors
     /234 Born on >2 neighbors
         V Only directly adjacent neighbors count

Или, если вы настаиваете на полном правиле RuleLoader, 89 байт:

@RULE X
@TABLE
n_states:2
neighborhood:vonNeumann
symmetries:permute
011001
011101
011111

Rulename - X, те же шаги, что и раньше.

CalculatorFeline
источник
1
Golly Quicklife может симулировать B3/S23что угодно! ... Но он имеет строгий формат ввода (как будто вся программа включена во вход (как еще вы это сделаете?)). НО ПОЧЕМУ РАЗБИРАТЬ УДОВОЛЬСТВИЕ ??
CalculatorFeline
Что ж, нам просто нужно дождаться вопроса, который сводится к долгосрочному поведению клеточного автомата!
CalculatorFeline
1
У меня есть некоторые сомнения по поводу действительности. Если бы Golly отображал только конечный результат, это было бы хорошо, но он также отображал промежуточные результаты (если я не ошибаюсь)
lirtosiast
1
@CatsAreFluffy У тебя есть мой голос.
lirtosiast
5

Python 2, 97 байт

s=' '*6+input()
exec"s=s[1:]+('1'+s)[sum(s[i]<'1'for i in[-6,-1,1,6])>2or'/'>s];"*980
print s[6:]

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

xsot
источник
Требуются кавычки вокруг ввода и \ n экранированные символы новой строки.
CalculatorFeline
@CatsAreFluffy Я полагаю, что ссылка Ideone уже разъясняет, как вводится.
xsot
Ввод принимается как строка в кавычках, каждая строка ограничена \ n s.
CalculatorFeline
Хорошо, я отредактирую это, чтобы сделать это менее двусмысленным.
xsot
3

Javascript (ES6), 91 89 87 байт

В качестве функции, которая принимает входные данные в виде массива чисел или строк.

-2 байта от Нейла (комбинируя назначение y с преобразованием строки)

-2 байта (удаление переменной j)

f=x=>(y=x.map((z,i)=>~(i%5&&x[i-1])+~(i%5<4&x[i+1])+~x[i-5]+~x[i+5]<-5|z))+[]==x?y:f(y)
<!-- Snippet demo with array <-> string conversion for convenience -->
<textarea id="input" cols="10" rows="5">0 0 0 0 1
0 0 0 0 1
0 0 0 1 1
0 0 1 1 1
0 1 1 1 1</textarea>
<button id="submit">Run</button>
<pre id="output"></pre>
<script>
strToArray=x=>x.match(/\d/g)
arrayToStr=x=>([]+x).replace(/(.),(.),(.),(.),(.),*/g, '$1 $2 $3 $4 $5\n')
submit.onclick=_=>output.innerHTML=arrayToStr(f(strToArray(input.value)))
</script>

nderscore
источник
Сохраните 2 байта, написав (y=...)+''==xвместо (y=...),y+''==x.
Нил
2

MATL , 22 байта

tn:"t5Bt!=~2X53$Y+1>Y|

Это работает в текущей версии (15.0.0) языка.

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

Формат ввода: 2D-массив со строками, разделенными точками с запятой. Таким образом, четыре контрольных примера имеют следующие входные данные:

[0 0 0 0 1; 0 0 0 0 1; 0 0 0 1 1; 0 0 1 1 1; 0 1 1 1 1]

[1 1 0 0 1; 0 0 0 0 0; 0 1 0 0 1; 0 0 0 0 0; 1 0 0 0 1]

[1 0 0 0 0; 0 1 0 0 0; 0 0 1 0 0; 0 0 0 1 0; 0 0 0 0 1]

[1 0 0 1 0; 0 0 1 0 1; 0 0 0 0 0; 1 0 0 0 0; 0 0 1 0 0]

объяснение

Это повторно выполняет двумерную свертку входного массива со следующей маской, которая определяет, какие соседи считаются загрязняющими:

0 1 0
1 0 1
0 1 0

Чтобы получить результат того же размера, что и исходный массив, он сначала дополняется кадром нулей, а затем сохраняется только «действительная» часть свертки (то есть без краевых эффектов).

Порог 2 применяется к выходу свертки, и результат поэлементно ИЛИ с исходным вводом.

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

t          % get input 2D array implicitly. Duplicate
n:"        % repeat as many times as elements in the input array
  t        %   duplicate array
  5B       %   number 5 in binary: row vector [1 0 1] 
  t!       %   duplicate and transpose into column
  =~       %   compare for inequality with broadcast. Gives desired mask
  2X53$Y+  %   2D convolution. Output has same size as input 
  1>       %   true for elements equal or greater than 2
  Y|       %   element-wise OR with previous copy of the array
           % end loop. Implicitly display
Луис Мендо
источник
1

TI-BASIC, 151 байт

Prompt [A]
[A]→[B]
Lbl 0
[B]→[A]
For(Y,1,5
For(X,1,5
DelVar ADelVar BDelVar CDelVar D
If Y>1:[A](Y-1,X→A
If Y<5:[A](Y+1,X→B
If X>1:[A](Y,X-1→C
If X<5:[A](Y,X+1→D
max(A+B+C+D≥2,[A](Y,X→[B](Y,X
End
End
If [A]≠[B]:Goto 0
[B]

Введите как [[1,0,0,1,1][1,0,0,0,0]...].

Конор О'Брайен
источник
1
Я думаю, что вы можете получить это до 100 байтов. Первый совет: используйте Repeatпетлю.
lirtosiast
1

Луа, 236 байт

s=arg[1]u=s.sub while p~=s do p=s s=s:gsub("(%d)()",function(d,p)t=0 t=t+((p-2)%6>0 and u(s,p-2,p-2)or 0)t=t+(p-7>0 and u(s,p-7,p-7)or 0)t=t+(p+5<30 and u(s,p+5,p+5)or 0)t=t+(p%6>0 and u(s,p,p)or 0)return t>1 and 1 or d end)end print(s)

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

Ungolfed:

s=arg[1]
u=s.sub
while p~=s do
    p=s
    s=s:gsub("(%d)()", function(d, p)
                 t=0
                 t=t+((p-2)%6>0 and u(s,p-2,p-2)or 0)
                 t=t+(p-7>0 and u(s,p-7,p-7)or 0)
                 t=t+(p+5<30 and u(s,p+5,p+5)or 0)
                 t=t+(p%6>0 and u(s,p,p)or 0)
                 return t>1 and 1 or d
    end)
end
print(s)
Trebuchette
источник
1

APL, 76 72 70 байт

{⍵∨1<¯1 ¯1↓1 1↓↑+/(1 0)(¯1 0)(0 ¯1)(0 1){⍺[1]⊖⍺[2]⌽⍵}¨⊂¯1⊖¯1⌽7 7↑⍵}⍣≡

То, что это делает: расширяет матрицу до 7x7, затем центрирует наш аргумент (омега). Из этой матрицы сгенерируйте 4 «дочерние» матрицы, каждая из которых смещена в различном направлении (вверх / вниз / влево / вправо), сложите их вместе (чтобы мы получили количество соседей), опустите кадр (чтобы вернуться к Матрица 5х5). Или эта новая матрица со «старой», чтобы убедиться, что мы не уронили ни одной ячейки в процессе (т.е. на краю). Затем используйте ⍣≡комбинацию, чтобы получить значение с фиксированной точкой.

{⍵∨1<¯1 ¯1↓1 1↓↑+/(1 0)(¯1 0)(0 ¯1)(0 1){⍺[1]⊖⍺[2]⌽⍵}¨⊂¯1⊖¯1⌽7 7↑⍵}⍣≡
                                                             7 7↑⍵    ⍝ Expand the matrix
                                                       ¯1⊖¯1⌽         ⍝ Center the original matrix
                  (1 0)(¯1 0)(0 ¯1)(0 1){⍺[1]⊖⍺[2]⌽⍵}¨⊂               ⍝ Construct 4 child matrices, each offset from the original one by the values on the left of {}
                +/                                                    ⍝ Sum each matrix into one giant matrix
               ↑                                                      ⍝ Mix
     ¯1 ¯1↓1 1↓                                                       ⍝ Transform the 7x7 matrix back to a 5x5 matrix
   1<                                                                 ⍝ Check which elements are smaller than 1
 ⍵∨                                                                   ⍝ "Or" this matrix and the generated matrix
{                                                                 }⍣≡ ⍝ Find the fixpoint

пример (учитывая, что функция была назначена contaminate):

          stage ⍝ the base matrix
0 0 0 0 1
0 0 0 0 1
0 0 0 1 1
0 0 1 1 1
0 1 1 1 1
      contaminate stage ⍝ apply the function
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
0 1 1 1 1
Вен
источник