"KNOTEN" oder "NICHT"?

144

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 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

zimperliches Ossifrage
quelle
36
+1 Gute Frage. Ich bin versucht, ein Kopfgeld auf dieses zu setzen, um die Leute zu ermutigen, in diese Knotentheorie einzusteigen.
Digital Trauma
2
Können wir davon ausgehen, dass es sich um einen Knoten handelt (möglicherweise um einen Knoten), oder kann es sich um eine Verknüpfung von> 1 verbundenen Komponenten handeln?
msh210
@ msh210 Ja, man kann davon ausgehen, dass es sich um einen einzelnen Knoten handelt :-)
zimperliches Ossifrage

Antworten:

94

Python 3, 457 316 306 Bytes

E=enumerate
V={'+'}
Q=[[(-j,i,k)for i,u in E(open(0))for j,v in E(u)for k in[{v}&V,'join'][u[j:j+2]=='|-']]]
while Q:
 a,b,c,d,*e=A=tuple(x//2for y,x in sorted((y,x)for x,y in E(Q.pop())));e or exit('NOT')
 if{A}-V:V|={A};Q+=[[c,d,a,b]+e,A,A[2:]+A[:2]][a<c<b<d:][c<a<d<b:]
 if b==d:Q=[[a,c]+e]
exit('KNOT')

Huh?

Das Programm konvertiert zunächst den Knoten in ein rechteckiges Diagramm, das die folgenden Einschränkungen aufweist:

  1. Keine zwei vertikalen oder horizontalen Segmente liegen auf derselben Linie.
  2. Kein vertikales Segment überquert ein horizontales Segment.

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:

(5,10, 1,9, 8,10, 9,12, 5,12, 1,4, 0,3, 2,4, 3,7, 6,8, 7,11, 2,11, 0,6)

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:

  1. Zyklisches Permutieren der vertikalen (oder horizontalen) Segmente;
  2. Vertauschen aufeinanderfolgender vertikaler (oder horizontaler) Segmente unter bestimmten Konfigurationseinschränkungen.
  3. Ersetzen Sie drei benachbarte Scheitelpunkte, die sich in der äußersten Ecke des Diagramms befinden, durch einen Scheitelpunkt.

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

$ python3 knot.py <<EOF
+-------+    +-------+    
|       |    |       |    
|   +---|----+   +-------+
|   |   |        |   |   |
+-------|------------|---+
    |   |        |   |    
    +---+        +---+    
EOF
KNOT
$ python3 knot.py <<EOF
+----------+         
|          |         
|    +--------------+
|    |     |        |
|    |   +-|----+   |
|    |   | |    |   |
|    +-----+    |   |
|        |      |   |
|        +------|---+
|               |    
+---------------+    
EOF
NOT
$ python3 knot.py <<EOF  # the Culprit
        +-----+  
        |     |  
+-----------+ |  
|       |   | |  
|   +-+ | +---|-+
|   | | | | | | |
| +-|-------+ | |
| | | | | |   | |
+-|-+ | | +---+ |
  |   | |       |
  +---|---------+
      | |        
      +-+        
EOF
NOT
$ python3 knot.py <<EOF  # Ochiai unknot
    +-----+    
    |     |    
  +-|---------+
  | |     |   |
  | | +-+ |   |
  | | | | |   |
+-|-|---|-|-+ |
| | | | | | | |
| | | +---|---+
| | |   | | |  
+-------+ | |  
  | |     | |  
  | +-------+  
  |       |    
  +-------+    
EOF
NOT
$ python3 knot.py <<EOF  # Ochiai unknot plus trefoil
    +-----+ +-----+
    |     | |     |
  +-|---------+   |
  | |     | | |   |
  | | +-+ | +---+ |
  | | | | |   | | |
+-|-|---|-|-+ +---+
| | | | | | |   |  
| | | +---|-----+  
| | |   | | |      
+-------+ | |      
  | |     | |      
  | +-------+      
  |       |        
  +-------+        
EOF
KNOT
$ python3 knot.py <<EOF  # Thistlethwaite unknot
      +---------+        
      |         |        
    +---+ +---------+    
    | | | |     |   |    
    | +-------+ |   |    
    |   | |   | |   |    
    |   | | +---+   |    
    |   | | | |     |    
    |   | +-------+ |    
    |   |   | |   | |    
    |   +-------+ | |    
    |       | | | | |    
+-----------+ | | | |    
|   |         | | | |    
| +-----------+ | | |    
| | |           | | |    
| | +-------------+ |    
| |             |   |    
| |             +-----+  
| |                 | |  
| |                 +---+
| |                   | |
+---------------------+ |
  |                     |
  +---------------------+
EOF
NOT
$ python3 knot.py <<EOF  # (−3,5,7)-pretzel knot
      +-------------+
      |             |
    +-|-----+       |
    | |     |       |
  +-|-+   +-------+ |
  | |     | |     | |
+-|-+   +---+   +---+
| |     | |     | |  
| |   +---+   +---+  
| |   | |     | |    
| | +---+   +---+    
| | | |     | |      
| +---+   +---+      
|   |     | |        
|   |   +---+        
|   |   | |          
|   | +---+          
|   | | |            
|   +---+            
|     |              
+-----+              
EOF
KNOT
$ python3 knot.py <<EOF  # Gordian unknot
+-------------+                 +-------------+
|             |                 |             |
| +---------+ |                 | +---------+ |
| |         | |                 | |         | |
| | +-------------+         +-------------+ | |
| | |       | |   |         |   | |       | | |
| | | +---------+ |         | +---------+ | | |
| | | |     | | | |         | | | |     | | | |
| +-------+ | +-------+ +-------+ | +-------+ |
|   | |   | |   | |   | |   | |   | |   | |   |
+-------+ | +-------+ | | +-------+ | +-------+
    | | | |     | | | | | | | |     | | | |    
    | +-------+ | | | | | | | | +-------+ |    
    |   | |   | | | | | | | | | |   | |   |    
    +-------+ | | | | | | | | | | +-------+    
        | | | | | | | | | | | | | | | |        
        | +-----+ | | | | | | +-----+ |        
        |   | |   | | | | | |   | |   |        
        +---------+ | | | | +---------+        
            | |     | | | |     | |            
          +---------+ | | +---------+          
          | | |       | |       | | |          
          | | +-----------------+ | |          
          | |         | |         | |          
          | +---------------------+ |          
          |           | |           |          
          +-----------+ +-----------+          
EOF
NOT
Anders Kaseorg
quelle
Wow, das ist exzellent.
Squeamish Ossifrage
3
Könnten Sie eine unbenutzte Version Ihres Codes posten?
J. Antonio Perez
Wie hoch ist die zeitliche Komplexität Ihres Programms?
J. Antonio Perez
3
@JorgePerez Ich habe keine separate ungolfed Version. Der beste Weg, das Programm zu verstehen, ist, Dynnikovs Artikel zu lesen, den ich verlinkt habe. Die Komplexität ist etwas schrecklich Exponentielles; Soweit ich weiß, ist es immer noch ein offenes Problem, ob ein polynomieller Zeitalgorithmus existiert.
Anders Kaseorg