„KNOT” czy „NOT”?

144

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

piskliwy kostuch
źródło
36
+1 Świetne pytanie. Kusiło go, aby wynagrodzić go za to, aby zachęcić ludzi do wskoczenia w teorię węzłów.
Digital Trauma
2
Czy możemy założyć, że jest to węzeł (ewentualnie unknot), czy może to być link> 1 połączonych elementów?
msh210
@ msh210 Tak, możesz założyć, że to pojedynczy węzeł :-)
piskliwy ossifrage

Odpowiedzi:

94

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
Anders Kaseorg
źródło
Wow, to jest doskonałe.
piskliwy ossifrage
3
Czy mógłbyś opublikować nieoznaczoną wersję swojego kodu?
J. Antonio Perez,
Jaka jest złożoność czasowa twojego programu?
J. Antonio Perez,
3
@JorgePerez Nie mam osobnej wersji bez golfa; najlepszym sposobem na zrozumienie programu jest przeczytanie artykułu Dynnikowa, który połączyłem. Złożoność jest czymś strasznie wykładniczym; o ile wiem, czy istnieje algorytm wielomianu czasu, jest nadal otwartym problemem.
Anders Kaseorg,