Gitter können kurvig sein. Wie lange ist deins

12

Stellen Sie eine einfache , offene , zweidimensionale Kurve in einem breiten x hohen Textgitter dar, in dem ein XTeil der Kurve und ein .leerer Raum dargestellt werden und keine anderen Zeichen verwendet werden.

Jeder Gitterplatz hat 8 benachbarte Gitterplätze, die Nachbarschaft Moore . Gitterbereiche außerhalb der Grenzen werden als leer betrachtet.

Ein Gitter enthält eine Kurve, wenn es genau ein X ODER hat, wenn es mehr als ein hat, Xwobei:

  • Genau zwei Xs haben nur einen Nachbarn X. Dies sind die Endpunkte der Kurve.
  • Jeder Xneben den Endpunkten Nachbarn genau zwei Xs. Diese bilden den Hauptteil der Kurve.

Zum Beispiel enthält dieses Raster mit W = 9 und H = 4 eine Kurve:

....X....
.X.X.X.X.
X..X..X.X
.XX.....X

Ebenso haben diese Gitter (W = 4, H = 3) Kurven:

....  .X..  ....  ....  .X.X
....  X..X  ..X.  XX..  X.X.
..X.  .XX.  .X..  ....  ....

Diese Gitter enthalten jedoch keine Kurve:

....  .XX.  ...X  XX..  ....  X.X.
....  X..X  ..XX  XX..  .X.X  .X..
....  .XX.  .X..  ....  ...X  X.X.

Wir können die Länge einer Kurve ermitteln, indem wir die Abstände zwischen allen benachbarten Paaren von Xs summieren :

  • Der Abstand zweier orthogonal benachbarter Xs beträgt 1 Einheit.

    XX
    X
X

  • Der Abstand zwischen zwei diagonal benachbarten Xs beträgt √2 Einheiten.

    X.
.X
    .X
X.

Zum Beispiel die Länge der Kurve im Raster

XXX.
...X
..X.

kann visualisiert werden als

Länge Beispiel

wir können also sehen, dass es 1 + 1 + √2 + √2 = 4.828427 ist ...

Die Länge einer Kurve mit nur einer Xist Null.

Wenn ein Gitter keine Kurve bildet, ist seine Länge nicht genau definiert.

Herausforderung

Bei einem vorgegebenen Textraster aus Xs und .s geben Sie die Länge der Kurve aus, die es enthält, oder geben Sie etwas wie -1oder ausNull um anzuzeigen, dass das Raster keine Kurve enthält.

Für die Eingabe können Sie andere Zeichen als Xund verwenden ., und H und W können bei Bedarf als Eingabe verwendet werden. Die Eingabe als verschachtelte Liste oder Matrix mit Einsen und Nullen anstelle einer Zeichenfolge ist ebenfalls in Ordnung.

Sie können einen Gleitkommawert für die Kurvenlänge oder alternativ zwei ganze Zahlen A und B ausgeben length = A + B*√2.

Der kürzeste Code in Bytes gewinnt.

Testfälle

XXX.
...X
..X.
2 + 2*√2 = 4.828427...

....X....
.X.X.X.X.
X..X..X.X
.XX.....X
3 + 8*√2 = 14.313708...

....
....
..X.
0 + 0*√2 = 0

.X..
X..X
.XX.
1 + 3*√2 = 5.242640...

....
..X.
.X..
0 + 1*√2 = 1.414213...

....
XX..
....
1 + 0*√2 = 1

.X.X
X.X.
....
0 + 3*√2 = 4.242640...

....
....
....
....
-1

.XX.
X..X
.XX.
-1

...X
..XX
.X..
-1

....
.X.X
...X
-1

X.X.
.X..
X.X.
-1
code-golf arithmetic geometry grid graph-theory Calvins Hobbys
quelle
Ich empfehle dem Solver die Auswahl des Ausgabeformats für Raster ohne Kurven (jeder konsistente Wert, der nicht die Form m + n * sqrt (2) für m, n≥0 hat).
Greg Martin
@ Greg Klingt gut. Fertig
Calvins Hobbys
[x.x,...,.x.]ist keine gültige Kurve, oder?
Magic Octopus Urn
@ Carusocomputing richtig
Calvin Hobbies

Antworten:

3

MATL , 52 51 Bytes

t2Y6~Z+*ssGt3Y6Z+*tt1=z2=wssGzqE=*Gz1=+?}_q]ssy-h2/

Die Eingabe ist eine Matrix aus Nullen und Einsen.

Ausgabe ist Bdann A. Nichtkurven ergeben ein Negativ A.

Probieren Sie es online! Oder überprüfen Sie alle Testfälle .

Erläuterung

Bei der Berechnung der Länge der Kurve werden zwei 2D-Faltungen 1 verwendet : eine mit der Moore-Maske und eine mit einer Maske, die nur die diagonalen Nachbarn enthält. Das Ergebnis sind zwei Matrizen mit der gleichen Größe der Eingabe, die als M bzw. D bezeichnet werden. M gibt die Gesamtzahl der Nachbarn für jeden Punkt an, während D die Anzahl der diagonalen Nachbarn angibt.

Die Ergebnisse in M und D müssen gefiltert werden, um Punkte zu verwerfen, die nicht zur Kurve gehören. Außerdem müssen sie durch 2 geteilt werden, da "Nachbar sein von" eine symmetrische Beziehung ist, sodass jeder Punkt in der Kurve zweimal gezählt wird.

