Die letzte Stufe der Kontamination

10

In einem Empfänger von 5x5 befindet sich ein Virus. Da wir wissen, wie es seine Kontamination verbreitet, besteht Ihre Mission darin, die letzte Stufe der Kontamination auszugeben.

Der Empfänger

Es wird als zweidimensionales Array von 5x5 dargestellt:

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

Wo 1bedeutet eine Position, an der das Virus bereits kontaminiert ist, und 0eine Position, die nicht kontaminiert ist.

Wie sich das Virus ausbreitet

  1. Eine kontaminierte Position kann nicht sauber sein.
  2. Eine saubere Position wird in der nächsten Stufe nur dann kontaminiert, wenn mindestens zwei ihrer benachbarten Positionen (Nord-, Ost-, Süd- und Westzellen) kontaminiert sind.
  3. Die letzte Stufe der Kontamination tritt ein, wenn keine sauberen Zellen mehr kontaminiert werden können.

Stichprobe

Unter Verwendung des oben beschriebenen Empfängers als Stufe 1 der Kontamination wird die Stufe 2 sein:

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

Die Stufe 3 der Kontamination wird sein:

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

Die Stufe 4 der Kontamination wird sein:

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

Und die Stufe 5 (in diesem Beispiel die letzte) wird sein:

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

Herausforderung

Wenn Sie eine Stufe der Kontamination als Eingabe angeben, sollten Sie die letzte Stufe der Kontamination ausgeben.

Sie dürfen ein vollständiges Programm oder eine Funktion schreiben. Sie können die Eingabe als Array / Liste, als getrennte Zahlen oder sogar als Zeichenfolge verwenden. Wählt den besten Weg, der zu Ihrer Sprache passt.

Die kürzeste Antwort in Bytes gewinnt!

Ein weiterer Testfall

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
code-golf binary-matrix entfernt
quelle
1
Wie kann 1 0 1es in der Ausgabe vorkommen? Liegt die mittlere Null nicht neben zwei 1s?
Lynn
@Lynn .. Ich habe aktualisiert;) ... Entschuldigung
entfernt
1
Könnten Sie 1 0 0 1 0 \ 0 0 1 0 1 \ 0 0 0 0 0 \ 1 0 0 0 0 \ 0 0 1 0 0als Testfall hinzufügen ?
Conor O'Brien
@ CᴏɴᴏʀO'Bʀɪᴇɴ. Dank hinzugefügt
entfernt
2
In allen Testfällen sind bisher nur vollständige Zeilen und Spalten leer. Ich würde vorschlagen 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, was unverändert bleibt.
xnor

Antworten:

12

Da es sich im Grunde genommen um einen zellularen Automaten handelt, gebe ich Ihnen ..

Golly Quicklife-Regel, 10 Bytes

01234/234V

Geben Sie die Regel ein, fügen Sie das Raster in Golly ein und führen Sie das Muster aus. Das resultierende Muster ist die Ausgabe.

Erläuterung:

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

Oder wenn Sie auf einer vollständigen RuleLoader-Regel bestehen, 89 Byte:

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

Der Regelname ist X, die gleichen Schritte wie zuvor.

