Calcular spread COVID
Como o coronavírus ainda está em liberdade, achei que seria adequado ter um desafio com tema epidêmico.
Desafio
Você recebe um array 2D de pessoas, onde 1representa alguém com o vírus e 0alguém sem o vírus. Todos os dias, as pessoas com o vírus infectam seus vizinhos. Você deve calcular, dada essa grade, quantos dias levará para infectar a população (ou seja, cada item é 1).
Regras
- A entrada conta como Dia 0 e a cada dia seguinte aumenta em 1 (você pode contar o primeiro dia como Dia 1 se quiser, mas indique isso em sua resposta).
- Os itens da grade não precisam ser
1s e0s, eles podem ser quaisquer valores verdadeiros / falsos. Cada item na grade é randomizado para um desses valores. Especifique quais valores verdadeiros / falsos seu programa irá / não aceitará. - A grade de entrada pode ter qualquer tamanho entre 2x2 e 100x100. A grade não precisa ser quadrada. O tamanho da grade é aleatório (ou seja, você não pode escolher).
- Quadrados diagonais não contam como adjacentes.
- Este é o código de golfe , então a resposta mais curta vence!
Exemplos
[[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
Respostas
Estêncil ≢ , 2 bytes
×v
Experimente online!
≢registra o número de etapas necessárias (incluindo o estado inicial) até que a estabilidade seja alcançada. Este argumento de linha de comando não é contabilizado para a contagem de bytes, de acordo com o consenso Meta .
O próximo estado de cada célula é determinado por:
× o sinal da
v soma de todos os valores em seu v na vizinhança de Neumann (incluindo ele mesmo)
Gelatina , 10 bytes
ŒJạ€ŒṪ§Ṃ€Ṁ
Experimente online!
-2 bytes graças a Sísifo
Calcule as diferenças de Manhattan de todos os 0s para todos os 1s, e a resposta é o máximo dos mínimos (o mínimo de cada linha é o número de estágios até que seja infectado, então o número de estágios necessários é o máximo dos estágios necessários para cada pessoa )
Convenientemente, se todos os elementos forem 1, retornará 0, pois esse é o valor padrão para minmax.
Se nenhuma pessoa estiver infectada no estado inicial, também retorna 0.
Explicação
Œ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 bytes
f=Length@FixedPointList[ListConvolve[CrossMatrix@1,#,{2,2},0,Times,Max]&,#]-2&
Experimente online!
-12 bytes, porque é claro que há um built-in CrossMatrixpara construir o kernel \$K\$.
Define uma função pura fque recebe uma matriz como entrada. Se ninguém estiver infectado, volte 0. Usa convolução de lista para espalhar a doença dia-a-dia e um Mathematica embutido para loop até que um ponto fixo seja alcançado (ou seja, todos são infectados). Explicação:
Para espalhar a doença, use um kernel
$$K=\begin{pmatrix} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 0 \end{pmatrix}$$
e convolução de lista. Por exemplo, se começarmos em
$$I_0=\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}$$
então aplicando
ListConvolve[{{0, 1, 0}, {1, 1, 1}, {0, 1, 0}}, #, {2, 2}, 0] &
resulta em
$$\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 2 & 2 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}.$$
Na verdade, não precisamos saber se uma pessoa está infectada várias vezes, portanto, dentro da convolução da lista, em vez de somar, vamos apenas pegar o máximo
ListConvolve[{{0, 1, 0}, {1, 1, 1}, {0, 1, 0}}, #, {2, 2}, 0, Times, Max] &
que dá
$$\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}.$$
Então, só precisamos iterar até que um ponto fixo seja alcançado, ou seja, todos estão infectados para que nenhuma nova infecção possa ocorrer. Existe (como sempre) um prático embutido no Mathematica FixedPointList, que fornece uma lista de todas as iterações até que um ponto fixo seja alcançado. Uma vez que esta lista contém a entrada e o ponto fixo duas vezes, apenas subtraia dois do comprimento da lista para obter a resposta.
Como nota lateral, os parâmetros em ListConvolvegarantem que a convolução funcione bem com o kernel. Com os parâmetros padrão, convolvendo
$$\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix}$$
com o kernel
$$\begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix}$$
dá bastante inutilmente
$$\begin{pmatrix} 0 & 0 \\ b & c \end{pmatrix}.$$
Para pelo menos preservar as dimensões, vamos adicionar o parâmetro {1,1}, que agora dá
$$\begin{pmatrix} 0 & d & e & f \\ 0 & g & h & i \\ 0 & 0 & 0 & 0 \\ 0 & a & b & c \\ \end{pmatrix}.$$
Desta vez, o problema é que a convolução começa no canto superior esquerdo em vez de no centro do kernel, então vamos mudar o {1,1}para {2,2}, o que dá
$$\begin{pmatrix} g & h & i & 0 \\ 0 & 0 & 0 & 0 \\ a & b & c & 0 \\ d & e & f & 0 \\ \end{pmatrix}.$$
Isso é quase o que precisamos, mas a parte inferior do kernel transborda para o topo. Para corrigir isso, vamos apenas adicionar um parâmetro de preenchimento 0. Finalmente
$$\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ a & b & c & 0 \\ d & e & f & 0 \\ \end{pmatrix}.$$
Octave , 26 bytes
@(x)max(bwdist(x,'ci')(:))
Experimente online!
Para cada célula, calcule a distância até a célula diferente de zero mais próxima sob o \$L_1\$norma (métrica de táxi). A solução é o valor máximo.
APL (Dyalog Extended) , 20 bytes
{⌈/⌊⌿⍵∘.(1⊥∘|-)⍥⍸~⍵}
Experimente online!
Usa o método Manhattan Distance da resposta Jelly do HyperNeutrino.
A entrada é uma matriz binária.
Explicação
{⌈/⌊⌿⍵∘.(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 bytes
Salvou 31 39 40 44 56 57 bytes gritantes graças ao tetocat !!!
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;}
Experimente online!
Insere a grade de população como um ponteiro para uma matriz de ints, que são \$1\$para infectados ou \$0\$caso contrário, junto com o número de linhas e colunas. Retorna o número de dias que levará para infectar a população.
Como?
Cria uma matriz de sombra pque possui uma borda de elemento ao redor, para que não tenhamos que nos preocupar com os vizinhos não estarem lá quando estivermos nas bordas. Inicializa todos os seus elementos para \$0\$. Para cada dia, passamos pela grade de população de entrada, linha por linha e coluna por coluna, verificando os elementos infectados. Para todos os encontrados, marcamos essa posição na matriz de sombra e seu \$4\$vizinhos como infectados. Depois disso, no mesmo dia, percorremos o array de entrada novamente, copiando os elementos de sombra correspondentes e contando o número total de infectados naquele dia. Retorna o número de dias decorridos até que todos sejam infectados.
J , 35 bytes
1-~&#<@_>./@:(|.!.0)~&(0,(,-)=i.2)]
Experimente online!
(0,(,-)=i.2):0 0,1 0,0 1,-1 0,0 -1<@_ f&dirs ]repitainput f dirsaté que o resultado não mude e retorne todas as etapas intermediárias.>./@:(|.!.0)~mude o tabuleiro ao longo das direções (com os0s sendo deslocados nas bordas) e tire o máximo de todos eles.1-~&#conte os passos menos 1.
JavaScript (ES6), 97 95 bytes
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])))
Experimente online!
Comentou
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 bytes
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])
Experimente online!
Se ninguém estiver infectado no original, retornará 0.
-11 bytes graças a caird coinheringaahing
Experimente online!
Método mais antigo usando recursão:
Python 3 , 199 bytes
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]
Experimente online!
Se não houver ninguém infectado no original, ocorrerá um estouro de recursão.
Carvão , 39 bytes
Ｉ⌈Ｅθ∨⌈Ｅ⌕Ａι⁰∨⌊ΦＥθ⌊Ｅ⌕Ａν¹⁺↔⁻ξκ↔⁻πλ¬⁼νＩν⁰¦⁰
Experimente online! O link é para a versão detalhada do código. Usa o método de distância de Manhattan novamente. O carvão vegetal não pode nivelar listas, além de retornar Nonepara o mínimo ou máximo de uma lista vazia, o que complica um pouco o código. Explicação:
Ｅθ 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 bytes
{|/&/{+/x|-x}''u-\:/:(1=x.)#u:+!(#x),#*x}
Experimente online!
Máximo dos mínimos da distância Manhattan de cada ponto a cada ponto verdadeiro.
{ } \ 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 bytes
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;}
Pequena modificação da minha resposta aqui .
Produz o resultado incluindo a primeira etapa.
Experimente online.
Explicação:
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 bytes
ΔĀ2FøJT‚12‚:€S]N
Produz o resultado incluindo a primeira etapa.
Experimente online ou verifique todos os casos de teste .
Explicação:
Δ # 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 bytes
Editar: -4 bytes graças 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))
Experimente 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 bytes
^
¶
{1s`¶(1.*0|0.*1)
_$& }`(?<=(.)*)0(?=(.*¶(?<-1>.)*(?(1)$))?1|(?<=10|¶(?(1)^)(?<-1>.)*1.*¶.*))
1
_
Experimente online! Aceita a entrada como uma matriz retangular de dígitos. Explicação:
^
¶
Anexe uma nova linha para fornecer uma área de trabalho para construir o resultado. (Embora eu possa anexar o resultado em vez disso, isso complica as expressões regulares, portanto, não é nenhum jogador de golfe.)
{`
}`
Repita até que uma posição estável seja alcançada (todos 0s ou todos 1s).
1s`¶(1.*0|0.*1)
_$&
Se a posição contém uma mistura de 0s e 1s, aumente o número de dias.
(?<=(.)*)0
Se existe um 0que ...
(?=(.*¶(?<-1>.)*(?(1)$))?1|
... está diretamente ao lado de um 1que está à direita ou abaixo, ou ...
(?<=10|¶(?(1)^)(?<-1>.)*1.*¶.*))
... está diretamente à direita de a 1ou diretamente abaixo de 1...
1
... em seguida, substitua-o por um 1.
_
Produza o número de dias em decimal.
As verificações acima / abaixo são feitas usando grupos de balanceamento .NET. O inicial (?<=(.)*)captura o número da coluna $#1, e então temos dois casos:
.*¶(?<-1>.)*(?(1)$)1avança para a próxima linha, avança um caractere para cada coluna, verifica a coluna correta ($não é possível corresponder antes1, portanto,(?(1)$)só pode corresponder se não houver colunas restantes para avançar) e, em seguida, corresponde1.(?<=¶(?(1)^)(?<-1>.)*1.*¶.*)é um lookbehind, então é correspondido da direita para a esquerda: primeiro ele avança para a linha anterior, depois encontra um1, então avança e verifica a coluna correta (^não pode corresponder depois¶porque não estamos no modo multilinha, mas$iríamos também funciona), então verifica o início da linha (não será o início do buffer por causa do¶adicionado no início do programa).
CJam , 68 bytes
{__{,,:)}:M~\zMm*\_{{_M.*}%\z}2*..{_{a+}{;;}?}:~f{\f{.-:z:+}$0=}$W=}
Experimente online!
Se eu soubesse como manipular adequadamente matrizes 2D nesta linguagem ...
Calcula o máximo de cada distância mínima de Manhattan de cada ponto a cada ponto infectado.
Perl 5 -00p , 63 , 60 bytes
Economizei alguns bytes graças a Dom Hastings.
/
/;$,='.'x"@-";$\++while s/(?<=1$,)0|1\K0|0(?=$,1|1)/1/gs}{
Experimente online!
Python 3 , 115 bytes
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)])
Experimente online!
Solução recursiva indexada 1. Substitui cada item por Truese ele mesmo ou qualquer um de seus vizinhos ortogonais são 1(== True). A recursão para quando todos os valores na matriz são True.