Das Ermitteln, ob die Kurve gültig ist, ist umständlicher als erwartet. Zu diesem Zweck testet der Code drei Bedingungen:

  1. Ist die Anzahl der Einsen in M gleich 2? (Das heißt, gibt es genau zwei Punkte mit einem einzigen Nachbarn?)
  2. Entspricht die Gesamtsumme von M der Anzahl der Punkte in der Eingabekurve mal 2minus 2? (Zusammen mit Bedingung 1 wird geprüft, ob alle Nicht-Null-Werte in M außer zwei von ihnen gleich sind. 2)
  3. Enthält die Eingabekurve einen einzelnen Punkt?

Die Kurve ist gültig, wenn die Bedingungen 1 und 2 erfüllt sind oder Bedingung 3 erfüllt ist.

t       % Implicit input matrix of zeros and ones. Duplicate
2Y6~    % Push [1 0 1; 0 0 0; 1 0 1]
Z+      % 2D convolution, keeping size
*       % Multiply to zero out results for non-curve points. Gives matrix D
ss      % Sum of matrix D
Gt      % Push input again wtice
3Y6     % Push [1 1 1; 1 0 1; 1 1 1]
Z+      % 2D convolution, keeping size
*       % Multiply to zero out results for non-curve points. Gives matrix M
tt      % Duplicate twice
1=z     % Number of ones
2=      % Does it equal 2? This is condition 1
wss     % Swap. Sum of matrix
G       % Push input again
zqE     % Number of nonzeros values minus 1, and then multiplied by 2
=       % Are they equal? This is condition 2
*       % Multiply. This is a logical AND of conditions 1 and 2
G       % Push input again
z1=     % Does it contain exactly one nonzero value? This is condition 3
+       % Add. This is a logical OR with condition 3
?}      % If result was false
  _q    %   Negate and subtract 1. This makes sure we get a negative value
]       % End
ss      % Sum of matrix M
y       % Duplicate sum of matrix D from below
-       % Subtract
h       % Concatenate horizontally
2/      % Divide by 2. Implicitly display

1 Faltung ist der Schlüssel zum Erfolg .

Luis Mendo
quelle
1

Python 3 , 316 315 311 Bytes

Ich denke, das deckt alle Fälle ab; Zumindest funktionieren die Testfälle .

Auch gibt es sicher noch viel zu golfen, wahrscheinlich am Anfang, wo die Edge Cases bearbeitet werden.

def f(d,R,C):
 s=sum;d=[0]*(C+2),*[[0,*r,0]for r in d],[0]*(C+2);o=-1,0,1;k=[[[(1,0),(0,1)][i*j]for i in o for j in o if d[r+i][c+j]and i|j]for c in range(1,-~C)for r in range(1,-~R)if d[r][c]];w=[x/2for x in map(s,zip(*s(k,[])))]or[0,0];print([w,-1][s(w)!=s([s(z)for z in d])-1or[len(t)for t in k].count(1)>2])

Probieren Sie es online!

Wie es funktioniert:

  1. d,R,C sind 1. eine Liste von Listen mit 1 als Kurve und 0 als Hintergrund, 2. Zeilen- und Spaltenanzahl
  2. Fügen Sie eine Zeile mit Nullen vor und nach und eine Spalte mit Nullen vor und nach ein, ddamit wir uns nicht um den Rand des 2d-Arrays kümmern müssen
  3. Scannen Sie für jede 1 im 2d-Array die Nachbarschaft nach Einsen und fügen Sie (1,0) zu einer Liste hinzu, wenn die Beziehung diagonal ist, andernfalls fügen Sie (0,1) hinzu.
  4. Summiere alle Tupel, so dass (n, m) die Anzahl der diagonalen und nicht diagonalen Nachbarn darstellt
  5. Überprüfen Sie, ob die Anzahl der Relationen genau der Anzahl der Einsen minus Eins entspricht. Wenn nicht, keine Kurve.

Vielen Dank an @Helka Homba für den Hinweis auf einen fehlenden Fall. Vielen Dank an @TuukkaX und @Trelzevir für die Golftipps.

Nil
quelle
Sieht so aus, d=[[1,0,1],[0,1,0],[1,0,1]]als würde dies fehlschlagen (Testfall hinzugefügt).
Calvins Hobbys
@HelkaHomba Du hast Recht, ich habe das überwacht. Danke! Repariert es (jetzt leider mit mehr Bytes).
Nil
1
s=sumSpart 4 Bytes.
Trelzevir
0

Mathematica, 153 150 Bytes

Switch[Sort[Join@@BlockMap[If[#[[2,2]]<1,Nothing,Tr[Tr/@#]]&,#~ArrayPad~1,{3,3},1]],{1},0,{2,2,3...},1/.#~ComponentMeasurements~"PolygonalLength",_,]&

Nimmt ein 2D-Array mit 0s für .s und 1s für Xs. Ausgänge Nullfür Nichtkurven.

1/.#~ComponentMeasurements~"PolygonalLength"&

In Mathematica sind 45 Byte integriert, es werden jedoch einige Zahlen für Nichtkurven und 1 / sqrt (2) für die Eingabe ausgegeben {{1}}. Das Korrigieren dieser Kosten kostet 105 Bytes (könnte Golf gespielt werden?).

JungHwan min
quelle