«УЗЕЛ» или «НЕ»?

144

Напишите программу, которая обрабатывает художественное представление ASCII запутанной строки и решает, можно ли ее распутать в простой цикл. Клубок представлен с помощью символов -и |для представления горизонтальных и вертикальных сегментов, а также +для представления углов. Места, где строка проходит над собой, представлены следующим образом:

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

Концы нити соединены вместе; нет свободных концов.

Если ваша программа решает, что строку нельзя распутать в простой цикл, она должна вывести слово KNOT. В противном случае следует вывести слово NOT.

Это вызов , поэтому победит самый короткий действительный ответ (измеряемый в байтах исходного кода).

рамки

Вход ASCII будет состоять из 25 строк по 80 символов. Вы можете предположить, что все строки дополнены пробелами одинаковой длины.

Примеры

Входные данные:

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

Выход:

KNOT

Входные данные:

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

Выход:

NOT

Рекомендации

брезгливый оссифраж
источник
36
+1 Отличный вопрос. Соблазниться наложить на это награду, чтобы побудить людей перейти к этой теории узлов.
Цифровая травма
2
Можем ли мы предположить, что это узел (возможно, узел) или это может быть ссылка> 1 подключенных компонентов?
msh210
@ msh210 Да, вы можете предположить, что это один узел :-)
брезгливый оссифраж

Ответы:

94

Python 3, 457 316 306 байт

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

А?

Программа сначала преобразует узел в прямоугольную диаграмму, которая имеет следующие ограничения:

  1. Никакие два вертикальных или горизонтальных сегмента не лежат на одной линии.
  2. Ни один вертикальный сегмент не пересекает горизонтальный сегмент.

Например, первый тестовый пример преобразуется в следующую прямоугольную диаграмму:

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

который мы однозначно представляем последовательностью y координат вертикальных сегментов справа налево:

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

Затем он ищет упрощения прямоугольной диаграммы, как описано у Ивана Дынникова, «Арк-презентации ссылок. Монотонное упрощение », 2004 . Дынников доказал, что на любой прямоугольной диаграмме узла есть последовательность упрощающих ходов, которая заканчивается на тривиальной диаграмме. Вкратце, разрешенные ходы включают в себя:

  1. Циклически переставляя вертикальные (или горизонтальные) сегменты;
  2. Обмен последовательных вертикальных (или горизонтальных) сегментов при определенных ограничениях конфигурации.
  3. Замена трех смежных вершин, лежащих в самом углу диаграммы, одной вершиной.

Смотрите бумагу для фотографий. Это не очевидная теорема; он не действует, если, скажем, вместо этого используются ходы Рейдемейстера, которые не увеличивают количество пересечений. Но для конкретных видов упрощений выше, это оказывается правдой.

(Мы упрощаем реализацию, переставляя только вертикальные сегменты, но также позволяя транспонировать весь узел для взаимного обмена по горизонтали с вертикалью.)

демонстрация

$ 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
Андерс Касеорг
источник
Вау, это отлично.
брезгливое оссифраж
3
Не могли бы вы опубликовать версию вашего кода, не принадлежащую к гольфу?
Х. Антонио Перес
Кроме того, какова временная сложность вашей программы?
Х. Антонио Перес
3
@JorgePerez У меня нет отдельной неголевой версии; лучший способ понять программу - прочитать статью Дынникова, которую я связал. Сложность - это нечто ужасно экспоненциальное; насколько я знаю, существует ли алгоритм полиномиального времени, все еще остается открытой проблемой.
Андерс Касеорг