Da morgen der 4. Mai ist, gibt es hier einen kleinen Star Wars-Themenbeitrag, der Sie mental auf all die schlechten Witze vorbereitet, die morgen kommen.

HINTERGRUNDGESCHICHTE

Während einer Sitzung des galaktischen Senats sitzen alle Senatoren in einem n*nRaster. Ein plötzlicher Ausbruch der JarJar-Grippe (der ewig anhält und die Infizierten wie JarJar Binks ansprechen lässt) führt dazu, dass sich einige Senatoren anstecken.

Hier ist ein Beispiel mit einem 6*6Raster, in dem Xsich die infizierten Senatoren befinden. Die entsprechende Liste lautet [[0,5],[1,4],[2,3],[2,1],[3,3],[3,0],[4,5],[0,5]]:

Danach beginnt sich die Infektion schrittweise auszubreiten. Zwei Senatoren grenzen aneinander, wenn sie eine ganze Kante im Raster haben (dh oben, unten, rechts, links), was bedeutet, dass wir Diagonalen ausschließen.

Wir können daraus schließen, dass ein Senator an 2,3 oder 4 andere Senatoren angrenzt und die folgenden Regeln für die Infektion beansprucht:

• Ein infizierter Senator bleibt für immer infiziert
• Ein Senator wird in einem Schritt infiziert, wenn er im vorherigen Schritt neben zwei oder mehr infizierten Senatoren war

Hier ist ein Beispiel mit dem vorherigen Raster, das die 2 ersten Schritte der Infektion zeigt:

Nach den nächsten Schritten wird der gesamte Senat infiziert

DEINE AUFGABE

Ihr Code muss keine ungültigen Eingaben wie eine Liste größer als n*noder Koordinaten verarbeiten, die keine Unterscheidungsmerkmale sind.

Ihr Code verwendet als Eingabe eine Liste von Paaren von Ganzzahlen (oder ein Binärgitter oder ein anderes Format, das zu Ihrer Sprache passt) und eine Ganzzahl n(was unnötig sein kann, wenn Sie ein anderes Format als eine Liste verwenden), zum Beispiel:

8 [[1,2],[1,1],[7,4],[2,7],[4,3]]

n ist die Seite des Gitters, was bedeutet, dass das Gitter ein * n-Gitter ist, und die Liste der Ganzzahlpaare sind die Koordinaten der Zellen der ursprünglich infizierten Senatoren.

Die untere linke Ecke des Gitters ist [0,0] und die obere rechte Ecke ist [n-1, n-1]. Oben links ist [0, n-1].

Ihr Code muss eine Ganzzahl ausgeben:

-1 oder ein falscher Wert oder ein Fehler, wenn das gesamte Raster niemals vollständig infiziert wird, oder die Mindestanzahl von Schritten, die erforderlich sind, um das gesamte Raster zu infizieren

Testfälle

6 [[0,5],[1,4],[2,3],[2,1],[3,3],[3,0],[4,5],[5,0]] => 7

4 [[1,1][0,3][1,0][3,0][3,3]] => 9

Denken Sie daran, dass dies Code-Golf ist und somit die kürzeste Antwort in Bytes gewinnt!

MATL, 29 28 Bytes

tn:"tlY6Z+1>Z|t?@.]]Nl=?l_]&

Die Eingabe erfolgt in Form einer 2D-Matrix aus Einsen und Nullen

Probieren Sie es bei MATL Online aus

Erläuterung

        % Implicitly grab user input as a 2D matrix
t       % Duplicate the inputs
n:      % Count the number of elements in the input (N) and create the array [1...N]
"       % Loop this many times (maximum number of steps we analyze)
  t     % Duplicate the top element
  lY6   % Push the 2D array => [0 1 0; 1 0 1; 0 1 0]
  Z+    % Perform 2D convolution (and maintain the size)
  l>    % Find all values that are >= 2
  Z|    % Perform an element-wise OR with the previous state
  t?    % If all elements are 1's
    @.  % Push the current index and break out of the loop
  ]     % End of if 
]       % End of for loop
Nl=?    % If there is only one element on the stack
  l_    % Push a negative one
]       % End of if statement
&       % Display the top stack element

APL (Dyalog 16.0), 54 Zeichen oder 60 Bytes

Nimmt die beigefügte Matrix als Argument, gibt die Schrittnummer zurück, die die Infektion abgeschlossen hat, dh 1 = ist bereits vollständig infiziert. 0 = ist nicht vollständig verteilt, was nur 1 + den OP-Nummern entspricht.

