Puisque demain est le 4 mai, voici un petit post sur le thème de Star Wars pour vous préparer mentalement à toutes les mauvaises blagues à venir demain.

PASSÉ

Au cours d'une session du Sénat galactique, tous les sénateurs sont assis sur une n*ngrille. Une soudaine éclosion de grippe JarJar (qui dure éternellement et fait parler les personnes infectées comme JarJar Binks) provoque l'infection de certains sénateurs.

Voici un exemple avec une 6*6grille où se Xtrouvent les sénateurs infectés, la liste correspondante est [[0,5],[1,4],[2,3],[2,1],[3,3],[3,0],[4,5],[0,5]]:

Après cela, l'infection commence à se propager étape par étape. Deux sénateurs sont adjacents s'ils partagent un bord entier sur la grille (c'est-à-dire en haut, en bas, à droite, à gauche), ce qui signifie que nous excluons les diagonales.

Nous pouvons conclure qu'un sénateur peut être adjacent à 2,3 ou 4 autres sénateurs et réclamer les règles suivantes pour l'infection:

• Un sénateur infecté reste infecté pour toujours
• Un sénateur est infecté à une étape s'il était adjacent à 2 sénateurs infectés ou plus à l'étape précédente

Voici un exemple avec la grille précédente qui montre les 2 premières étapes de l'infection:

Après les prochaines étapes, tout le Sénat sera infecté

TA TÂCHE

Votre code n'a pas besoin de gérer des entrées non valides comme une liste supérieure à n*nou des coordonnées qui ne sont pas distinctes.

Votre code prendra en entrée une liste de couples d'entiers (ou une grille binaire ou tout autre format adapté à votre langue) et un entier n(qui peut être inutile si vous utilisez un autre format qu'une liste), par exemple:

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

n étant le côté de la grille, ce qui signifie que la grille sera une grille * n, et la liste des couples d'entiers étant les coordonnées des cellules des sénateurs initialement infectés.

Le coin inférieur gauche de la grille est [0,0] et le coin supérieur droit est [n-1, n-1]. Le coin supérieur gauche est [0, n-1].

Votre code doit générer un entier:

-1 ou une valeur falsifiée ou une erreur si toute la grille ne sera jamais totalement infectée ou le nombre minimum d'étapes nécessaires pour infecter toute la grille

Cas de test

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

N'oubliez pas qu'il s'agit de code-golf , donc la réponse la plus courte en octets gagne!

MATL, 29 28 octets

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

L'entrée se présente sous la forme d'une matrice 2D de 1 et de 0

Essayez-le sur MATL Online

Explication

        % 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 caractères ou 60 octets

Prend la matrice incluse comme argument, renvoie le numéro de l'étape qui termine l'infection, c'est-à-dire que 1 = est déjà complètement infecté. 0 = ne se propage pas complètement, ce qui est juste 1 + les nombres de l'OP.

54 caractères (Unicode):

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

60 octets (classique):

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

⌺ est équivalent à ⎕U233A

Exemples d'exécution:

      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

Les étapes sont les suivantes:

┌─────────────┬─────────────┬────────────────────── ──────┬─────────────┬─────────────┬──────────────┬─ ─────────────┐
│ 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 octets

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

Suite de tests .

Utilise l'indexation 1 pour la sortie.

Python, 231 octets

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

Il déclenche une erreur si ce n'est pas possible.

Essayez-le en ligne!

JavaScript (ES6), 132 octets

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))

Où \nreprésente le caractère de nouvelle ligne littéral. Prend l'entrée comme une chaîne de 0s et 1s dans un tableau délimité par des sauts de ligne. Renvoie NaNsi la grille ne sera jamais complètement infectée.