Schreiben Sie ein Programm oder eine Funktion, die ein rechteckiges Textraster enthält, in dem jede Zelle entweder eine A
oder eine ist B
. Alle die A
Zellen eine Form einfach zusammenhängende Form, dh sie werden alle orthogonal werden verbunden ohne Löcher (diagonal benachbarten Buchstaben zählen nicht als angeschlossen). Ebenso bilden alle B
Zellen eine andere einfach verbundene Form. Das Gitter enthält immer mindestens eins A
und mindestens eins B
.
Stellen Sie sich vor, das Gitter besteht aus zwei quaderförmigen Teilen aus dünnem Kunststoff, die durch die Abschnitte A
und dargestellt werden B
. Wenn es flach auf einen Tisch gelegt würde, könnten die beiden Teile auseinander geschoben werden, während beide vollständig flach auf dem Tisch bleiben?
Drucken oder einen Rück truthy Wert , wenn die beiden A
und B
Formen wie diese getrennt werden konnten , indem sie einfach auseinanderziehen. Wenn nicht, drucken Sie einen falschen Wert oder geben Sie ihn zurück .
Zum Beispiel die Eingabe
AAA
ABB
AAA
ist wahr, weil der BB
Abschnitt nach rechts verschoben werden kann, indem er von den folgenden getrennt wird A
:
AAA
A BB
AAA
Allerdings ist die Eingabe
AAAA
ABBA
ABAA
ist falsch, weil es keine Möglichkeit gibt, die A
und B
Teile auseinander zu schieben, ohne dass sie sich überlappen.
Der kürzeste Code in Bytes gewinnt. Falls gewünscht, können Sie anstelle von und zwei beliebige druckbare ASCII- Zeichen verwenden .A
B
Wahrheitsbeispiele (durch Leerzeilen getrennt)
BBB
BAA
BBB
BA
A
B
AB
AB
AAA
BBB
AAAAB
ABBBB
ABBA
ABBA
AAAA
AAAAAABBBBBBBBB
AABBBBBBBBBBBBB
AAAAAAAAAABBBBB
AABBBBBBBBBBBBB
AAAAAAAAAAAAAAB
AAAAAAAAAAAA
ABABABABABAB
BBBBBBBBBBBB
BAAAAABB
BBAAABBB
BBBABBBB
BBBABBBB
BBBABBBB
BBBBBBBB
BBBBBBBB
AAA
BAA
AAA
Falsche Beispiele
BBBB
BAAB
BABB
BBBB
BAAB
AABB
BBBBBBB
BBBBBAB
AAAAAAB
BBBBBBB
BAAA
BABA
BBBA
AABA
AAAA
AAAAAAA
ABBBBBA
AAAAABA
BBBBBBA
BAAAAABB
BBAAABBB
BBBABBBB
BBBABBBB
BBBAABBB
BBBBBBBB
BBBBBBBB
AAA
ABA
BBA
ABA
AAA
CJam,
3332201917 BytesÜberarbeitete Version, mit massiver Unterstützung von @ Sp3000 und @ MartinBüttner:
Probieren Sie es online aus
Beiträge
Algorithmus und Beweis
Im Folgenden werden die Kriterien für das horizontale Auseinandergleiten des Puzzles erläutert. Der vertikale Fall kann durch Betrachten von Spalten anstelle von Zeilen oder durch Transponieren der Zeichenmatrix und erneutes Betrachten der Zeilen bestimmt werden.
Ich werde den Begriff "Strecken" für eine maximale Folge der gleichen Buchstaben verwenden. Beispielsweise haben die folgenden Zeilen 1, 2 und 3 Abschnitte:
Ich werde den Begriff "Interlocked" auch für eine Reihe / ein Puzzle verwenden, die / das nicht auseinander rutschen kann.
Die Schlüsselbeobachtung ist, dass das Puzzle nur dann auseinander rutschen kann, wenn alle Reihen höchstens 2 Strecken haben . Oder umgekehrt, es ist nur dann verriegelt, wenn es eine Reihe mit mehr als 2 Abschnitten gibt .
Das Folgende könnte nicht als strenger mathematischer Beweis gelten, aber ich glaube, dass es eine überzeugende Erklärung dafür liefert, warum dies der Fall sein muss.
Es ist leicht zu erkennen, dass das Puzzle verriegelt ist, wenn es Reihen mit mehr als 2 Abschnitten enthält. Eine Reihe mit 3 Strecken betrachten:
es ist klar, dass es verhindert, dass das Puzzle auseinander rutscht, da die
A
Strecke zwischen denB
Strecken gesperrt ist . Dies bedeutet, dass die Reihe ineinander greift, wodurch das gesamte Puzzle ineinander greift.Die Gegenrichtung des Beweises ist nicht ganz so offensichtlich. Wir müssen zeigen, dass es keine ineinandergreifenden Rätsel gibt, bei denen alle Reihen nur 1 oder 2 Strecken haben. Beginnen wir mit ein paar Beobachtungen:
A
und habenB
, ist das Rätsel eindeutig nicht miteinander verzahnt. In diesem FallA
bleiben alleB
Zellen von allen Zellen übrig oder umgekehrt, und es kommt zu keinen Kollisionen, wenn die beiden Teile auseinander geschoben werden.Der einzige schwierige Fall wären Rätsel, bei denen wir Reihen mit 2 Abschnitten unterschiedlicher Reihenfolge haben. Ich werde zeigen, dass solche Rätsel unter den angegebenen Spezifikationen nicht existieren . Um dies zu zeigen, schauen wir uns ein Teilpuzzlespiel mit dieser Konfiguration an, in dem
.
sich Platzhalter befinden:Nun, sagt die Spezifikation , dass sowohl die
A
undB
Zellen sind einfach in allen gültigen Puzzles verbunden. Um dieA
Zellen im obigen Teilrätsel zu verbinden, haben wir zwei Möglichkeiten:Wir umrunden einen der folgenden Abschnitte
B
:Um dies zu tun, erweitern wir unvermeidlich eine der Reihen auf 3 Strecken, so dass wir niemals ein gültiges Rätsel erhalten, bei dem alle Reihen höchstens 2 Strecken haben.
Wir verbinden sie auf direktem Weg:
Die
A
Zellen sind jetzt einfach verbunden und es gibt noch keine Zeilen mit mehr als 2 Abschnitten. DieB
Zellen müssen jedoch auch einfach verbunden werden. Der direkte Pfad wird jetzt von den verbundenenA
Zellen blockiert , und die einzige Möglichkeit, dieB
Zellen zu verbinden , besteht darin, eine der Zellabschnitte in einer Schleife zuA
durchlaufen. Dies führt zu Fall 1 zurück, in dem wir dies nicht tun können, ohne Zeilen mit 3 Abschnitten zu erstellen.Zum Zählen der Strecken verwendet die Implementierung den CJam-RLE-Operator.
Erklärung des Codes
quelle
JavaScript (ES6),
108107989182 ByteLive-Demo . Getestet in Firefox. Übernimmt die Eingabe als durch Zeilenumbrüche getrennte Zeichenfolge.
Bearbeitungen:
\n
zu einer wörtlichen Newline gewechselt wird.g
Funktion und RegExp direkt auf dem Array aufrufen, anstatt zu verwendenfind
.Wie es funktioniert
Vorherige Version:
a
und teilen Sie sie durch Zeilenumbrüche in eine Reihe von Zeichenfolgen auf.a
und speichern Sie es inT
. Verwenden Siemap
, um über jedes Element von zu iterierena
, die Zeichenfolge in ein Zeichenarray aufzuteilen undmap
erneut, um dasi
th-Zeichen in der Zeile an diei
th-Zeile von anzuhängenT
. Da jedes Element vonT
nicht initialisiert ist, sieht es am Ende so aus"undefinedAAABBA"
, aber das spielt keine Rolle.g
, die dem Muster entspricht/AB+A|BA+B/
. Wenn es passt, sind die Teile in der angegebenen Richtung verriegelt, weil dann ein Satz vonB
s zwischen zwei oder mehrA
s liegt oder umgekehrt.g
Testfunktion, um alle Elemente des Blocksa
und seine TransponierungT
auf eine Übereinstimmung mit zu testenfind
. Stimmen beide überein, sind die Teile in beide Richtungen verriegelt. Geben Sie daher einen falschen Wert aus, andernfalls einen wahren.quelle
Javascript (ES6), 118
Erläuterung:
quelle
JavaScript (ES6) 72
74Bearbeiten Sie 2 Bytes, die dank @NotthatCharles gespeichert wurden
Ich habe das intuitive Verständnis, dass ein Teil, wenn es nur einen Bruchteil einer Stufe gleiten kann, kostenlos ist. Die aktuellen Testfälle bestätigen dies.
Also überprüfe ich nur einen Schritt in jede Richtung.
Verwendete Zeichen: 1 und 0
2 Byte mehr, um 2 beliebige druckbare Zeichen wie A und B zu verwenden
Testen Sie das unten stehende Snippet in einem EcmaScript 6-kompatiblen Browser (unterstützt den Spread-Operator - IE Firefox).
quelle
s[p+o]=='0'
scheint ein bisschen lang zu sein. Könnte es ersetzt werden durch1-s[p+o]
oder zumindests[p+o]==0
?=='A'
kann durch ersetzt werden<'B'
. Gleiches gilt für=='B'
x+s[p+o]=='AB'
?Mathematica
10069 BytesDank @Martin Buttner konnten 31 Bytes eingespart werden.
Formatiert die Eingabe als Zeichenmatrix. Es macht auch eine Transponierung der Matrix. Wenn entweder die Matrix oder ihre Transponierte nicht mehr als 2 Läufe pro Reihe hat, kann das Rätsel verschoben werden.
{a,a,b,b,b}
hat 2 Buchstabenreihen.{a,a,b,a,a}
hat 3 Buchstabenreihen.{a,a,b,a,a,a,b,b,b,b,b,b,b,b}
hat 4 Buchstabenreihen.quelle
Dyalog APL, 22 Bytes
Probieren Sie es hier aus. Dies ist eine Funktion, die ein 2D-Array von Zeichen aufnimmt und
1
für gleitende und0
für nicht gleitende Instanzen zurückgibt . Der Algorithmus ähnelt den meisten anderen Antworten: Prüfen Sie, ob die Matrix und ihre Transponierung mehr als ein benachbartes Paar verschiedener Buchstaben enthält. Für die 4x3 EingangsmatrixDie Funktion kann aufgerufen werden als
was ergibt
1
.Erläuterung
quelle
JavaScript (ES6), 94 Byte
Alternative Methode gleicher Größe:
Dies kehrt
1
für eine wahrheitsgemäße Eingabe und0
für falsch zurück. Ich habe damit begonnen, bevor irgendwelche anderen Antworten veröffentlicht wurden. Ursprünglich habe ich auch versucht, das Array-Verständnis von ES7 zu verwenden, aber das Ergebnis war ungefähr 10 Zeichen länger als diese Methode.Versuch es:
Vorschläge willkommen!
quelle