54 Zeichen (Unicode):

(≢×0=0∊⊃){(⊢≡f←⊢∨2≤{+/,⍵×3 3⍴0 1}⌺3 3)⊃⍵:⍵⋄(⊂f⊃⍵),⍵}⍣≡

60 Bytes (klassisch):

(≢×0=0∊⊃){(⊢≡f←⊢∨2≤{+/,⍵×3 3⍴0 1}⎕U233A 3 3)⊃⍵:⍵⋄(⊂f⊃⍵),⍵}⍣≡

⌺ ist äquivalent zu ⎕U233A

Beispiellauf:

      g←(≢×0=0∊⊃){(⊢≡f←⊢∨2≤{+/,⍵×3 3⍴0 1}⌺3 3)⊃⍵:⍵ ⋄ (⊂f⊃⍵),⍵}⍣≡
      ⎕IO←0
      b←⊂⊖⍉~@(⎕JSON'[[0,5],[1,4],[2,3],[2,1],[3,3],[3,0],[4,5],[5,0]]')⊢0⍴⍨2⍴6
      g b
8
      b←⊂⊖⍉~@(⎕JSON'[[1,1],[0,3],[1,0],[3,0],[3,3]]')⊢0⍴⍨2⍴4
      g b
10

Die Schritte sind wie folgt:

┌─────────────┬─────────────┬─────────────┬─────── ──────┬─────────────┬─────────────┬─────────────┬─ ────────────┐
│ XX │ XXX │ XXXX │ XXXXX │ XXXXX │ XXXXX │ XXXXX │ XXXXXX │
│ X │ XXX │ XXXX │ XXXXX │ XXXXX │ XXXXX │ XXXXXX │ XXXXXX │
│ XX │ XXX │ XXXX │ XXXX │ XXXXX │ XXXXXX │ XXXXXX │ XXXXXX │
│ │ X │ XXX │ XXXXX │ XXXXXX │ XXXXXX │ XXXXXX │ XXXXXX │
│ X │ XX │ XXX │ XXXXX │ XXXXXX │ XXXXXX │ XXXXXX │ XXXXXX │
│ XX │ XXXX │ XXXX │ XXXX │ XXXXX │ XXXXXX │ XXXXXX │ XXXXXX │
└─────────────┴─────────────┴─────────────┴─────── ──────┴─────────────┴─────────────┴─────────────┴─ ────────────┘
┌─────────┬─────────┬─────────┬─────────┬───────── ┬─────────┬─────────┬─────────┬─────────┬───────── ┐
│ XX │ XX │ XX │ XX │ XX │ XX │ XXX │ XXXX │ XXXX │ XXXX │
│ │ │ │ X │ XX │ XXX │ XXXX │ XXXX │ XXXX │
│ X │ X │ XX │ XXX │ XXX │ XXX │ XXX │ XXX │ XXXX │ XXXX │
│ XX │ XXX │ XXX │ XXX │ XXX │ XXX │ XXX │ XXX │ XXX │ XXXX │
└─────────┴─────────┴─────────┴─────────┴───────── ┴─────────┴─────────┴─────────┴─────────┴───────── ┘

Pyth , 49 Bytes

J^UE2*lK.uS{+NeMf>hT1r8S@Jsmm+VdkNs_MB_MBU2Q)qJeK

Testsuite .

Verwendet 1-Indizierung für die Ausgabe.

Python, 231 Bytes

g=input()
q=lambda r,c:g[r][c]if(0<=r<m)*(0<=c<m)else 0
m=len(g);p=t=0;n=range(m)
while not all([r for k in g for r in k]):h=[[g[r][c]or sum([q(r+1,c),q(r-1,c),q(r,c+1),q(r,c-1)])>1 for c in n] for r in n];t+=1;0/(g!=h);g=h
print t

Es wird ein Fehler ausgegeben, wenn dies nicht möglich ist.

Probieren Sie es online!

JavaScript (ES6), 132 Byte

f=s=>(w=s.search`\n`,t=` `.repeat(w+1),t+=s+t,t=s.replace(/0/g,(_,i)=>1-t[i]-t[i+=w]-t[i+=2]-t[i+w]>>>31),t==s?0/!/0/.test(s):1+f(t))

Wobei \ndas wörtliche Zeilenumbruchzeichen darstellt. Übernimmt die Eingabe als Zeichenfolge von 0s und 1s in einem durch Zeilenumbrüche getrennten Array. Gibt zurück, NaNwenn das Grid niemals vollständig infiziert wird.