Calcola la diffusione COVID
Poiché il coronavirus è ancora in libertà, ho pensato che sarebbe stato opportuno affrontare una sfida a tema epidemico.
Sfida
Viene fornito un array 2D di persone, dove 1rappresenta qualcuno con il virus e 0rappresenta qualcuno senza il virus. Ogni giorno, le persone con il virus infettano i loro vicini. È necessario calcolare, data una griglia di questo tipo, quanti giorni ci vorranno per infettare la popolazione (cioè ogni elemento è 1).
Regole
- L'input conta come Giorno 0 e ogni giorno successivo aumenta di 1 (puoi contare il primo giorno come Giorno 1 se lo desideri, ma indicalo nella tua risposta).
- Gli elementi di rete non devono essere
1s e0s, possono essere qualsiasi / valori falsy truthy. Ogni elemento nella griglia viene randomizzato a uno di questi valori. Si prega di specificare quali valori veritieri / falsi il vostro programma accetterà / non accetterà. - La griglia di input può essere di qualsiasi dimensione compresa tra 2x2 e 100x100. La griglia non deve essere quadrata. La dimensione della griglia è casuale (cioè non puoi scegliere).
- I quadrati diagonali non contano come adiacenti.
- Questo è il golf in codice , quindi la risposta più breve vince!
Esempi
[[1, 0, 0, 0, 1], # Input
[0, 1, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 1, 0]]
[[1, 1, 0, 1, 1], # Day 1
[1, 1, 1, 0, 1],
[0, 1, 0, 1, 0],
[0, 0, 1, 1, 1]]
[[1, 1, 1, 1, 1], # Day 2
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[0, 1, 1, 1, 1]]
[[1, 1, 1, 1, 1], # Day 3
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1]]
output = 3
[[1, 0], # Input
[0, 0],
[0, 0]]
[[1, 1], # Day 1
[1, 0],
[0, 0]]
[[1, 1], # Day 2
[1, 1],
[1, 0]]
[[1, 1], # Day 3
[1, 1],
[1, 1]]
output = 3
Risposte
Stencil ≢ , 2 byte
×v
Provalo online!
≢calcola il numero di passaggi necessari (compreso lo stato iniziale) fino al raggiungimento della stabilità. Questo argomento della riga di comando non viene conteggiato nel conteggio dei byte, secondo il consenso di Meta .
Lo stato successivo di ogni cella è determinato da:
× il segno della
v somma di tutti i valori nella sua v sul vicinato di Neumann (incluso se stesso)
Gelatina , 10 byte
ŒJạ€ŒṪ§Ṃ€Ṁ
Provalo online!
-2 byte grazie a Sisyphus
Calcola le differenze di Manhattan da tutti gli 0 a tutti gli 1 e la risposta è il massimo dei minimi (il minimo di ogni riga è il numero di fasi fino a quando non viene infettata, quindi il numero di fasi necessarie è il massimo delle fasi necessarie per ogni persona ).
Convenientemente, se tutti gli elementi sono 1, restituisce 0 poiché è il valore predefinito per minmax.
Se nessuna persona è infetta nello stato iniziale, anche questo restituisce 0.
Spiegazione
ŒJạ€ŒṪ§Ṃ€Ṁ Main Link
ŒJ Get all indices in the grid (2D indices in a matrix)
ŒṪ Get all truthy indices in the grid (finds all infected people)
ạ€ § Manhattan distance between each point to each truthy point
Ṃ€ Minimum of each (minimum number of days for each person to get infected)
Ṁ Maximum (of each point's required days to get infected)
Wolfram Language (Mathematica) , 90 78 byte
f=Length@FixedPointList[ListConvolve[CrossMatrix@1,#,{2,2},0,Times,Max]&,#]-2&
Provalo online!
-12 byte, perché ovviamente c'è un built-in CrossMatrixper costruire il kernel \$K\$.
Definisce una funzione pura fche accetta una matrice come input. Se nessuno è infetto, torna 0. Utilizza la convoluzione dell'elenco per diffondere la malattia giorno per giorno e un built-in di Mathematica per eseguire il loop fino a raggiungere un punto fisso (cioè tutti sono infetti). Spiegazione:
Per diffondere la malattia, usa un kernel
$$K=\begin{pmatrix} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 0 \end{pmatrix}$$
e elenca la convoluzione. Ad esempio, se iniziamo da
$$I_0=\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}$$
quindi applicare
ListConvolve[{{0, 1, 0}, {1, 1, 1}, {0, 1, 0}}, #, {2, 2}, 0] &
risultati in
$$\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 2 & 2 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}.$$
In realtà non abbiamo bisogno di sapere se una persona è stata infettata più volte, quindi all'interno della convoluzione dell'elenco, invece di sommare, prenderemo solo il massimo
ListConvolve[{{0, 1, 0}, {1, 1, 1}, {0, 1, 0}}, #, {2, 2}, 0, Times, Max] &
che dà
$$\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}.$$
Quindi dobbiamo solo iterarlo fino a raggiungere un punto fisso, ovvero tutti sono infetti e non possono verificarsi nuove infezioni. C'è (come al solito) un pratico built-in in Mathematica FixedPointList, che fornisce un elenco di tutte le iterazioni fino al raggiungimento di un punto fisso. Poiché questo elenco contiene due volte l'input e il punto fisso, è sufficiente sottrarre due dalla lunghezza dell'elenco per ottenere la risposta.
Come nota a margine, i parametri ListConvolveassicurano che la convoluzione funzioni bene con il kernel. Con i parametri di default, convoluzione
$$\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix}$$
con il kernel
$$\begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix}$$
dà piuttosto inutilmente
$$\begin{pmatrix} 0 & 0 \\ b & c \end{pmatrix}.$$
Per preservare almeno le dimensioni, aggiungeremo il parametro {1,1}, che ora dà
$$\begin{pmatrix} 0 & d & e & f \\ 0 & g & h & i \\ 0 & 0 & 0 & 0 \\ 0 & a & b & c \\ \end{pmatrix}.$$
Questa volta, il problema è che la convoluzione inizia nell'angolo in alto a sinistra invece che al centro del kernel, quindi cambiamo {1,1}in {2,2}, che dà
$$\begin{pmatrix} g & h & i & 0 \\ 0 & 0 & 0 & 0 \\ a & b & c & 0 \\ d & e & f & 0 \\ \end{pmatrix}.$$
Questo è quasi ciò di cui abbiamo bisogno, ma la parte inferiore del kernel trabocca verso l'alto. Per risolvere questo problema, aggiungeremo semplicemente un parametro di riempimento 0. Infine
$$\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ a & b & c & 0 \\ d & e & f & 0 \\ \end{pmatrix}.$$
Ottava , 26 byte
@(x)max(bwdist(x,'ci')(:))
Provalo online!
Per ogni cella, calcola la distanza dalla cella diversa da zero più vicina sotto \$L_1\$norma (metrica taxi). La soluzione è il valore massimo.
APL (Dyalog Extended) , 20 byte
{⌈/⌊⌿⍵∘.(1⊥∘|-)⍥⍸~⍵}
Provalo online!
Utilizza il metodo Manhattan Distance dalla risposta Jelly di HyperNeutrino.
L'input è una matrice binaria.
Spiegazione
{⌈/⌊⌿⍵∘.(1⊥∘|-)⍥⍸~⍵}
⍵ ~⍵ input and input negated
⍥⍸ coordinates of truthy values
∘. outer product using
(1⊥∘|-) Manhattan distance function (APLcart)
⌊⌿ Minimum of each column
⌈/ Maximum of the minima
C (gcc) , 270 \$\cdots\$ 214 213 byte
Risparmiato ben 31 39 40 44 56 57 byte grazie a Ceilingcat !!!
z;C;i;j;n;d;*p;f(a,r,c)int*a;{p=calloc(C=c+2,4*r+8);for(n=d=0;d<r*c;++n){for(d=0,i=r;i--;)for(j=c;j--;)a[i*c+j]?p[i*C-~j]=p[(i+2)*C-~j]=p[z=j-~i*C]=p[z+2]=1:0;for(;++i<r*c;)d+=a[i/c*c+i%c]=p[1-~(i/c)*C+i%c];}d=n;}
Provalo online!
Inserisce la griglia della popolazione come puntatore a un array di ints, che possono essere \$1\$per infetto o \$0\$in caso contrario, insieme al numero di righe e colonne. Restituisce il numero di giorni necessari per infettare la popolazione.
Come?
Crea un array di ombre pche ha un bordo di un elemento attorno, quindi non dobbiamo preoccuparci che i vicini non siano presenti quando siamo ai bordi. Inizializza tutti i suoi elementi in \$0\$. Per ogni giorno esaminiamo quindi la griglia della popolazione di input riga per riga e colonna per colonna per verificare la presenza di elementi infetti. Per tutti quelli trovati, contrassegniamo quella posizione nell'array shadow e il suo \$4\$vicini come infetti. Dopodiché, lo stesso giorno, esaminiamo nuovamente l'array di input, copiando gli elementi shadow corrispondenti e contando il numero totale di infetti per quel giorno. Restituisce il numero di giorni trascorsi prima che tutti siano stati infettati.
J , 35 byte
1-~&#<@_>./@:(|.!.0)~&(0,(,-)=i.2)]
Provalo online!
(0,(,-)=i.2):0 0,1 0,0 1,-1 0,0 -1<@_ f&dirs ]ripetereinput f dirsfino a quando il risultato non cambia e restituire tutti i passaggi intermedi.>./@:(|.!.0)~sposta la scacchiera lungo le direzioni (con0s che viene spostata ai bordi) e prendi il massimo di tutte.1-~&#contare i passaggi meno 1.
JavaScript (ES6), 97 95 byte
f=m=>/0/.test(a=[1,...m,1])&&1+f(m.map((r,y)=>r.map((v,x)=>v|r[x-1]|r[x+1]|a[y][x]|a[y+2][x])))
Provalo online!
Commentato
f = m => // m[] = matrix
/0/.test( // if there's still a zero in
a = [1, ...m, 1] // a[] which is defined as m[] with two dummy border rows
) && // then:
1 + f( // increment the final result and do a recursive call:
m.map((r, y) => // for each row r[] at position y in m[]:
r.map((v, x) => // for each value v at position x in r[]:
// the cell is set if:
v | // it's already set
r[x - 1] | // or the cell on the left is set
r[x + 1] | // or the cell on the right is set
a[y][x] | // or the cell above is set
a[y + 2][x] // or the cell below is set
// NB: both a[0][x] and a[a.length - 1][x] are
// undefined (falsy) for any x
) // end of inner map()
) // end of outer map()
) // end of recursive call
Python 3 , 131 byte
lambda a,e=enumerate:max([min([abs(x-X)+abs(y-Y)for X,I in e(a)for Y,J in e(I)if J]or[0])for x,i in e(a)for y,j in e(i)if j<1]+[0])
Provalo online!
Se nessuno è infetto nell'originale, questo restituirà 0.
-11 byte grazie a caird coinheringaahing
Provalo online!
Metodo precedente che utilizza la ricorsione:
Python 3 , 199 byte
f=lambda a,c=0:all(sum(a,[]))and c or f([[g(a,x,y+1)+g(a,x,y-1)+g(a,x+1,y)+g(a,x-1,y)+g(a,x,y)for y in range(len(a[x]))]for x in range(len(a))],c+1)
g=lambda q,x,y:len(q)>x>=0<=y<len(q[x])and q[x][y]
Provalo online!
Se non c'è nessuno infetto nell'originale, la ricorsione andrà in overflow.
Carboncino , 39 byte
Ｉ⌈Ｅθ∨⌈Ｅ⌕Ａι⁰∨⌊ΦＥθ⌊Ｅ⌕Ａν¹⁺↔⁻ξκ↔⁻πλ¬⁼νＩν⁰¦⁰
Provalo online! Il collegamento è alla versione dettagliata del codice. Utilizza di nuovo il metodo della distanza di Manhattan. Il carbone non può appiattire gli elenchi, inoltre restituisce Noneil minimo o il massimo di un elenco vuoto, il che complica un po 'il codice. Spiegazione:
Ｅθ For each row
Ｅ⌕Ａι⁰ For each `0` value in that row
Ｅθ For each row
Ｅ⌕Ａν¹ For each `1` value in that row
↔⁻ξκ↔⁻πλ Calculate the Manhattan distance
⌊ Take the minimum
Φ ¬⁼νＩν Filter out `None` values
⌊ Take the minimum
∨ ⁰ Or zero if the list was empty
⌈ Take the maximum
∨⌈ ⁰ Or zero if the list was empty
⌈ Take the maximum
Ｉ Cast to string
Implicitly print
K (oK) , 41 byte
{|/&/{+/x|-x}''u-\:/:(1=x.)#u:+!(#x),#*x}
Provalo online!
Massimo dei minimi della distanza Manhattan di ogni punto da ogni punto veritiero.
{ } \ a function with parameter x
#*x \ length of the first row
, \ appended to
(#x) \ the number of rows
! \ odometer (coordinates of the points)
+ \ transpose
u: \ assign to u
# \ filter
(1=x.) \ the coordinates of the truthy points
u-\:/: \ find the differences of the cooridinates
\ of each point to each truthy point
{+/x|-x}'' \ find the absolute value and sum
&/ \ minimum of the Manhattan distances
\ to each truthy point
|/ \ maximum
Java 8, 204 byte
m->{int r=0,f=1,l=m[0].length,i,t,I,J,n;for(;f>0;r++)for(n=f,f=0,i=m.length*l;i-->0;)for(t=4;m[I=i/l][J=i%l]==n&t-->0;)try{m[I-=t-t%3*t>>1][J-=t<2?1-2*t:0]+=m[I][J]<1?f=n+1:0;}finally{continue;}return r;}
Piccola modifica della mia risposta qui .
Emette il risultato incluso il primo passaggio.
Provalo online.
Spiegazione:
m->{ // Method with integer-matrix parameter and integer return-type
int r=0, // Result-integer, starting at 0
f=1, // Flag-integer, starting at 1
l=m[0].length, // Amount of rows
i,t,I,J,n; // Temp integers
for(;f>0; // Loop as long as the flag is NOT 0:
r++) // After every iteration: increase the result by 1
for(n=f, // Set `n` to the current flag-value
f=0, // And then reset the flag to 0
i=m.length*l;i-->0;) // Loop over the cells of the matrix:
for(t=4; // Set the temp integer `t` to 4
m[I=i/l][J=i%l]==n // If the current cell contains value `n`
&t-->0;) // Loop `t` in the range (4,0]:
try{m // Get the cell at a location relative to the current cell:
[I-=t-t%3*t>>1] // If `t` is 3:
// Take the cell above
// Else-if `t` is 2:
// Take the cell below
[J-=t<2?1-2*t:0] // Else-if `t` is 0:
// Take the cell left
// Else-if `t` is 1:
// Take the cell right
+=m[I][J]<1? // And if this cell contains a 0:
f=n+1 // Fill it with `n+1`,
// And set the flag to `n+1` as well
: // Else:
0; // Keep the value the same by increasing with 0
}finally{continue;} // Catch and ignore ArrayIndexOutOfBoundsExceptions
// (saves bytes in comparison to manual boundary checks)
return r;} // And after the loop: return the result
05AB1E , 18 byte
ΔĀ2FøJT‚12‚:€S]N
Emette il risultato incluso il primo passaggio.
Provalo online o verifica tutti i casi di test .
Spiegazione:
Δ # Loop until the result no longer changes,
# using the (implicit) input-matrix in the first iteration
Ā # Python-style truthify each integer, changing all potential 2s to 1s
2F # Loop 2 times:
ø # Zip/transpose; swapping rows/columns
J # Join each row of digits together to a string
T‚ # Pair 10 with its reversed: ["10","01"]
12‚ # Do the same for 12: ["12","21"]
: # Replace all "10" with "12" and all "01" with "21" in all rows
€S # And convert each row back to a list of digits
] # Close the nested loops
N # And push the 0-based index of the outer loop
# (note that the loop until the result no longer changes will loop an
# additional time, which is why this results in the correct result
# despite having 0-based indexing instead of 1-based)
# (after which it is output implicitly as result)
R , 105 101 byte
Modifica: -4 byte grazie a Giuseppe
function(m)max(apply(as.matrix(dist(which(m<2,T)[order(-!m),],"man"))[f<-1:sum(!m),-f,drop=F],1,min))
Provalo online!
covidsteps=
function(m, # m is input matrix
e=m<1) # e is uninfected cells
max( # get the max of the distances from each uninfected cell
# to its closest infected cell, by
apply(...,1,min) # getting the minima of
as.matrix(
dist(...,"man") # the pairwise manhattan distances between
which(m<2,T) # all coordinates
[order(-e),]) # ordered with infected cells first
[ # and selecting only distances between
f<-1:sum(e), # uninfected cells (rows in the distance matrix)
-f, # and infected cells (cols of the distance matrix)
drop=F])
Retina 0.8.2 , 100 byte
^
¶
{1s`¶(1.*0|0.*1)
_$& }`(?<=(.)*)0(?=(.*¶(?<-1>.)*(?(1)$))?1|(?<=10|¶(?(1)^)(?<-1>.)*1.*¶.*))
1
_
Provalo online! Accetta l'input come una matrice di cifre rettangolare. Spiegazione:
^
¶
Prepara una nuova riga per fornire un'area di lavoro per costruire il risultato. (Anche se posso aggiungere il risultato, ciò complica le espressioni regolari, quindi non è un giocatore di golf.)
{`
}`
Ripetere fino a raggiungere una posizione stabile (tutti 0o tutti 1).
1s`¶(1.*0|0.*1)
_$&
Se la posizione contiene una combinazione di se 0, 1aumentare il numero di giorni.
(?<=(.)*)0
Se c'è un 0che ...
(?=(.*¶(?<-1>.)*(?(1)$))?1|
... è direttamente accanto a un 1che a destra o in basso, oppure ...
(?<=10|¶(?(1)^)(?<-1>.)*1.*¶.*))
... è direttamente a destra di a 1o direttamente sotto a 1...
1
... quindi sostituiscilo con un file 1.
_
Visualizza il numero di giorni in decimale.
I controlli sopra / sotto vengono effettuati utilizzando i gruppi di bilanciamento .NET. L'iniziale (?<=(.)*)cattura il numero della colonna $#1e quindi abbiamo due casi:
.*¶(?<-1>.)*(?(1)$)1avanza alla riga successiva, avanza di un carattere per ogni colonna, verifica la colonna corretta ($non può corrispondere prima1, quindi(?(1)$)può corrispondere solo se non ci sono colonne rimaste per avanzare), quindi corrisponde1.(?<=¶(?(1)^)(?<-1>.)*1.*¶.*)è un lookbehind, quindi è abbinato da destra a sinistra: prima avanza alla riga precedente, poi trova una1, poi anticipi e controlli per la colonna corretta (^non possono eguagliare dopo¶perché non siamo in modalità multilinea, ma$sarebbe funziona anche), quindi controlla l'inizio della riga (non sarà l'inizio del buffer a causa dell'aggiunta¶all'inizio del programma).
CJam , 68 byte
{__{,,:)}:M~\zMm*\_{{_M.*}%\z}2*..{_{a+}{;;}?}:~f{\f{.-:z:+}$0=}$W=}
Provalo online!
Se solo sapessi come manipolare correttamente gli array 2D in questo linguaggio ...
Calcola il massimo di ciascuna distanza minima di Manhattan da ogni punto a ciascun punto infetto.
Perl 5 -00p , 63 , 60 byte
Ho salvato alcuni byte grazie a Dom Hastings.
/
/;$,='.'x"@-";$\++while s/(?<=1$,)0|1\K0|0(?=$,1|1)/1/gs}{
Provalo online!
Python 3 , 115 byte
f=lambda a,e=enumerate:all(map(all,a))or-~f([[1in[0,*r][j:j+3]+[0,*c][i:i+3]for j,c in e(zip(*a))]for i,r in e(a)])
Provalo online!
Soluzione ricorsiva con indice 1. Sostituisce ogni elemento con Truese stesso o con uno dei suoi vicini ortogonali sono 1(== True). La ricorsione si interrompe quando tutti i valori nell'array sono True.