Как можно участвовать в ICFPC (2016)

«Рядом с этой сокровищницей мысли, — неторопливо думал Васисуалий, — делаешься чище, как-то духовно растешь»

В этом году мы с товарищами (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 работает с целочисленными координатами (видимо, в основном заточен на экранную графику) размером Int64. А у нас рациональные и просто целые очень большие числа. Так что при попытке засунуть в clipper одну из первых тривиальных задач сразу получили: Literal 1267650600228229401496703205376 is out of the Int64 range -9223372036854775808..9223372036854775807. Так что реализацию сложных алгоритмов отложили на потом (по факту объединение многоугольников у нас в итоге и не использовалось). Minoru взялся писать разрезание многоугольника прямой на два (это в любом случае бы понадобилось для складывания, а в clipper этого нет).
Дальше Minoru, Fornever и hagane начали обсуждать вариант с разворачиванием скелета. Я в эту идею особо не вникал, т.к. думал над представлением «фигуры» в процессе её сворачивания и реализацией «сворачивалки» в виде State ЧтоТо ().
К вечеру пятницы у меня был «солвер», который брал многоугольник и один раз сворачивал квадрат вдоль каждой грани этого многоугольника. И рисовал в svg что получилось. То есть он теоретически мог уже решать часть задач. Но при этом он принимал данные не в том виде, и выводил не в том. При этом там было ещё куча неуловленных багов.
Fornever к этому времени перегенерировал все иллюстрации к задачам, устранив баг в рендерилке.

В субботу

с утра я стал было дописывать алгоритм сворачивания выпуклых полигонов, но наткнулся на баги в методе разрезания многоугольника (где-то какое-то деление на ноль). Попытался разобраться в коде этого метода и не смог. Т.к. Minoru сильно в другом часовом поясе, я решился переписать этот код. Стал гуглить как это делается правильно, и нашёл зубодробительные алгоритмы разрезания произвольных многоугольников. После долгих попыток в них разобраться я внезапно понял, что нам нужно разрезать только выпуклые многоугольники (т.к. многоугольники, на которые бумагу могут разделить складки оригами, могут быть только выпуклыми), и быстро написал сравнительно простой метод разрезания выпуклых многоугольников.
Потом я стал писать форматирование решения в соответствии с форматом, прниимаемым сервером. В это время Fornever с Hagene что-то писали на тему «разворачивания скелетов». Hagane ещё и постил задачи для других участников, придуманные «вручную». Потом, чтобы не тратить клетчатую бумагу, Hagane c Fornever стали писать генератор случайных задач.
grouzen предложил написать графическое интерактивное приложение для разворачивания фигур вручную, но до реализации этой идеи как-то ни у кого не дошли руки.
К вечеру субботы у меня был солвер, который решал некоторую часть задач, и я его пачками натравливал на избранные простые задачи. На многих задачах при этом проявлялся баг в геометрических алгоритмах. Тут же написалась решалка тривиальных задач (которые просто квадрат без складываний). Ещё я написал вариант солвера, который складывает вместо требуемой фигуры её выпуклую оболочку — это, очевидно, даёт приближённые решения, но лучше чем ничего.
Потом оказалось, что у нас имеется три реализации геометрии — Minoru и моя на Haskell, Hagane на Racket и Fornever на F#; и две реализации форматирования вывода, обе на Haskell — моя и Hagane, отличающиеся по-моему только названиями функций. На этом месте я взвыл в чатик — мол, нет на нас ПМ-а или хотя бы тимлида.
До позднего вечера я искал баги в реализации геометрии, Fornever с Hagane писали генератор задач, а Minoru писал разворачивание скелетов.
Потом Hagane решил взять на себя функции лида и отправил меня спать. Правда, совсем перед тем как лечь, я нашёл баг в одной строчке (опечатка при копипасте) в реализации разрезания многоугольника, и поправил его, отчего все «волшебные» баги исчезли.

В воскресенье

с утра у меня образовалось несколько идей:

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

Я нарешал скриптом с исправленным солвером пару сотен простых задач и стал реализовывать перечисленные идеи. В итоге где-то к середине дня я реализовал перенос и для самых простых случаев поворот, доделал сворачивание выпуклых фигур, и оставалось только время от времени запускать скачивалку и решалку (ту, которая складывает выпуклую оболочку для всего подряд). Ещё я оставшееся время пробовал всякие улучшения и оптимизации.
В частности, в какой-то момент я вдруг решил попробовать сделать хоть какой-нибудь вариант генетического алгоритма для решения сложных задач. Для этого нужно иметь функцию оценки, а она в данном случае определяется через площади многоугольников. Какое-то время я боролся с функцией нахождения площади из clipper, но то ли я его не так готовил, то ли есть баги в биндингах, то ли в самом clipper — результаты оценки получались настолько неадекватными, что я на это плюнул. Писать собственный расчёт площади времени не осталось.
У моего солвера оставалась существенная проблема: он часто генерировал решения размером в десятки или сотни килобайт, при ограничении в 5000 байт. Вечером стали думать, как уменьшить размер решений. В итоге сделал:

• если многоугольник не выпуклый и мы всё равно будем делать приблизительное решение — округлить входные координаты до 10-12 знаков после запятой (уменьшает размер дробей на выходе);
• складывать не по всем подряд рёбрам многоугольника, а сначала только по чётным, потом только по нечётным. Не очень понимаю почему, но на некоторых задачах это помогло существенно.

Вечером Minoru стал пытаться решать сложную задачу номер 101. Там нужно было сложить классического журавлика, и он его стал складывать. Из бумаги. С целью потом перевести эти складки в цифры. Правда, в итоге безуспешно. Но эту задачу вообще решила только одна команда.
Ночью я передал Minoru скрипты для скачивания задач, решения и заливки решений, оставил его их запускать в оставшееся время контеста, и ушёл спать. Leaderboard к этому времени как раз заморозили.

В итоге

к моменту заморозки leaderboard мы оказались на 44м месте (из 293 команд всего, получивших ненулевое количество очков 201). Что есть необычно высокий результат по сравнению с нашими прошлыми попытками.
По моему личному впечатлению, в этот раз задача была заметно проще, чем в предыдущие (я не удивлюсь, если увижу разочарованные отзывы об этом icfpc от «аксакалов» — мол, слишком легко). Но, возможно, это такой perception bias из-за того, что в классической аналитической геометрии с линейной алгеброй худо-бедно разбираюсь, а во всяких AI почти никак не разбираюсь.
У нас, как всегда, были проблемы с организацией и коммуникацией (каждый писал что-то своё, иногда дублируя работу). По-моему, если бы мы физически находились в одном месте, результаты могли бы быть сильно лучше, хотя бы за счёт взаимной мотивации (говорят, психологически сложнее отлынивать, когда видишь как человек за соседним компом сосредоточенно пишет код) :) Как и в прошлые разы, были проблемы из-за того, что члены команды имели сильно разный опыт работы с выбранным языком.
Надеюсь, в следующем году мы как-нибудь сможем смягчить эти проблемы, и результат будет ещё лучше.