Напишите программу, которая обрабатывает художественное представление ASCII запутанной строки и решает, можно ли ее распутать в простой цикл. Клубок представлен с помощью символов -
и |
для представления горизонтальных и вертикальных сегментов, а также +
для представления углов. Места, где строка проходит над собой, представлены следующим образом:
| |
------- ---|---
| |
(Horizontal segment on top) (Vertical segment on top)
Концы нити соединены вместе; нет свободных концов.
Если ваша программа решает, что строку нельзя распутать в простой цикл, она должна вывести слово KNOT
. В противном случае следует вывести слово NOT
.
Это вызов кода для гольфа , поэтому победит самый короткий действительный ответ (измеряемый в байтах исходного кода).
рамки
Вход ASCII будет состоять из 25 строк по 80 символов. Вы можете предположить, что все строки дополнены пробелами одинаковой длины.
Примеры
Входные данные:
+-------+ +-------+
| | | |
| +---|----+ +-------+
| | | | | |
+-------|------------|---+
| | | |
+---+ +---+
Выход:
KNOT
Входные данные:
+----------+
| |
| +--------------+
| | | |
| | +-|----+ |
| | | | | |
| +-----+ | |
| | | |
| +------|---+
| |
+---------------+
Выход:
NOT
Рекомендации
источник
Ответы:
Python 3,
457316306 байтА?
Программа сначала преобразует узел в прямоугольную диаграмму, которая имеет следующие ограничения:
Например, первый тестовый пример преобразуется в следующую прямоугольную диаграмму:
который мы однозначно представляем последовательностью y координат вертикальных сегментов справа налево:
Затем он ищет упрощения прямоугольной диаграммы, как описано у Ивана Дынникова, «Арк-презентации ссылок. Монотонное упрощение », 2004 . Дынников доказал, что на любой прямоугольной диаграмме узла есть последовательность упрощающих ходов, которая заканчивается на тривиальной диаграмме. Вкратце, разрешенные ходы включают в себя:
Смотрите бумагу для фотографий. Это не очевидная теорема; он не действует, если, скажем, вместо этого используются ходы Рейдемейстера, которые не увеличивают количество пересечений. Но для конкретных видов упрощений выше, это оказывается правдой.
(Мы упрощаем реализацию, переставляя только вертикальные сегменты, но также позволяя транспонировать весь узел для взаимного обмена по горизонтали с вертикалью.)
демонстрация
источник