В этом году мы с товарищами (ForNever, Minoru, Hagane, grouzen) опять взялись участвовать в ICFPC. Если кто не в курсе, что это такое — см мой предыдущий пост или серию постов товарища adept.
В этот раз для разнообразия мы не писали AI для игрушки. Организаторы были из Японии, и поэтому мы весь уик-енд… складывали оригами. Кто-то из кода, а кто-то нет.
Задача состояла в том, чтобы из квадратного «листа бумаги» складывать разные (плоские) фигуры. В качестве задачи даётся описание нужной фигуры, а решение — набор складок на квадрате и описание, какие вершины в какие переходят при складывании. Первая сотня фигур была предложена организаторами, а дальше задачи могли отправлять участники, и за отправку задач тоже давали очки.
При этом, на самом деле, это было «не настоящее оригами». Были допустимы решения, невозможные с бумагой — части листа могли проходить друг через друга при складывании. При отправке решений чужих задач можно было даже «рвать бумагу» (при отправке своих задач — нельзя). Момент про разрешено ли разрезание мы уточняли долго и сложно.
Контест в этот раз проходил с утра пятницы по вечер воскресенья в моём часовом поясе.

В пятницу

с утра я «по-быстрому» написал скачивалку задач с сервера и закачивалку решений (на python, просто потому что там было REST API, а у меня уже был опыт использования для этого питоньей библиотеки requests). Ещё я написал парсер предложенного формата задач и рендерилку, которая рисует фигуры из задач в виде svg (на Haskell). Сразу пригодился хаскельный модуль Data.Ratio. Дело в том, что в задачах использовались координаты в виде рациональных чисел, причём размеры числителя и знаменателя не были ограничены. Так что быстро образовалась строчка type Number = Ratio Integer.
Потом я посмотрел на результаты рендера и увидел, что первые семь задач тривиальные (там просто квадрат, сдвинутый или повёрнутый, но не сложенный), решения для них легко написать вручную. Решил и залил.
Потом мы начали думать над задачей (я уже писал, у меня всегда так — сначала код, потом думать).
Когда нет ограничения на разрезание бумаги, задача сводится к тому, чтобы разрезать квадрат на эн многоугольников и сложить из них нужную фигуру. Насколько я знаю, подобные темы широко и глубоко изучены, но я не знаком с конкретными работами и алгоритмами. (в университете был даже какой-то спецкурс по оригами, как разделу геометрии, но я на него не попал). Поэтому я долго и упорно думал в эту сторону, но ничего не придумал.
В чате довольно быстро образовалось несколько идей:

• Разрезать требуемую фигуру на треугольники и попытаться из таких треугольников сложить квадрат.
• Какой-нибудь вариант генетических алгоритмов: разрезаем квадрат как попало и складываем как попало, оцениваем скор в соответствии с правилами организаторов.
• Быстро придумался простой алгоритм для складывания любого достаточно маленького выпуклого многоугольника: пройти по всем его рёбрам и сложить бумагу вдоль них. Если останутся торчащие «хвосты», то опять пройти по рёбрам и подвернуть вдоль них.
• Кроме силуэта фигуры, в задачах приводился её «скелет» — набор всех рёбер в положении после складывания. При этом, правда, было указание, что это только подсказка, складывать в соответствии с этим скелетом не обязательно. Так вот, появилась идея брать этот скелет и пытаться разворачивать его до квадрата.

Товарищ grouzen произвёл обширные изыскания существующих научных работ на тему оригами и около, и обеспечил нас пейперами для чтения на всю неделю. К сожалению, применить их мы не смогли.
Потом начался как всегда разброд и шатание, каждый стал заниматься чем-то своим.
Я решил начать с написания какого-никакого «фреймворка» для дальнейшей работы — набора функций для разрезания многоугольников, объединения и т.п. Некоторые из геометрических алгоритмов тривиальны (отражение многоугольника относительно прямой), зато другие зубодробительны (объединение произвольных многоугольников). Для таких алгоритмов я стал гуглить существующие реализации, по возможности на Haskell (т.к. парсер задач уже был на Haskell). Нашёл только clipper. Это биндинги к одноимённой библиотеке на C++. Сразу обнаружилась особенность: Clipper работает с целочисленными координатами (видим