“KNOT” ou “NOT”?

144

Ecrivez un programme qui traite une représentation artistique ASCII d'une chaîne enchevêtrée et décide si elle peut ou non être démêlée en une simple boucle. L'enchevêtrement est représenté à l'aide des caractères -et |représente les segments horizontaux et verticaux, ainsi que les +angles. Les endroits où la chaîne passe sur lui-même sont représentés comme suit:

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

Les extrémités de la chaîne sont connectées ensemble; il n'y a pas de bouts.

Si votre programme décide que la chaîne ne peut pas être démêlée en une simple boucle, il doit générer le mot KNOT. Sinon, il devrait sortir le mot NOT.

Ceci est un défi , donc la réponse la plus courte valide (mesurée en octets de code source) sera gagnante.

Limites

L'entrée ASCII comprendra jusqu'à 25 lignes de 80 caractères. Vous pouvez supposer que toutes les lignes sont complétées par des espaces de même longueur.

Exemples

Contribution:

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

Sortie:

KNOT

Contribution:

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

Sortie:

NOT

Références

ossifrage délirant
la source
36
+1 excellente question. Tenté de mettre une prime sur celui-ci pour encourager les gens à se lancer dans cette théorie du noeud.
Digital Trauma
2
Pouvons-nous supposer que c'est un nœud (peut-être le dénouement) ou peut-il s'agir d'un lien de> 1 composants connectés?
msh210
@ msh210 Oui, vous pouvez en déduire que c'est un nœud unique :-)
ossifrage délirant

Réponses:

94

Python 3, 457 316 306 octets

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

Hein?

Le programme convertit d'abord le nœud en diagramme rectangulaire, qui présente les restrictions suivantes:

  1. Deux segments verticaux ou horizontaux ne se trouvent pas sur la même ligne.
  2. Aucun segment vertical ne traverse un segment horizontal.

Par exemple, le premier cas de test est converti en diagramme rectangulaire suivant:

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

que nous représentons uniquement par la suite des coordonnées y des segments verticaux, de droite à gauche:

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

Il cherche ensuite des simplifications du diagramme rectangulaire décrites dans Ivan Dynnikov, «Présentations de liens en arc. Simplification monotone ”, 2004 . Dynnikov a prouvé que, quel que soit le diagramme rectangulaire du dénouement, il existe une séquence de mouvements simplifiants qui se terminent au diagramme trivial. En bref, les mouvements autorisés incluent:

  1. Permuter cycliquement les segments verticaux (ou horizontaux);
  2. Permutation de segments verticaux (ou horizontaux) consécutifs sous certaines contraintes de configuration.
  3. Remplacement de trois sommets adjacents situés dans le coin même du diagramme par un sommet.

Voir le papier pour les images. Ce n'est pas un théorème évident; cela ne tient pas si, par exemple, Reidemeister utilise des mouvements qui n'augmentent pas le nombre de passages à niveau. Mais pour les types particuliers de simplifications ci-dessus, cela s'avère être vrai.

(Nous simplifions la mise en œuvre en ne permutant que les segments verticaux, mais en permettant également de transposer tout le nœud pour un échange horizontal avec vertical.)

Démo

$ 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
la source
Wow, c'est excellent.
ossifrage délirant
3
Pourriez-vous poster une version non-golfée de votre code?
J. Antonio Perez
Aussi, quelle est la complexité temporelle de votre programme?
J. Antonio Perez
3
@ JorgePerez Je n'ai pas de version distincte non-golfée; la meilleure façon de comprendre le programme est de lire le document de Dynnikov que j'ai lié. La complexité est horriblement exponentielle. pour autant que je sache, l'existence d'un algorithme polynomial est toujours un problème ouvert.
Anders Kaseorg