Oblicz spread COVID
Ponieważ koronawirus wciąż jest na wolności, pomyślałem, że warto podjąć wyzwanie związane z epidemią.
Wyzwanie
Otrzymujesz dwuwymiarową tablicę osób, gdzie 1reprezentuje osobę z wirusem i 0osobę bez wirusa. Każdego dnia ludzie zarażeni wirusem infekują swoich sąsiadów. Mając taką siatkę, musisz obliczyć, ile dni zajmie zarażenie populacji (czyli każdy przedmiot 1).
Zasady
- Wejście liczy się jako dzień 0, a każdy kolejny dzień zwiększa się o 1 (jeśli chcesz, możesz policzyć pierwszy dzień jako dzień 1, ale zaznacz to w swojej odpowiedzi).
- Elementy siatki nie muszą być
1s i0s, mogą to być dowolne wartości prawdziwe / fałszywe. Każdy element w siatce jest losowany do jednej z tych wartości. Proszę określić, które prawdziwe / fałszywe wartości Twój program będzie / nie zaakceptuje. - Siatka wejściowa może mieć dowolny rozmiar od 2x2 do 100x100. Siatka nie musi być kwadratowa. Rozmiar siatki jest losowy (tj. Nie możesz wybrać).
- Kwadraty ukośne nie liczą się jako sąsiadujące.
- To jest code-golf , więc najkrótsza odpowiedź wygrywa!
Przykłady
[[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
Odpowiedzi
Wzornik ≢ , 2 bajty
×v
Wypróbuj online!
≢oblicza liczbę niezbędnych kroków (w tym stan początkowy), aż do osiągnięcia stabilności. Ten argument wiersza poleceń nie jest wliczany do liczby bajtów, zgodnie z konsensusem Meta .
Następny stan każdej komórki jest określany przez:
× znak
v sumy wszystkich wartości w jego v na sąsiedztwie Neumann (włączając siebie)
Galaretka , 10 bajtów
ŒJạ€ŒṪ§Ṃ€Ṁ
Wypróbuj online!
-2 bajty dzięki Syzyfowi
Oblicz różnice Manhattanu od wszystkich zera do wszystkich jedynek, a odpowiedzią jest maksimum z minimów (minimum każdego wiersza to liczba etapów do zarażenia, więc liczba potrzebnych etapów to maksymalna liczba etapów potrzebnych dla każdej osoby ).
Dogodnie, jeśli wszystkie elementy mają wartość 1, zwraca to 0, ponieważ jest to domyślna wartość minmax.
Jeśli żadna osoba nie jest zarażona w stanie początkowym, to również zwraca 0.
Wyjaśnienie
Œ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)
Język Wolfram (Mathematica) , 90 78 bajtów
f=Length@FixedPointList[ListConvolve[CrossMatrix@1,#,{2,2},0,Times,Max]&,#]-2&
Wypróbuj online!
-12 bajtów, ponieważ oczywiście jest wbudowana CrossMatrixfunkcja do konstruowania jądra \$K\$.
Definiuje czystą funkcję, fktóra przyjmuje macierz jako dane wejściowe. Jeśli nikt nie jest zarażony, wróć 0. Wykorzystuje splot listowy do rozprzestrzeniania się choroby z dnia na dzień i wbudowaną funkcję Mathematica, która zapętla się, aż do osiągnięcia ustalonego punktu (tj. Wszyscy zostaną zarażeni). Wyjaśnienie:
Aby rozprzestrzenić chorobę, użyj jądra
$$K=\begin{pmatrix} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 0 \end{pmatrix}$$
i lista splotów. Na przykład, jeśli zaczniemy od
$$I_0=\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}$$
następnie zastosowanie
ListConvolve[{{0, 1, 0}, {1, 1, 1}, {0, 1, 0}}, #, {2, 2}, 0] &
prowadzi do
$$\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 2 & 2 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}.$$
W rzeczywistości nie musimy wiedzieć, czy dana osoba jest zarażona wiele razy, więc w obrębie splotu listy zamiast sumowania przyjmiemy po prostu maksimum
ListConvolve[{{0, 1, 0}, {1, 1, 1}, {0, 1, 0}}, #, {2, 2}, 0, Times, Max] &
co daje
$$\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}.$$
Następnie musimy tylko iterować, aż osiągnięty zostanie ustalony punkt, tj. Każdy zostanie zainfekowany, aby nie wystąpiły żadne nowe infekcje. Jest (jak zwykle) poręczny wbudowany w Mathematica FixedPointList, który wyświetla listę wszystkich iteracji aż do osiągnięcia stałego punktu. Ponieważ ta lista zawiera dwa razy dane wejściowe i stały punkt, po prostu odejmij dwa od długości listy, aby uzyskać odpowiedź.
Na marginesie, parametry ListConvolvezapewniają, że splot działa dobrze z jądrem. Z domyślnymi parametrami, convolving
$$\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix}$$
z jądrem
$$\begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix}$$
daje raczej bezużytecznie
$$\begin{pmatrix} 0 & 0 \\ b & c \end{pmatrix}.$$
Aby przynajmniej zachować wymiary, dodamy parametr {1,1}, który teraz daje
$$\begin{pmatrix} 0 & d & e & f \\ 0 & g & h & i \\ 0 & 0 & 0 & 0 \\ 0 & a & b & c \\ \end{pmatrix}.$$
Tym razem problem jest to, że zaczyna splotu w lewym górnym rogu, a nie w środku jądra, więc zmieńmy {1,1}się {2,2}, co daje
$$\begin{pmatrix} g & h & i & 0 \\ 0 & 0 & 0 & 0 \\ a & b & c & 0 \\ d & e & f & 0 \\ \end{pmatrix}.$$
To jest prawie to, czego potrzebujemy, ale dół jądra przelewa się do góry. Aby to naprawić, po prostu dodamy parametr wypełnienia 0. Wreszcie
$$\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ a & b & c & 0 \\ d & e & f & 0 \\ \end{pmatrix}.$$
Oktawa , 26 bajtów
@(x)max(bwdist(x,'ci')(:))
Wypróbuj online!
Dla każdej komórki oblicz odległość do najbliższej niezerowej komórki pod \$L_1\$norma (metryczna taksówka). Rozwiązaniem jest wartość maksymalna.
APL (Dyalog Extended) , 20 bajtów
{⌈/⌊⌿⍵∘.(1⊥∘|-)⍥⍸~⍵}
Wypróbuj online!
Używa metody odległości Manhattan z odpowiedzi HyperNeutrino's Jelly.
Wejście to macierz binarna.
Wyjaśnienie
{⌈/⌊⌿⍵∘.(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 bajtów
Zapisano aż 31 39 40 44 56 57 bajtów dzięki sufitowi !
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;}
Wypróbuj online!
Wprowadza siatkę populacji jako wskaźnik do tablicy ints, czyli \$1\$dla zainfekowanych lub \$0\$w przeciwnym razie wraz z liczbą wierszy i kolumn. Zwraca liczbę dni potrzebnych do zainfekowania populacji.
W jaki sposób?
Tworzy tablicę cieni, pktóra ma jedną granicę wokół niej, więc nie musimy się martwić, że sąsiedzi nie będą tam, gdy jesteśmy na krawędzi. Inicjuje wszystkie swoje elementy do \$0\$. Każdego dnia przechodzimy następnie przez siatkę populacji wejściowej, sprawdzając wiersz po wierszu i kolumnę po kolumnie pod kątem zainfekowanych elementów. Dla wszystkich znalezionych oznaczamy tę pozycję w tablicy shadow i jej \$4\$sąsiedzi jako zarażeni. Następnie, tego samego dnia, ponownie przeglądamy tablicę wejściową, kopiując odpowiednie elementy cienia i zliczając całkowitą liczbę zainfekowanych tego dnia. Zwraca liczbę dni, które minęły, zanim wszyscy zostali zainfekowani.
J , 35 bajtów
1-~&#<@_>./@:(|.!.0)~&(0,(,-)=i.2)]
Wypróbuj online!
(0,(,-)=i.2):0 0,1 0,0 1,-1 0,0 -1<@_ f&dirs ]powtarzaj,input f dirsaż wynik się nie zmieni, i zwróć wszystkie kroki pośrednie.>./@:(|.!.0)~przesuwaj planszę wzdłuż kierunków (z0przesunięciem s na krawędziach) i weź maksimum z nich wszystkich.1-~&#policz kroki minus 1.
JavaScript (ES6), 97 95 bajtów
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])))
Wypróbuj online!
Skomentowano
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 bajtów
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])
Wypróbuj online!
Jeśli nikt nie jest zainfekowany w oryginale, zwróci to 0.
-11 bajtów dzięki caird coinheringaahing
Wypróbuj online!
Starsza metoda wykorzystująca rekurencję:
Python 3 , 199 bajtów
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]
Wypróbuj online!
Jeśli w oryginale nie ma nikogo zainfekowanego, spowoduje to przepełnienie rekursji.
Węgiel , 39 bajtów
Ｉ⌈Ｅθ∨⌈Ｅ⌕Ａι⁰∨⌊ΦＥθ⌊Ｅ⌕Ａν¹⁺↔⁻ξκ↔⁻πλ¬⁼νＩν⁰¦⁰
Wypróbuj online! Link prowadzi do pełnej wersji kodu. Ponownie używa metody odległości Manhattanu. Węgiel nie może spłaszczyć list, a ponadto zwraca Noneminimum lub maksimum pustej listy, co nieco komplikuje kod. Wyjaśnienie:
Ｅθ 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 bajtów
{|/&/{+/x|-x}''u-\:/:(1=x.)#u:+!(#x),#*x}
Wypróbuj online!
Maksymalna minimalna odległość Manhattanu każdego punktu do każdego prawdziwego punktu.
{ } \ 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 bajty
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;}
Drobna modyfikacja mojej odpowiedzi tutaj .
Podaje wynik wraz z pierwszym krokiem.
Wypróbuj online.
Wyjaśnienie:
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 bajtów
ΔĀ2FøJT‚12‚:€S]N
Podaje wynik wraz z pierwszym krokiem.
Wypróbuj online lub zweryfikuj wszystkie przypadki testowe .
Wyjaśnienie:
Δ # 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 bajtów
Edycja: -4 bajty dzięki Giuseppe
function(m)max(apply(as.matrix(dist(which(m<2,T)[order(-!m),],"man"))[f<-1:sum(!m),-f,drop=F],1,min))
Wypróbuj 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 bajtów
^
¶
{1s`¶(1.*0|0.*1)
_$& }`(?<=(.)*)0(?=(.*¶(?<-1>.)*(?(1)$))?1|(?<=10|¶(?(1)^)(?<-1>.)*1.*¶.*))
1
_
Wypróbuj online! Przyjmuje dane wejściowe jako prostokątną tablicę cyfr. Wyjaśnienie:
^
¶
Wstaw nowy wiersz, aby zapewnić obszar roboczy do budowania wyniku. (Chociaż mogę zamiast tego dołączyć wynik, to komplikuje wyrażenia regularne, więc nie jest to żaden golfista).
{`
}`
Powtarzaj aż do osiągnięcia stabilnej pozycji (wszystkie 0lub wszystkie 1).
1s`¶(1.*0|0.*1)
_$&
Jeśli pozycja zawiera kombinację 0s i 1s, zwiększ liczbę dni.
(?<=(.)*)0
Jeśli jest coś 0takiego ...
(?=(.*¶(?<-1>.)*(?(1)$))?1|
... znajduje się bezpośrednio obok 1znaku znajdującego się po prawej lub poniżej, albo ...
(?<=10|¶(?(1)^)(?<-1>.)*1.*¶.*))
... znajduje się bezpośrednio na prawo od a 1lub bezpośrednio pod 1...
1
... następnie zamień go na 1.
_
Podaj liczbę dni w postaci dziesiętnej.
Powyższe / poniżej sprawdzenia są wykonywane przy użyciu grup równoważenia .NET. Początek (?<=(.)*)pobiera numer kolumny do $#1, a następnie mamy dwa przypadki:
.*¶(?<-1>.)*(?(1)$)1przechodzi do następnego wiersza, przesuwa o jeden znak w każdej kolumnie, sprawdza poprawną kolumnę ($nie może być wcześniej dopasowana1, więc(?(1)$)może dopasować tylko wtedy, gdy nie ma żadnych kolumn do przejścia), a następnie dopasowuje1.(?<=¶(?(1)^)(?<-1>.)*1.*¶.*)jest lookbehind, więc jest dopasowany od prawej do lewej: pierwszy to przejście do poprzedniej linii, a następnie znajdzie1, to postęp i czeki dla prawidłowej kolumnie (^nie może się równać po¶ponieważ nie jesteśmy w stanie multilinii, ale$będzie również działa), a następnie sprawdza początek linii (nie będzie to początek bufora z powodu¶dodania na początku programu).
CJam , 68 bajtów
{__{,,:)}:M~\zMm*\_{{_M.*}%\z}2*..{_{a+}{;;}?}:~f{\f{.-:z:+}$0=}$W=}
Wypróbuj online!
Gdybym tylko wiedział, jak poprawnie manipulować tablicami 2D w tym języku ...
Oblicza maksymalną minimalną odległość Manhattanu od każdego punktu do każdego zainfekowanego punktu.
Perl 5 -00p , 63 , 60 bajtów
Oszczędzono trochę bajtów dzięki Domowi Hastingsowi.
/
/;$,='.'x"@-";$\++while s/(?<=1$,)0|1\K0|0(?=$,1|1)/1/gs}{
Wypróbuj online!
Python 3 , 115 bajtów
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)])
Wypróbuj online!
Rozwiązanie rekurencyjne z 1 indeksowaniem. Zastępuje każdy element znakiem Trueif on sam lub którykolwiek z jego ortogonalnych sąsiadów to 1(== True). Rekursja zatrzymuje się, gdy wszystkie wartości w tablicy są True.