Napisz program, który przetwarza graficzną reprezentację splątanego łańcucha ASCII i decyduje, czy można go rozplątać w prostej pętli. Plątanina jest reprezentowana za pomocą znaków -oraz |do reprezentowania poziomych i pionowych segmentów oraz +do reprezentowania narożników. Miejsca, w których ciąg przechodzi nad sobą, są reprezentowane w następujący sposób:

            |                           |   
         -------                     ---|---
            |                           |   
(Horizontal segment on top)   (Vertical segment on top)

Końce sznurka są połączone ze sobą; nie ma luźnych końców.

Jeśli twój program zdecyduje, że łańcucha nie można rozplątać w prostej pętli, powinien wypisać słowo KNOT. W przeciwnym razie powinien wypisać słowo NOT.

Jest to wyzwanie dla golfa , więc wygra najkrótsza ważna odpowiedź (mierzona w bajtach kodu źródłowego).

Granice

Wejście ASCII będzie się składać z maksymalnie 25 wierszy po 80 znaków. Możesz założyć, że wszystkie linie są wypełnione spacjami na tej samej długości.

Przykłady

Wejście:

+-------+    +-------+    
|       |    |       |    
|   +---|----+   +-------+
|   |   |        |   |   |
+-------|------------|---+
    |   |        |   |    
    +---+        +---+    

Wynik:

KNOT

Wejście:

+----------+         
|          |         
|    +--------------+
|    |     |        |
|    |   +-|----+   |
|    |   | |    |   |
|    +-----+    |   |
|        |      |   |
|        +------|---+
|               |    
+---------------+    

Wynik:

NOT

Bibliografia

• http://en.wikipedia.org/wiki/Knot_theory
• http://en.wikipedia.org/wiki/Reidemeister_move
• http://en.wikipedia.org/wiki/Unknotting_problem

Python 3, 457 316 306 bajtów

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

Co?

Program najpierw przekształca węzeł w prostokątny schemat, który ma następujące ograniczenia:

1. Żadne dwa pionowe lub poziome segmenty nie leżą na tej samej linii.
2. Żaden segment pionowy nie przecina segmentu poziomego.

Na przykład pierwszy przypadek testowy jest konwertowany na następujący prostokątny schemat:

+-----------+            
|           |            
|           | +-------+  
|           | |       |  
| +-------+ | |       |  
| |       | | |       |  
| |     +---+ |       |  
| |     | |   |       |  
| |     | +---+       |  
| |     |             |  
| |     |       +-------+
| |     |       |     | |
+-----+ |       |     | |
  |   | |       |     | |
  | +---+       |     | |
  | | |         |     | |
  | | +-------------+ | |
  | |           |   | | |
  | |           | +---+ |
  | |           | | |   |
  | |           | | +---+
  | |           | |      
  +-+           | |      
                | |      
                +-+      

które jednoznacznie reprezentujemy przez ciąg współrzędnych y segmentów pionowych od prawej do lewej:

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

Następnie szuka uproszczeń na prostokątnym schemacie, jak opisano w Iwan Dynnikow, „Prezentacje łuków linków. Monotoniczne uproszczenie ”, 2004 . Dynnikow udowodnił, że z dowolnego prostokąta schematu unknot jest sekwencja upraszczających ruchów, która kończy się na trywialnym schemacie. W skrócie, dozwolone ruchy obejmują:

1. Cyklicznie przepuszczając pionowe (lub poziome) segmenty;
2. Zamiana kolejnych pionowych (lub poziomych) segmentów przy określonych ograniczeniach konfiguracji.
3. Zastąpienie trzech sąsiadujących wierzchołków leżących w samym rogu diagramu jednym wierzchołkiem.

Zobacz papier do zdjęć. To nie jest oczywiste twierdzenie; nie ma zastosowania, jeśli, powiedzmy, zastosowane zostaną ruchy Reidemeister, które nie zwiększają liczby przejść. Ale w przypadku powyższych rodzajów uproszczeń okazuje się to prawdą.

(Upraszczamy implementację, dopuszczając tylko segmenty pionowe, ale także umożliwiając transpozycję całego węzła w celu zamiany poziomej na pionową.)

Próbny

$ 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