«Рядом с этой сокровищницей мысли, — неторопливо думал Васисуалий, — делаешься чище, как-то духовно растешь»
В этом году мы с товарищами (ForNever, Minoru, Hagane, grouzen) опять взялись участвовать в ICFPC. Если кто не в курсе, что это такое — см мой предыдущий пост или серию постов товарища adept.
В этот раз для разнообразия мы не писали AI для игрушки. Организаторы были из Японии, и поэтому мы весь уик-енд... складывали оригами. Кто-то из кода, а кто-то нет.
Задача состояла в том, чтобы из квадратного «листа бумаги» складывать разные (плоские) фигуры. В качестве задачи даётся описание нужной фигуры, а решение — набор складок на квадрате и описание, какие вершины в какие переходят при складывании. Первая сотня фигур была предложена организаторами, а дальше задачи могли отправлять участники, и за отправку задач тоже давали очки.
При этом, на самом деле, это было «не настоящее оригами». Были допустимы решения, невозможные с бумагой — части листа могли проходить друг через друга при складывании. При отправке решений чужих задач можно было даже «рвать бумагу» (при отправке своих задач — нельзя). Момент про разрешено ли разрезание мы уточняли долго и сложно.
Контест в этот раз проходил с утра пятницы по вечер воскресенья в моём часовом поясе.
В пятницу
с утра я «по-быстрому» написал скачивалку задач с сервера и закачивалку решений (на python, просто потому что там было REST API, а у меня уже был опыт использования для этого питоньей библиотеки requests). Ещё я написал парсер предложенного формата задач и рендерилку, которая рисует фигуры из задач в виде svg (на Haskell). Сразу пригодился хаскельный модуль Data.Ratio. Дело в том, что в задачах использовались координаты в виде рациональных чисел, причём размеры числителя и знаменателя не были ограничены. Так что быстро образовалась строчка type Number = Ratio Integer.Потом я посмотрел на результаты рендера и увидел, что первые семь задач тривиальные (там просто квадрат, сдвинутый или повёрнутый, но не сложенный), решения для них легко написать вручную. Решил и залил.
Потом мы начали думать над задачей (я уже писал, у меня всегда так — сначала код, потом думать).
Когда нет ограничения на разрезание бумаги, задача сводится к тому, чтобы разрезать квадрат на эн многоугольников и сложить из них нужную фигуру. Насколько я знаю, подобные темы широко и глубоко изучены, но я не знаком с конкретными работами и алгоритмами. (в университете был даже какой-то спецкурс по оригами, как разделу геометрии, но я на него не попал). Поэтому я долго и упорно думал в эту сторону, но ничего не придумал.
В чате довольно быстро образовалось несколько идей:
- Разрезать требуемую фигуру на треугольники и попытаться из таких треугольников сложить квадрат.
- Какой-нибудь вариант генетических алгоритмов: разрезаем квадрат как попало и складываем как попало, оцениваем скор в соответствии с правилами организаторов.
- Быстро придумался простой алгоритм для складывания любого достаточно маленького выпуклого многоугольника: пройти по всем его рёбрам и сложить бумагу вдоль них. Если останутся торчащие «хвосты», то опять пройти по рёбрам и подвернуть вдоль них.
- Кроме силуэта фигуры, в задачах приводился её «скелет» — набор всех рёбер в положении после складывания. При этом, правда, было указание, что это только подсказка, складывать в соответствии с этим скелетом не обязательно. Так вот, появилась идея брать этот скелет и пытаться разворачивать его до квадрата.
Потом начался как всегда разброд и шатание, каждый стал заниматься чем-то своим.
Я решил начать с написания какого-никакого «фреймворка» для дальнейшей работы — набора функций для разрезания многоугольников, объединения и т.п. Некоторые из геометрических алгоритмов тривиальны (отражение многоугольника относительно прямой), зато другие зубодробительны (объединение произвольных многоугольников). Для таких алгоритмов я стал гуглить существующие реализации, по возможности на 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 скрипты для скачивания задач, решения и заливки решений, оставил его их запускать в оставшееся время контеста, и ушёл спать. Leaderboard к этому времени как раз заморозили.
В итоге
к моменту заморозки leaderboard мы оказались на 44м месте (из 293 команд всего, получивших ненулевое количество очков 201). Что есть необычно высокий результат по сравнению с нашими прошлыми попытками.По моему личному впечатлению, в этот раз задача была заметно проще, чем в предыдущие (я не удивлюсь, если увижу разочарованные отзывы об этом icfpc от «аксакалов» — мол, слишком легко). Но, возможно, это такой perception bias из-за того, что в классической аналитической геометрии с линейной алгеброй худо-бедно разбираюсь, а во всяких AI почти никак не разбираюсь.
У нас, как всегда, были проблемы с организацией и коммуникацией (каждый писал что-то своё, иногда дублируя работу). По-моему, если бы мы физически находились в одном месте, результаты могли бы быть сильно лучше, хотя бы за счёт взаимной мотивации (говорят, психологически сложнее отлынивать, когда видишь как человек за соседним компом сосредоточенно пишет код) :) Как и в прошлые разы, были проблемы из-за того, что члены команды имели сильно разный опыт работы с выбранным языком.
Надеюсь, в следующем году мы как-нибудь сможем смягчить эти проблемы, и результат будет ещё лучше.
