144
\$\begingroup\$

Write a program that processes an ASCII art representation of a tangled string and decides whether or not it can be untangled into a simple loop. The tangle is represented using the characters - and | to represent horizontal and vertical segments, and + to represent corners. Places where the string passes over itself are represented as follows:

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

The ends of the string are connected together; there are no loose ends.

If your program decides that the string cannot be untangled into a simple loop, it should output the word KNOT. Otherwise, it should output the word NOT.

This is a challenge, so the shortest valid answer (measured in bytes of source code) will win.

Limits

The ASCII input will consist of up to 25 lines of 80 characters. You may assume that all the lines are padded with spaces to the same length.

Examples

Input:

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

Output:

KNOT

Input:

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

Output:

NOT

References

\$\endgroup\$
  • 36
    \$\begingroup\$ +1 Great question. Tempted to put a bounty on this one to encourage folks to jump into that knot theory. \$\endgroup\$ – Digital Trauma Jun 6 '14 at 16:50
  • 2
    \$\begingroup\$ Can we assume it's a knot (possibly the unknot) or can it be a link of >1 connected components? \$\endgroup\$ – msh210 May 3 '16 at 7:03
  • \$\begingroup\$ @msh210 Yes, you can assume it's a single knot :-) \$\endgroup\$ – squeamish ossifrage May 3 '16 at 20:50
94
+650
\$\begingroup\$

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?

The program first converts the knot to a rectangular diagram, which has the following restrictions:

  1. No two vertical or horizontal segments lie on the same line.
  2. No vertical segment crosses over a horizontal segment.

For example, the first test case is converted to the following rectangular diagram:

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

which we uniquely represent by the sequence of y coordinates of the vertical segments, from right to left:

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

It then searches for simplifications of the rectangular diagram as described in Ivan Dynnikov, “Arc-presentations of links. Monotonic simplification”, 2004. Dynnikov proved that from any rectangular diagram of the unknot, there is a sequence of simplifying moves that ends at the trivial diagram. Briefly, the allowed moves include:

  1. Cyclically permuting the vertical (or horizontal) segments;
  2. Swapping consecutive vertical (or horizontal) segments under certain configuration constraints.
  3. Replacing three adjacent vertices that lie in the very corner of the diagram with one vertex.

See the paper for pictures. This is not an obvious theorem; it does not hold if, say, Reidemeister moves that do not increase the number of crossings are used instead. But for the particular kinds of simplifications above, it turns out to be true.

(We simplify the implementation by only permuting vertical segments, but also allowing the entire knot to be transposed to interchange horizontal with vertical.)

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
\$\endgroup\$
  • \$\begingroup\$ Wow, this is excellent. \$\endgroup\$ – squeamish ossifrage May 3 '16 at 21:21
  • 3
    \$\begingroup\$ Could you post an ungolfed version of your code? \$\endgroup\$ – J. Antonio Perez Dec 6 '16 at 23:00
  • \$\begingroup\$ Also, what's the time complexity of your program? \$\endgroup\$ – J. Antonio Perez Dec 6 '16 at 23:00
  • 3
    \$\begingroup\$ @JorgePerez I don’t have a separate ungolfed version; the best way to understand the program is to read Dynnikov’s paper that I linked. The complexity is something horribly exponential; as far as I know, whether a polynomial time algorithm exists is still an open problem. \$\endgroup\$ – Anders Kaseorg Dec 7 '16 at 23:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.