"NUDO" o "NO"?

144

Escriba un programa que procese una representación artística ASCII de una cadena enredada y decida si se puede desenredar o no en un bucle simple. El enredo se representa usando los caracteres -y |para representar segmentos horizontales y verticales, y +para representar esquinas. Los lugares donde la cadena pasa sobre sí misma se representan de la siguiente manera:

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

Los extremos de la cuerda están conectados entre sí; No hay cabos sueltos.

Si su programa decide que la cadena no se puede desenredar en un bucle simple, debería generar la palabra KNOT. De lo contrario, debería generar la palabra NOT.

Este es un desafío de código de golf , por lo que la respuesta válida más corta (medida en bytes del código fuente) ganará.

Límites

La entrada ASCII constará de hasta 25 líneas de 80 caracteres. Puede suponer que todas las líneas están rellenadas con espacios de la misma longitud.

Ejemplos

Entrada:

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

Salida:

KNOT

Entrada:

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

Salida:

NOT

Referencias

code-golf ascii-art decision-problem knot-theory ossifrage aprensivo
fuente
36
+1 Gran pregunta. Tentado a poner una recompensa por esto para alentar a la gente a saltar a esa teoría del nudo.
Trauma digital
2
¿Podemos suponer que es un nudo (posiblemente el nudo) o puede ser un enlace de> 1 componentes conectados?
msh210
@ msh210 Sí, se puede asumir que es un solo nudo :-)
quebrantahuesos aprensivos

Respuestas:

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

¿Eh?

El programa primero convierte el nudo en un diagrama rectangular, que tiene las siguientes restricciones:

  1. No hay dos segmentos verticales u horizontales en la misma línea.
  2. Ningún segmento vertical cruza sobre un segmento horizontal.

Por ejemplo, el primer caso de prueba se convierte al siguiente diagrama rectangular:

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

que representamos únicamente por la secuencia de coordenadas y de los segmentos verticales, de derecha a izquierda:

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

Luego busca simplificaciones del diagrama rectangular como se describe en Ivan Dynnikov, “Presentaciones en arco de enlaces. Simplificación monotónica ”, 2004 . Dynnikov demostró que, desde cualquier diagrama rectangular del nudo, hay una secuencia de movimientos simplificadores que termina en el diagrama trivial. Brevemente, los movimientos permitidos incluyen:

  1. Permutando cíclicamente los segmentos verticales (u horizontales);
  2. Intercambiando segmentos verticales (u horizontales) consecutivos bajo ciertas restricciones de configuración.
  3. Reemplazar tres vértices adyacentes que se encuentran en la esquina del diagrama con un vértice.

Vea el periódico para fotos. Este no es un teorema obvio; no se mantiene si, por ejemplo, se utilizan movimientos Reidemeister que no aumentan el número de cruces. Pero para los tipos particulares de simplificaciones anteriores, resulta ser cierto.

(Simplificamos la implementación solo permutando segmentos verticales, pero también permitiendo que todo el nudo se transponga para intercambiar horizontalmente con vertical).

Manifestación

$ 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
fuente
Wow, esto es excelente.
aprensivo ossifrage
3
¿Podría publicar una versión no codificada de su código?
J. Antonio Perez
Además, ¿cuál es la complejidad temporal de su programa?
J. Antonio Perez
3
@JorgePerez No tengo una versión separada sin golf; La mejor manera de entender el programa es leer el artículo de Dynnikov que he vinculado. La complejidad es algo terriblemente exponencial; Hasta donde yo sé, si existe un algoritmo de tiempo polinómico sigue siendo un problema abierto.
Anders Kaseorg