Berechnen Sie den COVID-Spread
Da das Coronavirus immer noch auf freiem Fuß ist, hielt ich es für angebracht, eine epidemische Herausforderung zu haben.
Herausforderung
Sie erhalten eine 2D-Gruppe von Personen, in 1der jemand mit dem Virus und 0jemand ohne den Virus dargestellt wird. Jeden Tag infizieren die Menschen mit dem Virus ihre Nachbarn. Bei einem solchen Raster müssen Sie berechnen, wie viele Tage es dauern wird, um die Bevölkerung zu infizieren (dh jeder Gegenstand ist 1).
Regeln
- Die Eingabe zählt als Tag 0 und erhöht sich jeden Tag danach um 1 (Sie können den ersten Tag als Tag 1 zählen, wenn Sie möchten, geben dies jedoch in Ihrer Antwort an).
- Die Rasterelemente müssen nicht
1s und0s sein, sie können beliebige Wahrheits- / Falschwerte sein. Jedes Element im Raster wird nach dem Zufallsprinzip einem dieser Werte zugeordnet. Bitte geben Sie an, welche Wahrheits- / Falschwerte Ihr Programm akzeptiert / nicht akzeptiert. - Das Eingaberaster kann eine beliebige Größe zwischen 2x2 und 100x100 haben. Das Gitter muss nicht quadratisch sein. Die Rastergröße ist zufällig (dh Sie können nicht wählen).
- Diagonale Quadrate zählen nicht als benachbart.
- Dies ist Code-Golf , also gewinnt die kürzeste Antwort!
Beispiele
[[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
Antworten
Schablone ≢ , 2 Bytes
×v
≢zählt die Anzahl der notwendigen Schritte (einschließlich des Ausgangszustands), bis die Stabilität erreicht ist. Dieses Befehlszeilenargument wird gemäß Meta-Konsens nicht auf die Anzahl der Bytes angerechnet .
Der nächste Zustand jeder Zelle wird bestimmt durch:
× das Vorzeichen
v der Summe aller Werte in seinem v auf Neumann Nachbarschaft (einschließlich sich selbst)
Gelee , 10 Bytes
ŒJạ€ŒṪ§Ṃ€Ṁ
-2 Bytes dank Sisyphus
Berechnen Sie die Manhattan-Unterschiede von allen Nullen zu allen Einsen, und die Antwort ist das Maximum des Minimums (das Minimum jeder Zeile ist die Anzahl der Stufen, bis sie infiziert wird, sodass die Anzahl der erforderlichen Stufen das Maximum der Stufen ist, die für jede Person benötigt werden ).
Wenn alle Elemente 1 sind, wird zweckmäßigerweise 0 zurückgegeben, da dies der Standardwert für minmax ist.
Wenn im Ausgangszustand keine Person infiziert ist, gibt dies ebenfalls 0 zurück.
Erläuterung
Œ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&
-12 Bytes, da natürlich ein CrossMatrixKernel eingebaut ist \$K\$.
Definiert eine reine Funktion f, die eine Matrix als Eingabe verwendet. Wenn niemand infiziert ist, kehren Sie zurück 0. Verwendet die Listenfaltung, um die Krankheit Tag für Tag zu verbreiten, und eine in Mathematica integrierte Schleife, bis ein fester Punkt erreicht ist (dh jeder ist infiziert). Erläuterung:
Verwenden Sie einen Kernel, um die Krankheit zu verbreiten
$$K=\begin{pmatrix} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 0 \end{pmatrix}$$
und Faltung auflisten. Zum Beispiel, wenn wir bei beginnen
$$I_0=\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}$$
dann bewerben
ListConvolve[{{0, 1, 0}, {1, 1, 1}, {0, 1, 0}}, #, {2, 2}, 0] &
führt zu
$$\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 2 & 2 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}.$$
Wir müssen eigentlich nicht wissen, ob eine Person mehrmals infiziert ist. Innerhalb der Listenfaltung nehmen wir also nur das Maximum, anstatt zu summieren
ListConvolve[{{0, 1, 0}, {1, 1, 1}, {0, 1, 0}}, #, {2, 2}, 0, Times, Max] &
was gibt
$$\begin{pmatrix} 0 & 1 & 1 & 0 \\ 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \\ \end{pmatrix}.$$
Dann müssen wir es nur noch wiederholen, bis ein fester Punkt erreicht ist, dh jeder ist infiziert, bis keine neuen Infektionen auftreten können. In Mathematica ist (wie üblich) eine praktische integrierte Funktion enthalten FixedPointList, die eine Liste aller Iterationen enthält, bis ein fester Punkt erreicht ist. Da diese Liste die Eingabe und den Fixpunkt zweimal enthält, subtrahieren Sie einfach zwei von der Listenlänge, um die Antwort zu erhalten.
Nebenbei bemerkt stellen die Parameter ListConvolvesicher, dass die Faltung gut mit dem Kernel zusammenarbeitet. Mit den Standardparametern Faltung
$$\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \end{pmatrix}$$
mit dem Kernel
$$\begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix}$$
gibt eher nutzlos
$$\begin{pmatrix} 0 & 0 \\ b & c \end{pmatrix}.$$
Um zumindest die Dimensionen beizubehalten, fügen wir den Parameter hinzu {1,1}, der jetzt angegeben wird
$$\begin{pmatrix} 0 & d & e & f \\ 0 & g & h & i \\ 0 & 0 & 0 & 0 \\ 0 & a & b & c \\ \end{pmatrix}.$$
Dieses Mal besteht das Problem darin, dass die Faltung in der oberen linken Ecke statt in der Mitte des Kernels beginnt. Ändern wir also das {1,1}in {2,2}, was ergibt
$$\begin{pmatrix} g & h & i & 0 \\ 0 & 0 & 0 & 0 \\ a & b & c & 0 \\ d & e & f & 0 \\ \end{pmatrix}.$$
Dies ist fast das, was wir brauchen, aber die Unterseite des Kernels läuft nach oben über. Um dies zu beheben, fügen wir einfach einen Auffüllparameter hinzu 0. Schließlich
$$\begin{pmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ a & b & c & 0 \\ d & e & f & 0 \\ \end{pmatrix}.$$
Oktave , 26 Bytes
@(x)max(bwdist(x,'ci')(:))
Berechnen Sie für jede Zelle den Abstand zur nächsten Zelle ungleich Null unter \$L_1\$Norm (Taximetrik). Die Lösung ist der Maximalwert.
APL (Dyalog Extended) , 20 Bytes
{⌈/⌊⌿⍵∘.(1⊥∘|-)⍥⍸~⍵}
Verwendet die Manhattan Distance-Methode aus HyperNeutrinos Jelly-Antwort.
Die Eingabe ist eine binäre Matrix.
Erläuterung
{⌈/⌊⌿⍵∘.(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
Dank Ceilingcat satte 31 39 40 44 56 57 Bytes gespart !!!
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;}
Gibt das Populationsraster als Zeiger auf ein Array von ints ein, die entweder \ sind$1\$für infizierte oder \$0\$Andernfalls zusammen mit der Anzahl der Zeilen und Spalten. Gibt die Anzahl der Tage zurück, die zur Infektion der Bevölkerung benötigt werden.
Wie?
Erstellt ein Schattenarray pmit einer Ein-Element-Grenze, sodass wir uns keine Sorgen machen müssen, dass die Nachbarn nicht da sind, wenn wir an den Rändern sind. Initialisiert alle seine Elemente auf \$0\$. Für jeden Tag gehen wir dann zeilenweise und spaltenweise durch das Eingabepopulationsraster, um nach infizierten Elementen zu suchen. Für alle gefundenen markieren wir diese Position im Schattenarray und sein \$4\$Nachbarn als infiziert. Danach gehen wir am selben Tag das Eingabearray erneut durch, kopieren die entsprechenden Schattenelemente und zählen die Gesamtzahl der Infizierten für diesen Tag. Gibt die Anzahl der Tage zurück, die vergangen sind, bis alle infiziert sind.
J , 35 Bytes
1-~&#<@_>./@:(|.!.0)~&(0,(,-)=i.2)]
(0,(,-)=i.2)::0 0,1 0,0 1,-1 0,0 -1<@_ f&dirs ]Wiederholen Sie diesen Vorgang,input f dirsbis sich das Ergebnis nicht mehr ändert, und geben Sie alle Zwischenschritte zurück.>./@:(|.!.0)~Verschieben Sie das Brett entlang der Richtungen (wobei0s an den Rändern verschoben wird) und nehmen Sie das Maximum von allen.1-~&#Zähle die Schritte minus 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])))
Kommentiert
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])
Wenn im Original niemand infiziert ist, wird 0 zurückgegeben.
-11 Bytes dank Caird Coinheringaahing
Ältere Methode mit Rekursion:
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]
Wenn im Original niemand infiziert ist, kommt es zu einem Rekursionsüberlauf.
Holzkohle , 39 Bytes
Ｉ⌈Ｅθ∨⌈Ｅ⌕Ａι⁰∨⌊ΦＥθ⌊Ｅ⌕Ａν¹⁺↔⁻ξκ↔⁻πλ¬⁼νＩν⁰¦⁰
Probieren Sie es online aus! Der Link führt zur ausführlichen Version des Codes. Verwendet erneut die Manhattan-Distanzmethode. Holzkohle kann Listen nicht reduzieren und gibt Nonefür das Minimum oder Maximum einer leeren Liste zurück, was den Code etwas kompliziert. Erläuterung:
Ｅθ 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}
Maximum der Minimums der Manhattan-Entfernung von jedem Punkt zu jedem Wahrheitspunkt.
{ } \ 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;}
Kleinere Änderung meiner Antwort hier .
Gibt das Ergebnis einschließlich des ersten Schritts aus.
Erläuterung:
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
Gibt das Ergebnis einschließlich des ersten Schritts aus.
Probieren Sie es online aus oder überprüfen Sie alle Testfälle .
Erläuterung:
Δ # 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
Edit: -4 Bytes dank Giuseppe
function(m)max(apply(as.matrix(dist(which(m<2,T)[order(-!m),],"man"))[f<-1:sum(!m),-f,drop=F],1,min))
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
_
Probieren Sie es online aus! Nimmt die Eingabe als rechteckiges Ziffernarray auf. Erläuterung:
^
¶
Stellen Sie eine neue Zeile vor, um einen Arbeitsbereich zum Aufbau des Ergebnisses bereitzustellen. (Obwohl ich stattdessen das Ergebnis anhängen kann, erschwert dies die regulären Ausdrücke, sodass es kein Golfer ist.)
{`
}`
Wiederholen, bis eine stabile Position erreicht ist (entweder alle 0s oder alle 1s).
1s`¶(1.*0|0.*1)
_$&
Wenn die Position eine Mischung aus 0s und 1s enthält, erhöhen Sie die Anzahl der Tage.
(?<=(.)*)0
Wenn es das gibt 0...
(?=(.*¶(?<-1>.)*(?(1)$))?1|
... befindet sich direkt neben einem 1, entweder rechts oder unten, oder ...
(?<=10|¶(?(1)^)(?<-1>.)*1.*¶.*))
... befindet sich entweder direkt rechts von a 1oder direkt unter einem 1...
1
... dann durch a ersetzen 1.
_
Geben Sie die Anzahl der Tage in Dezimalzahl aus.
Die obigen / unteren Überprüfungen werden mithilfe von .NET-Ausgleichsgruppen durchgeführt. Der Anfangsbuchstabe (?<=(.)*)greift in die Spaltennummer ein $#1, und dann haben wir zwei Fälle:
.*¶(?<-1>.)*(?(1)$)1geht zur nächsten Zeile über, rückt für jede Spalte ein Zeichen vor, sucht nach der richtigen Spalte ($kann möglicherweise vorher nicht übereinstimmen1,(?(1)$)kann also nur übereinstimmen, wenn keine Spalten mehr vorhanden sind) und stimmt dann überein1.(?<=¶(?(1)^)(?<-1>.)*1.*¶.*)ist ein Lookbehind, wird also von rechts nach links abgeglichen: Zuerst wird zur vorherigen Zeile übergegangen, dann wird eine gefunden1, dann wird die richtige Spalte aufgerufen und überprüft (^kann danach nicht mehr übereinstimmen,¶da wir uns nicht im mehrzeiligen Modus befinden, aber$würden funktioniert auch), prüft dann auf den Zeilenanfang (es wird nicht der Start des Puffers sein, da er¶zu Beginn des Programms hinzugefügt wurde).
CJam , 68 Bytes
{__{,,:)}:M~\zMm*\_{{_M.*}%\z}2*..{_{a+}{;;}?}:~f{\f{.-:z:+}$0=}$W=}
Wenn ich nur wüsste, wie man 2D-Arrays in dieser Sprache richtig manipuliert ...
Berechnet das Maximum jeder minimalen Manhattan-Entfernung von jedem Punkt zu jedem infizierten Punkt.
Perl 5 -00p , 63 , 60 Bytes
Dank Dom Hastings wurden einige Bytes gespeichert.
/
/;$,='.'x"@-";$\++while s/(?<=1$,)0|1\K0|0(?=$,1|1)/1/gs}{
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)])
1-indizierte rekursive Lösung. Ersetzt jedes Element durch Trueif (selbst) oder einen seiner orthogonalen Nachbarn 1(== True). Die Rekursion stoppt, wenn alle Werte im Array vorhanden sind True.