Schreiben Sie ein Programm oder eine Funktion, die eine mehrzeilige Folge von 0
's und 1
' s enthält. Andere Zeichen werden in der Zeichenfolge sein , und die Zeichenfolge wird immer rechteckig sein (alle Linien dieselbe Anzahl von Zeichen haben), mit den Abmessungen so klein wie 1 × 1, aber ansonsten ist das 0
"s und 1
s können willkürlich angeordnet sein.
Sie können davon ausgehen, dass die Zeichenfolge eine optionale nachgestellte Newline enthält. Falls gewünscht, können Sie zwei verschiedene druckbare ASCII- Zeichen anstelle von 0
und verwenden 1
.
Drucke oder einen Rück truthy Wert , wenn alle von dem Pfad verbunden Regionen beide 0
's und 1
ist in der Zeichenfolge sind feste Rechtecken , sonst Ausgabe eines falsy Wert .
Eine pfadverbundene Region von 0
's bedeutet, dass von einer beliebigen 0
Region in der Region alle anderen 0
erreicht werden können, indem man sich nur nach oben, unten, links und rechts zu den anderen bewegt 0
(und sich nicht diagonal bewegt, sich nicht zu einer anderen bewegt 1
, und nicht außerhalb der Zeichenkettengrenzen bewegen). Die gleiche Idee gilt für 1
pfadverbundene Regionen.
Ein ausgefülltes Rechteck von 0
's bedeutet, dass der gesamte Bereich des Rechtecks mit 0
' s und no 1
's gefüllt ist . Die gleiche Idee gilt für 1
ausgefüllte Rechtecke.
Der kürzeste Code in Bytes gewinnt. Tiebreaker ist frühere Antwort.
(Beachten Sie, dass die Zeichenfolge nicht mit toroidalen Randbedingungen umwickelt wird .)
Beispiele
1) Diese Eingangszeichenfolge hat 3 pfadverbundene Bereiche (2 für 0
und 1 für 1
). Nur der rechte untere 00
Bereich ist ein ausgefülltes Rechteck, daher wäre die Ausgabe falsch.
0011
0111
0100
2) Diese Eingangszeichenfolge hat 4 pfadverbundene Bereiche (2 für beide 0
und 1
). Alle von ihnen sind feste Rechtecke, so dass die Ausgabe wahr sein würde.
0011
0011
1100
3) Dieser Eingang verfügt über 2 pfadverbundene Bereiche, von denen jedoch nur einer ein ausgefülltes Rechteck ist, sodass der Ausgang falsch wäre.
00000000
01111110
00000000
4) Dieser Eingang hat nur 1 Pfad verbundenen Bereich und ist trivial ein festes Rechteck, so dass der Ausgang wahr ist.
11111111
11111111
11111111
Testfälle
Ein T
knapp unter der Eingabezeile stehendes Zeichen bedeutet Wahrhaftigkeit, F
bedeutet Falschheit.
0
T
1
T
00
T
01
T
10
T
11
T
0000000
T
1111111
T
011100100100101100110100100100101010100011100101
T
00
11
T
01
10
T
01
11
F
00
01
F
11
11
T
110
100
F
111
000
T
111
101
111
F
101
010
101
T
1101
0010
1101
0010
T
1101
0010
1111
0010
F
0011
0111
0100
F
0011
0011
1100
T
00000000
01111110
00000000
F
11111111
11111111
11111111
T
0000001111
0000001111
T
0000001111
0000011111
F
0000001111
1000001111
F
1000001111
1000001111
T
1110100110101010110100010111011101000101111
1010100100101010100100010101010101100101000
1110100110010010110101010111010101010101011
1010100100101010010101010110010101001101001
1010110110101010110111110101011101000101111
F
Rubin, 76
In einem Gitter, das ausschließlich aus Rechtecken besteht, muss jede Zeile mit der vorherigen Zeile identisch sein, oder es müssen alle Bits von 0 auf 1 und umgekehrt umgedreht werden.
Dies ist leicht zu beweisen. Nehmen Sie ein Blatt Papier und ziehen Sie beliebige vertikale und horizontale Linien darüber. Färben Sie nun die Rechtecke mit nur 2 Farben. Sie erhalten ein verzerrtes Schachbrettmuster, bei dem alle Farben in jeder Zeile umkehren.
Möchten Sie Rechtecke mit Linien zeichnen, die nur einen Teil der Breite haben? Versuchen Sie, ein Segment Ihrer Zeilen zu löschen. Sie benötigen jetzt mehr als 2 Farben, um Ihr Design einzufärben, da Sie Punkte haben, an denen sich 3 Rechtecke treffen (2 Ecken und eine Kante). Solche Designs sind daher für diese Frage irrelevant.
Ich bin überrascht, dass Antworten dies bisher nicht bemerkt haben.
Ich denke, dieser Algorithmus sollte in einer anderen Sprache viel kürzer sein.
Ungolfed im Testprogramm
quelle
s.scan(/^?.*\n/)
würde helfen, Bytes zu sparen.Schnecken , 20 Bytes
Druckt den Bereich des Gitters, wenn es kein 2x2-Quadrat mit 3 Nullen und einer Eins oder drei Einsen und einer Null gibt oder
0
wenn ein solches 2x2-Quadrat vorhanden ist.quelle
MATL , 12 Bytes
Gleicher Algorithmus wie die großartige Antwort von @ sp3000 .
Um mehrzeilige Eingaben zuzulassen, muss das Zeilenzeichen-Array (String) explizit mit Zeichen
10
für Zeilenvorschub erstellt werden. Die Eingabe der vier Beispiele[]
lautet also (beachten Sie, dass es sich bei der Verkettung um ein Zeilenarray von Zeichen handelt):und die letzten drei Testfälle sind
Die Ausgabe von Truthy ist ein Array, das nur Einsen enthält.
Probieren Sie es online!
Erläuterung
Dies nutzt die Tatsache, dass die Parität von Zeichen
'0'
und'1'
die gleiche ist wie die von Zahlen0
und1
, so dass es nicht erforderlich ist, von char zu der Ziffer, die es darstellt, zu konvertieren.quelle
['first line' 10 'second llne']
, wobei10
ASCII für newline ist. Ist das akzeptabel'0011 0111 0100'
JavaScript (ES6), 69 Byte
Ich glaube, dass das Kriterium des Wegeverbindungsrechtecks der Forderung entspricht, dass es bei vier beliebigen Punkten, die die Ecken eines beliebigen Rechtecks bilden, eine gerade Anzahl von
1
s gibt. Beachten Sie, dass die Parität des Rechtecks (0, b), (x, y) mit (0, b), (a, y),^
(a, b), (x, y) identisch ist , sodass ich nur prüfen muss die Rechtecke, deren obere linke Ecke bei (0, 0) liegt. Auch nach De Morgans Gesetzen!.some()
ist es dasselbe,.every(!)
was mir ein paar Bytes erspart.Bearbeiten: Ich stelle fest, dass die Jelly-Lösung die Parität der Ecken aller 2 × 2-Rechtecke überprüft, die als äquivalent dargestellt werden können.
quelle
JavaScript (ES6), 79
Gleicher Algorithmus der Jelly-Antwort von @ Sp3000 (und froh, nicht beweisen zu müssen, dass es funktioniert). Nur 8 mal länger
Weniger golfen
Testsuite
quelle
Grime v0.1, 31 Bytes
Druckt
1
für Übereinstimmung und0
für keine Übereinstimmung. Probieren Sie es online!Erläuterung
Schmutz ist meine 2D-Pattern-Matching-Sprache. Ich habe es heute geändert, aber nur, um den Charakter eines Syntaxelements (
`
statt,
) zu ändern , damit es meine Punktzahl nicht beeinflusst.Ich benutze einen ähnlichen Ansatz wie Sp3000 : Eine Eingabe ist falsch, wenn sie ein 2 × N-Rechteck enthält, dessen eine Zeile beide
0
und enthält1
, und die andere Zeile nicht.quelle
JavaScript (ES6), 64 Byte
Basierend auf der Beobachtung von @ LevelRiverSt, dass jede Linie entweder die gleiche oder die entgegengesetzte sein muss wie die erste.
quelle