CalculatorFeline
quelle
3
Ist das eine Programmiersprache ?
Lynn
1
Golly Quicklife kann simulieren, B3/S23was alles kann! ... aber es hat ein striktes Eingabeformat (wie das gesamte Programm in der Eingabe enthalten ist (wie würden Sie es sonst tun?)). ABER WARUM DEN SPASS RUINIEREN?
CalculatorFeline
Nun, wir müssen nur auf eine Frage warten, die auf das langfristige Verhalten eines zellularen Automaten hinausläuft!
CalculatorFeline
1
Ich habe einige Zweifel an der Gültigkeit. Wenn Golly nur das Endergebnis anzeigen würde, wäre es in Ordnung, aber es zeigt auch Zwischenergebnisse an (es sei denn, ich
liege
1
@CatsAreFluffy Dann hast du meine Gegenstimme.
Lirtosiast
5

Python 2, 97 Bytes

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

Probieren Sie es online aus . Die Eingabe wird als Zeichenfolge in Anführungszeichen gesetzt, wobei jede Zeile durch Zeilenumbrüche begrenzt wird. Das 980ist nicht optimal und kann durch ein unteres Vielfaches von 35 ersetzt werden. Da es keinen Einfluss auf die Länge dieses Programms hat, habe ich die Bestimmung der niedrigsten sicheren Obergrenze als Übung für den Leser belassen.

xsot
quelle
Erfordert Anführungszeichen um die Eingabe und \ n maskierte Zeilenumbrüche.
CalculatorFeline
@CatsAreFluffy Ich glaube, der Ideone-Link verdeutlicht bereits, wie die Eingabe erfolgt.
Xsot
Die Eingabe wird als Zeichenfolge in Anführungszeichen gesetzt, wobei jede Zeile durch \ ns begrenzt ist.
CalculatorFeline
Okay, ich werde es bearbeiten, um es weniger mehrdeutig zu machen.
Xsot
3

Javascript (ES6), 91 89 87 Bytes

Als Funktion, die Eingaben als Array von Zahlen oder Zeichenfolgen akzeptiert.

-2 Bytes von Neil (Kombination von Zuweisung ymit String-Konvertierung)

-2 Bytes (Variable entfernen 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>
Erweitern Sie das Snippet

nderscore
quelle
Speicher 2 Bytes durch das Schreiben (y=...)+''==xstatt (y=...),y+''==x.
Neil
2

MATL , 22 Bytes

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

Dies funktioniert in der aktuellen Version (15.0.0) der Sprache.

Probieren Sie es online aus !

Das Eingabeformat ist: 2D-Array mit durch Semikolons getrennten Zeilen. Die vier Testfälle haben also folgende Eingaben:

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

Erläuterung

Dies führt wiederholt eine 2D-Faltung des Eingabearrays mit der folgenden Maske durch, die definiert, welche Nachbarn als kontaminierend gelten:

0 1 0
1 0 1
0 1 0

Um ein Ergebnis zu erhalten, das dieselbe Größe wie das ursprüngliche Array hat, wird es zuerst mit einem Rahmen aus Nullen aufgefüllt, und dann wird nur der "gültige" Teil der Faltung beibehalten (dh der ohne Kanteneffekte).

Ein Schwellenwert von 2 wird auf die Ausgabe der Faltung angewendet, und das Ergebnis wird mit der ursprünglichen Eingabe elementweise ODER-verknüpft.

Dies muss ausreichend oft durchgeführt werden, um sicherzustellen, dass der Endzustand erreicht wurde. Ein einfaches Kriterium, das dies erfüllt, lautet: Iterieren Sie so oft wie die Anzahl der Einträge im Eingabearray (dh 25 Mal in den Testfällen).

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
Luis Mendo
quelle
1

TI-BASIC, 151 Bytes

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]

Eingabe als [[1,0,0,1,1][1,0,0,0,0]...].

Conor O'Brien
quelle
1
Ich denke, Sie können dies auf etwa 100 Bytes bringen. Erster Tipp: Verwenden Sie eine RepeatSchleife.
Lirtosiast
1

Lua, 236 Bytes

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)

Akzeptiert Eingaben in der Befehlszeile und verwendet Luas String-Manipulation, um die Antwort zu erhalten.

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
quelle
1

APL, 76 72 70 Bytes

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

Dies bedeutet: Erweitern Sie die Matrix auf eine 7x7-Matrix und zentrieren Sie dann unser Argument (Omega). Generieren Sie aus dieser Matrix 4 "untergeordnete" Matrizen, die jeweils in eine andere Richtung verschoben sind (nach oben / unten / links / rechts), addieren Sie sie (damit wir die Anzahl der Nachbarn erhalten) und lassen Sie den Frame fallen (um zu a zurückzukehren) 5x5 Matrix). Oder diese neue Matrix mit der "alten", um sicherzustellen, dass wir dabei keine Zellen fallen lassen (dh am Rand). Verwenden Sie dann die ⍣≡Kombination, um zu einem Festpunktwert zu gelangen.

{⍵∨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

Beispiel (unter Berücksichtigung der Funktion, der zugewiesen wurde 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
Ven
quelle