Schreiben Sie ein Programm, das eine ASCII-Grafikdarstellung einer verwickelten Zeichenfolge verarbeitet und entscheidet, ob sie in einer einfachen Schleife entwirrt werden kann. Das Gewirr wird mithilfe der Zeichen -
und |
zur Darstellung horizontaler und vertikaler Segmente sowie +
zur Darstellung von Ecken dargestellt. Stellen, an denen die Zeichenfolge über sich selbst verläuft, werden wie folgt dargestellt:
| |
------- ---|---
| |
(Horizontal segment on top) (Vertical segment on top)
Die Enden der Schnur sind miteinander verbunden; Es gibt keine losen Enden.
Wenn Ihr Programm feststellt, dass der String nicht in eine einfache Schleife zerlegt werden kann, sollte es das Wort ausgeben KNOT
. Andernfalls sollte das Wort ausgegeben werden NOT
.
Dies ist eine Code-Golf- Herausforderung, daher gewinnt die kürzeste gültige Antwort (gemessen in Byte Quellcode).
Grenzen
Die ASCII-Eingabe besteht aus bis zu 25 Zeilen mit 80 Zeichen. Sie können davon ausgehen, dass alle Zeilen mit Leerzeichen gleicher Länge aufgefüllt sind.
Beispiele
Eingang:
+-------+ +-------+
| | | |
| +---|----+ +-------+
| | | | | |
+-------|------------|---+
| | | |
+---+ +---+
Ausgabe:
KNOT
Eingang:
+----------+
| |
| +--------------+
| | | |
| | +-|----+ |
| | | | | |
| +-----+ | |
| | | |
| +------|---+
| |
+---------------+
Ausgabe:
NOT
Verweise
quelle
Antworten:
Python 3,
457316306 BytesHuh?
Das Programm konvertiert zunächst den Knoten in ein rechteckiges Diagramm, das die folgenden Einschränkungen aufweist:
Beispielsweise wird der erste Testfall in das folgende rechteckige Diagramm konvertiert:
was wir durch die Abfolge der y-Koordinaten der vertikalen Segmente von rechts nach links eindeutig darstellen:
Anschließend wird nach Vereinfachungen des rechteckigen Diagramms gesucht, wie in Ivan Dynnikov, „Bogenpräsentationen von Links. Monotone Vereinfachung “, 2004 . Dynnikov hat bewiesen, dass aus jedem rechteckigen Diagramm des Unknotens eine Folge von vereinfachenden Zügen hervorgeht, die am trivialen Diagramm endet. Kurz gesagt umfassen die erlaubten Züge:
Siehe das Papier für Bilder. Dies ist kein offensichtlicher Satz; es gilt nicht, wenn stattdessen beispielsweise Reidemeister-Züge verwendet werden, die die Anzahl der Überfahrten nicht erhöhen. Aber für die oben genannten Vereinfachungen hat sich herausgestellt, dass dies zutrifft.
(Wir vereinfachen die Implementierung, indem wir nur vertikale Segmente permutieren, aber auch zulassen, dass der gesamte Knoten so transponiert wird, dass er horizontal mit vertikal wechselt.)
Demo
quelle