Any sufficiently complicated ICFP Contest submission contains an ad-hoc, informally specified, bug-ridden, slow implementation of half of a CSP-solver.
TLDR;
Предчувствия не обманули.
Сказать, что задача была замечательной, — это не сказать вообще ничего.
Никаких лабиринтов и классических компьютерных игр, правда и никаких WAM-машин тоже.
Итак. Что мы знаем о Стране Восходящего Солнца? Самураи. Традиции. Сакура. Ортодоксальная столярка. Дроно-гейши, способные гнуть реальность через 4-ое измерение. Древнейшее искусство Оригами...
Пятница
Прочитав задание я лично сразу понял, что дело пахнет керосином.Во-первых, столько рациональной геометрии нам за три дня не осилить даже и в лучшие годы.
А во-вторых, чёрт его знает, чем все эти simple valley fold'ы отличаются друг от друга, почему некоторые из них impossible, и зачем нужны дроно-гейшы, работающие в четвёром измерении. Задание на отрез отказывалось укладываться в голове.
Поняв, что ничего не понимаю, я решил заняться интеграцией: база данных для проблем и решений, взаимодействие с орговским сервером, сохранение лидерборда — вот это вот всё. Базу для пущего развлечения развернул на Raspberry Pi Zero, для миграций использовал liquibase, скрипты на bash'е... Ну и как-то оно постепенно завертелось. Как водится, на интеграцию был убит весь день. Правда в этот раз оно-таки выстрелило ближе к вечеру воскресенья.
Лёха разрушительной рефлексии не поддался и сразу же увлёкся визуализатором задач и решений на python'е, на что и ухлопал весь день. Судя по git log'у проблем там тоже было немало.
Первый день для меня закончился беглым чтением каких-то статей и даже книг про математику оригами. Количество теории в этой области превосходило всякие разумные рамки. Аксиомы Huzita-Hatori, связь с системами полиномиальных уравнений, физически реализуемые и нереализуемые складки и их обобщения.
Постепенно у меня стала зреть мысль, что нужно идти другим путём...
Суббота
Постоянных читателей моего блога не удивит тот факт, что утром я проснулся с чётким пониманием того, как следует решать задачу, а именно: искать замощение единичного квадрата предложенными в силуэте полигонами, удовлетворяющее ограничениям на valid submission. С этого момента теория стала развиваться с бешеной скоростью.
Очевидно, что площадь всех отобранных полигонов с учётом их кратности должна суммироваться в единицу.
Внешний периметр, очевидно, должен суммироваться к 4, а периметр каждой из сторон — к 1.
Стороны с иррациональной длиной не могут участвовать в периметре.
Для замощения достаточно использовать только выпуклые полигоны — доказательство оставляю в качестве лёгкого упражнения для читателя, — что здорово упрощает геометрические изыскания, но имеет свои скрытые пока в мутной воде грабли.
Кроме того, должны выполняться требования спека к решению: отсутствие пересечений внутренностей полигонов на исходнике, пересечение ребёр только в вершинах, 5000 байт на кодирование решения итд.
Таким образом наклёвывался поиск в дереве (ok, в DAG'е), где узлом является частично заполненный полигонами единичный квадрат.
Корень дерева — квадрат вообще без полигонов.
Первый слой дерева — квадраты, в которых один из полигонов как-то уложен в угол.
Последующие слои — узлы, где к уже уложенным полигонам пристроены вплотную новые по всем правилам спецификации.
И дальше только борьба с симметриями, тупиковыми ветвями и мб поиск хороших эвристик. Easy, right? Но мы пошли другим путём...
Поскольку недавно прочитана AIMA-book, в голове срабатывает pattern-matching на слово CSP. Т.к. про CSP я знаю пока только теоретически, то обращаюсь за советом к Лёхе. Тот вздыхает, смотрит на меня с экзистенциальной грустью в глазах и говорит: "Ну, возьми minizinc", — и отправляется ковыряться дальше со своим питоном. Дело там, видимо, идёт не очень, т.к. в репозитории начинают появляться какие-то статьи, копирайты чужого кода и прочие полезные для решения задач вещи. Впрочем, появляются и какие-то решения для отдельных проблем, очевидно, добытые врукопашную.
На minizinc я убиваю весь день.
В чём-то оно выглядит перспективно и иногда даже может мне сказать, сколько нужно и каких полигонов взять для решения задачи. Но выразить все геометрические ограничения над полем рациональных чисел на языке уравнений практически нереально.
А при нехватке уравнений эта система имеет слишком много симметрий...
Воскресенье
В воскресенье становится ясно, что мы продолжаем пребывать у разбитого корыта. Солвера нет.Закапываем minizinc, и я сажусь за C++ писать "точный" солвер, контуры которого более или менее понятны (pun is not intended).
Лёха занимается "неточным" солвером на питоне. С помощью какой-то оптимизации он подбирает четырёхугольник с рациональными сторонами, который покрывает заданный силуэт, а дальше ищет простую последовательность fold'ов, приводящую единичный квадрат к этому четырёхугольнику.
К шести вечера становится понятно, что точного солвера у нас не будет. Зато неточный выбирается из квасов и начинает активно дробить числа. Я переключаюсь из dev в ops и гоняю интеграцию.
Пайплайн работает как часы, ведётся строжайший учёт. Задача либо решается, либо отправляется к Лёхе в R&D отдел на исследование. Правила для valid submission на самом деле довольно тонкие, поэтому сбоев много. Но всё равно задачи решаются сотнями, пусть мы и рубим мало очков, применяя неточный солвер. Лёха периодически выкатывает новые версии солвера. Интеграция позволяет перерешать только проблемные кейсы. Паровоз летит вперёд.
Наш чатик забит содержательными сообщениями типа
4561 3229 4557 921 949 908 924 4551 2967 2760 3195 5173 3273 5141 2197 1777 5150 947 3774 957 942 987 3103 986 5238 5245 3766 3817 3455 2033 985 4558 2716 4552 5642 5810 5812 5393 3190и картинками вроде таких
К вечеру мы прорешиваем все задачи, кроме тех, которые вообще нельзя решить нашей технологией.
Промежуточные итоги
Компетишн, мы, конечно, зафейлили. Точного солвера не запилили. Зато, как это ни смешно, заняли исторически самое высокое (72-ое) место за всю историю участия в ICFP Contest. Прямо вау...Естественно, всё дело в интеграции. Учитывая наличие порядка 3k проблем, ручной их процессинг без какого-то строго учёта просто не скейлился. На том и выехали.
Постфактум шансы для нашей команды разработать за трое суток точный солвер оцениваю как околонулевые из-за необходимости реализации большого количества всякой тонкой геометрии. Хотя многим другим командам это удалось. Возможно, они просто умеют готовить boost + gmp...
Послешоу
...Через пару дней после окончания контеста я вернулся к идее точного солвера и начал периодически что-то попиливать, благо орги лидерборд не отключали, а только перевели его в режим postmortem, где он стал чаще обновляться.Почти сразу солвер научился решать задачку-пример из спецификации, а через несколько дней уже окреп до того, что осилил 17-ую Проблему (которая содержала какую-то нетривиальную складку).
[19:36, 8/13] AP: Не знаю, чего все так парятся с 17-ой задачей...
Пока я 3 часа гулял, мой солвер нашёл решение :-)
[19:37, 8/13] AP: Правда, я его еще не проверял формально, но на вид вполне ok
[22:17, 8/13] AS: Так долго искал решение для 17? Где 5 полигонов??
[22:18, 8/13] AS: Это прекрасно, что он его нашёл.
И это отличный результат для субботы.
Для той, что была неделю назад :)
[22:18, 8/13] AP: Ну, не 5, а 8.
Ну а чего ты хотел от неоптимизированного поиска в глубину?
[22:18, 8/13] AP: Зато решил!
[22:18, 8/13] AP: Да, суббота пропала не зря.
[22:19, 8/13] AS: Это да, это чудесно :). Точный солвер тоже есть в копилке :)
[22:21, 8/13] AP: Это ведь на самом деле поразительный результат.
Три часа ты ждёшь неизвестно чего
(и даже не знаешь, сколько часов будешь еще ждать)
и вдруг получаешь ответ, который валидируется на бумажке
А 17-го числа та же 17-ая проблема уже решалась за несколько миллисекунд в интерпретаторе...
Следующим этапом была 50-ая. После серии мелких фиксов она тоже стала решаться за миллисекунды.
Версия 1.4 солвера, выпущенная 19 августа, уже позволила войти в top-10 postmortem'а, несмотря на то, что в лидерборде до сих пор были какие-то активные участники. К этому моменту было точно решено 1423 из 3654 задач. Все низковисящие фрукты были сбиты, требовались новые идеи. Самой очевидной было реализовать поддержку дырок в силуэтах, но для начала я решил покопаться в имеющемся датасете и попробовать поклассифицировать задачи.
Само собой, сразу начались откровения. Разве вот это не прекрасно?
Следующей фичей солвера v1.5 стала поддержка дыр в силуэтах, что позволило немедленно подняться до top-7. А ко 2-му сентября тот же солвер дотянулся до top-5 при 2110 решённых задачах из 3764. Кстати, всё это запускалось урывками на обыкновенном яблочном лэптопе.
8-го сентября я пильнул точный выпуклый солвер, что оказалось весьма непросто. Некоторые заботливые граждане так тщательно, знаете ли, подбирали угол поворота силуэта, чтобы его было очень сложно вернуть обратно в единичный квадрат. Особо отметим авторов 5391, 6214, 3272 и 78. Но и это затруднение было преодолено в итоге. Жаль, что недорешённых выпуклых задач было совсем чуть.
9-го случилось очередное озарение (прошло предыдущее помутнение...) и солвер стал перебирать намного меньше эквивалентных поддеревьев. Кратковременно был взят top-4, но малину испортили Дикие Башкортостанские Маги со своим солвером OXYETHYLENE, которые спихнули меня обратно на 5-ую позицию.
19-го я выпустил версию 1.11 с кучей новых отсечений плюс некоторые апгрейды к интеграции, которые позволяли не решать эквивалентные задачи. А также я заглянул, наконец, в профайлер, отчего десятикратно увеличилась скорость перебора. На этом, к сожалению, всё и закончилось, т.к. после объявления результатов орги отключили лидерборд. Моя система позволяла работать и без сервера, но это было как-то скучно. Поразительно, но даже в этой версии всё еще оставался баг из-за которого иногда неправильно вычислялась точка пересечения двух отрезков...
В качестве финального аккорда я еще упоролся и проанализировал группу симметрий каждой из проблем и добавил-таки поддержку вращательных симметрий в солвер (+45 решённых задач).
А в итоге осталось 975 нерешённых задач из 3764 и что с ними делать стало совершенно непонятно. Единственный вариант — это повторить весь экзерцис но только уже с невыпуклыми полигонами, как в солвере unagi. Но на этом мой энтузиазм оказался исчерпан.
Окончательные итоги
Задача у оргов получилась просто на зависть. Красивая, геометрическая, многоплановая, с кучей возможных подходов.
Кто-то использовал увлекающуюся оригами жену как чит-код. Кто-то придумывал задачки.
Невероятный Алексей jabber.ru в жесточайшей борьбе c unagi взял лайтнинг фактически врукопашную.
Сами unagi реализовали примерно то же самое, что описано в этом посте, только для невыпуклых полигонов и уложившись в 3 дня, а не в 3 месяца, и заняли первое место с колоссальным отрывом.
TBD опубликовали проблему, которую никто не смог решить, за что и удостоились судейского приза.
Много всяких интересных отчётов можно найти на reddite'е.
Ну, а ваш покорный слуга так и не согнул ни одного листа бумаги. Никаких частных случаев.
Сезон 2017
Судя по всему, в этот раз мы хлебнём каких-то азартных игр в lambda casino, где некий lambda punter будет зарабатывать какие-то lambda point'ы. А может быть, всё будет совсем не так, и будем мы управлять какой-то лямбда-плоскодонкой в бурлящей реке жидкого гелия...В любом случае, без лямбд не обойдётся на этот раз. Жутко интересно.
