Введение

Отчёт от tilarids

Отчет от brox

Отчет от san

Отчет от svg

Отчет от mask

Лирическое отступление

Формальный результат

Введение

В этом году контест проходил с 5 по 8 августа, а организаторами были японцы. Сделано все было на высочайшем уровне, в лучших традициях ICFPC. Живой leaderboard был, сабмитить решения было просто, сервер не вис, сайт не лежал, описание задачи укладывалось в пару страниц. Задание было чрезвычайно интересным и многоплановым, так что всем участникам нашлось, чем заняться.

Так случилось, что san уехал в Le Pindeaustan незадолго до начала контеста, а покоритель эверестов tilarids как раз путешествовал лисапетом из Кремниевой долины на Аляску. Поэтому решено было штаб квартиру организовать в конторе brox’а Grid Dynamics. Гридовцы отнеслись с пониманием, выделили комнату с необходимым оборудованием, и даже бюджет на питание. Связь с домиком на берегу океана, где сидел san, а также с лисапетом мотелем tilarids’а проходила в режиме телеконференции, что оказалось весьма удобно. За трое суток google Hangouts завис всего раза 3, и то ненадолго.

С харьковской стороны также участвовали Сергей ‘svg’ Гришаев (уже традиционно) и приехавший из Киева на время контеста Максим ‘mask’ Медведь (с неплохо прокачанной математикой)

Задание

Те, у кого было нормальное детство, наверняка умеют сворачивать бумажные самолетики и корабли. Из обычного тетрадного листа “в клеточку” получались вполне действующие модели.

По условиям конкурса давалась вторая картинка - “рентгеновский” снимок модели со всеми краями и линиями сгиба, а требовалось построить развертку (первая картинка).

В классическом оригами все модели собираются из исходного единственного листа бумаги квадратной формы, при этом во время складывания лист нельзя разрезать. Именно такой набор (всего 101 модель) организаторы предоставили нам для решения. Приведенный чуть выше “журавлик” - задание номер 101. Насколько нам известно, с этим заданием справилась всего одна команда…

Предполагалось, что за сутки все команды научатся решать такого рода задачи хоть как-то, и затем разрешалось участникам самим создавать их и выкладывать всем остальным для решения. Каждая команда могла выложить 46 своих задач, и это давало дополнительные очки. Итого к последним часам контеста скопилось 3528 задач, вместе с изначальными.

Отчёт от tilarids 

В этом году ICFPC застал меня в дороге, но отказаться от участия я никак не мог. Поэтому я заранее забронировал 4 ночи в мотеле в Ньюпорте, штат Орегон. В моем часовом поясе соревнование начиналось в 5 часов вечера в четверг, а заканчивалось в 5 часов вечера в воскресенье. И вот до Ньюпорта я докрутил педали только часам к двум четверга, купил еды, сходил в душ и сразу включился в соревнование.

В первые полчаса-час я потратил на чтение условия и написание визуализатора задач и решений на Python + tkinter, но оказалось, что не у всех моих товарищей работает tkinter (не знал, что такое возможно). Пришлось переписывать на Javascript + Canvas. Этот визуализатор после нескольких перерождений мы использовали до конца контеста для отладки всех алгоритмов, которые в этом году писались на Java и Kotlin.

Я даже и не пытался начать что-то писать на С++, а сразу присоединился к san’у наблюдать, как он будет закладывать основу. Первоначальная идея заключалась в том, что нам нужна хорошая база для длинной арифметики и геометрии, и именно этим мы и занимались. После того, как фундаментальные функции были написаны, а Харьков подсобил с математикой, san’у удалось написать замечательную функцию fold, которая принимала на вход список фигур, прямую, по которой складывать и “направление” складывания, а на выходе давала новый список фигур, который получался после складывания по этой линии. Также была добавлена функция unfold, которая разворачивала все фолды, сохраняя информацию о соответствии точек в свернутом и развернутом варианте.

Тут я взял готовый fold, довел до ума unfold и написал первую версию нашего первого солвера, который проверял, является ли конечная фигура выпуклой, и делал fold по всем сторонам данной фигуры - ConvexSolver. Я воспользовался RestClientом, который написал svg к тому моменту, и вот на 10-м часу контеста мы получили первые осмысленные решения. Данный ConvexSolver в дальнейшем приносил нам кучу очков на простейших задачах.

Удовлетворенный полученным результатом, я попытался его развить, добавив SkeletonSolver. Идея заключалась в том, чтобы пытаться сворачивать не только по сторонам фигуры, но и по скелету. Идея не стоила потраченного времени, но в 6 утра после бессонной ночи я этого не понимал, и успел ее реализовать, хоть она в итоге практически ничего не принесла. После этого со спокойной душой я отпраивлся спать часа на 3.

К моменту как я проснулся, san хорошенько переколбасил ConvexSolver, и он стал решать даже то, что до этого не решал. В какой-то момент (но я пропустил, когда) svg добавил в решатель параллельный перенос, что дало еще множество решений.

Последние часы лайтнинга прошли в попытках улучшить и исправить существующий алгоритм. Когда до конца лайтнинга оставалось меньше часа, мы осознали, что каждый час мы должны публиковать хоть какую-то задачу, иначе потеряем очки. Последний час я потратил на попытки научить гуй, который написал san, генерировать задачи в том виде, в котором его примут организаторы. К сожалению, ничего не вышло, и нашу первую задачу мы так и не залили. Чтобы этого не происходило в дальнейшем, я написал RandomProblemGenerator, который пытался делать N случайных сверток и проверял, насколько плохо наш собственный солвер справляется с решением такой задачи, и выдавал самую замудреную задачу. Данный генератор работал неплохо, но в итоге мы использовали только несколько задач им сгенерированных. Причина простая - случайно сгенерированные задачи иногда на деле оказывались сложными, иногда - простыми. А вот задачи, которые придумывали brox и svg почти всегда оказывались сложными.

После того, как закончился лайтнинг, появилось время подумать над тем, что делать дальше, и попробовать идеи, на которые раньше не было времени. Одна из идей, что я исследовал, была автоматически сканировать развертки при помощи OpenCV и генерировать решения на их основе. За полчаса ковыряния с разверткой журавлика у меня ничего путного не вышло, поэтому я идею забросил, а очень зря. Нужно было доводить это до ума, чтобы можно было сложные задачи решать вручную, при помощи сканирования и простенького гуя. Как я понимаю, многие команды этим занимались.

Но вернемся к основной части контеста. До определенного момента мы с san’ом считали, что в развертках оригами должна соблюдаться некоторая симметричность, но тут mask открыл нам глаза, сложив из бумаги непонятное что-то, что в развертке давало четыре никак не симметричных многоугольника. Т.е., оказалось, что никаких требований к симметричности не было. Более того, организаторы от нас требовали лишь развертку решения, а не последовательность действий, так что возникла гениальная идея: а почему бы не подбирать развертку так, чтобы получался квадратный лист бумаги? Ну, и что, что мы не знаем, как из такой развертки получается наш силуэт, главное, что организаторы знают! Подбирать развертку собрались из многоугольников скелета. Так как скелет задавался не в виде полигонов, а в виде отрезков, san написал генератор многоугольников и, наконец, пошел спать.

Взяв готовый генератор многоугольников я сел писать PolySolver, который сначала строил граф соединений между многоугольниками (соединение между многоугольниками возможно только если у них общая сторона; многоугольник соединен сам с собой через каждую из своих сторон), а потом пытался замостить плоскость данными многоугольниками. Стоит упомянуть, что я активно использовал одну из наших фундаментальных утилит, которая позволяла находить объединения произвольных (в т.ч. невыпуклых) многоугольников. San написал этот код с использованием какой-то java либы, и она, к сожалению, работала c числами с плавающей точкой. На переводе из BigRation в double и обратно терялась точность, и проявлялись тормоза. Впрочем, все это не помешало мне все же написать этот PolySolver, но, к сожалению, он банально не справлялся с перебором такого огромного количества вариантов. Тут проснулся san и предложил для решения задачи №49 просто считать, что каждый многоугольник может быть использован только единожды. С таким ограничением PolySolver начал справляться с некоторыми задачами, но, очевидно, не подходил для решения всех задач.

San же решил не разбираться с тормозами PolySolverа, и начал писать собственный перебиральщик, который он назвал FloatSolver. Основными отличиями от PolySolver было то, что для решения использовались числа с плавающей точкой (отсюда и название; забавно, что после все было переделано на BigRational, так что от floatов осталось только название) и использовалась priority queue вместо обычного DFS.

Довольно быстро я оставил попытки реанимировать PolySolver и переключился помогать san’у улучшать его решение. Что радует, время потраченное на PolySolver не было потрачено впустую. Решения, которые он находил, позволили отладить FloatSolver, а еще once in a blue moon PolySolver решал задачи, которые оказывались FloatSolver не по зубам. Очень удобно, когда есть два решения одной задачи, написанные разными людьми. У таких решений дырки в разных местах.

Добавив кучу проверок и улучшений в FloatSolver, а также получив от svg список задач, на которых FloatSolver затыкался, я принялся вручную скармливать эти задачи FloatSolverу с разными параметрами. Понимание того, какие параметры помогают, а какие - нет, помогли впоследствии с написанием MetaSolver (детище svg, которое запускало все живые солверы).

Последние часы контеста мы чинили баги, добавляли новые проверки, вычищали использование double из кода, и под конец - заливали все решения с 5 машин. Как обычно, мы не залили существенную часть решений просто потому, что не успели. Мы даже не успели погонять FloatSolver с таймаутом больше 60 секунд. Но все равно надежда на неплохое место остается.

Вывод: участвовать в мотеле оказалось вполне возможным благодаря hangouts и разумному распределению задач. Самое сложное оказалось складывать оригами в комнате мотеля, где не было ни одного листка бумаги, кроме страниц Библии (а портить чужое имущество не хотелось). Но в целом контест - удался! Спасибо организаторам и сокомандникам!

Отчет от brox

Закончив подготовку комнаты к мероприятию и встретив гостей, я понял, что мы готовы - если не к победе, то к неограниченному фану. Опубликованное в 3 часа ночи задание сразу же укрепило в мысли, что скучно нам не будет. San тут же кинулся имплементить правила, tilarids сделал визуализатор на python, а мы начали делать инфраструктуру для сабмита решений (ибо их предстояло отправлять пачками). Все 3 дня контеста шло обсуждение, как можно сократить перебор (ведь задача NP-полная). Доска покрывалась слоями математики, а наши столы - кучами  согнутых бумажек. Примитивный переборный алгоритм поиска решения был более-менее очевиден, и для простых задач (2-3 сгиба исходного квадрата) давал хороший результат. Откровением для нас стало, что можно обычными поворотом и параллельным переносом квадратного листа сделать задачу нерешаемой нашим примитивным алгоритмом. Эта ситуация была исправлена полностью (кажется, svg) только (кажется) на 3-й день контеста.

Поскольку народа, яростно долбящего по клавиатуре в любимых IDE, у нас хватало, я в основном занимался нашей стратегией. Помимо решения чужих задач (с которыми хотя бы было понятно, куда двигаться) нам нужно было подумать и о создании своих. Перепробовав несколько рандомных складывателей бумаги от san’а и tilarids’а, мы поняли, что так мы много очков не заработаем. Даже задачи с предельным размером решения (5000 байт), даже с огромными рациональными числами (составленными из гигантских простых), были быстро решены соперниками, а нам самим мало что досталось. Так что я и svg сосредоточились на “полуручном” генераторе задач. Подходов было 2:

1) начать с узкой полосы, составленной сгибанием на N равных частей параллельными сгибами, и затем уже из полученной “гармошки” вручную свернуть сложную фигуру, желательно с “дырками” внутри

2) просто сгибать квадрат вручную таким образом, чтобы за 3-4 сгиба получить достаточно замороченную конструкцию, при этом стараясь минимизировать длину решения

Забегая вперед, скажу, что именно эти 2 метода генерации проблем и принесли нам максимум профита.

В какой-то момент мне пришла в голову идея, которая в принципе могла дать в наше распоряжение семейство труднорешаемых задач, и достаточно было варьировать всего один параметр.

Как видим, ни одна из четырех линий сгиба не проходит сплошной линией через весь лист. Если посмотреть на полученную в результате такого хитрого сгибания фигуру справа, становится ясно, что решить ее может только переборный алгоритм - последовательные разгибания вдоль любого ребра не приводит ни к чему. Mask построил полное аналитическое решение (основываясь на координатах “центральной” точки). Мы тут же засабмитили пробную задачку, и через пару часов стало ясно, что несколько команд таки обладают полным переборным решателем.

Еще несколько часов пришлось потратить на отладку солвера tilarids’а, который иногда упорно отказывался решать простейшие задачи. Дело оказалось в неточном критерии выхода из рекурсии, в результате чего найденные решения отбрасывались.

Оставшееся время я генерил новые проблемы для отправки на сервер и время от времени выводил из ступора san’а, складывая вручную из бумаги сложные случаи.

В целом время проведено чудесно и фан получен на 100%. Многие из алгоритмических подходов мы не успели попробовать или не вспомнили, зато те, что сделали, сделали хорошо.

Отчет от san

ICFPC меня застал тоже вне дома, и поэтому я участвовал по скайпу (на самом деле по Hangouts), и начало у меня произошло в 8 вечера. Накануне я хорошо выспался 2 дня и это позволило полностью попедалить в лайтнинг раунд.

Проблема этого года сложна тем, что она плохо умещается в голове, и мне как человеку, который мыслит исключительно образно, конкретно, а не математически абстрактно, было очень сложно придумывать подходы. Коварство этой задачи заключалось также в том, что чем больше втягиваешься в образное обдумывание, тем более сложных видишь нюансов, а еще дальше - бездна.

Весь лайтнинг раунд меня неотступно преследовало сильное впечатление, что решением является визуальное (!) дерево линий на бумаге: первый сгиб, от него второй сгиб дает веточки под одинаковым углом, пересекая ближайшую линию, итд:

Тут на картнке первая линия сгиба - диагональ, затем остальные 2 синие линии, а следующий сгиб - 4 красных линий итд.

Математическое же решение, которым ошарашил меня mask сразу по окончании лайтнинг раунда, и заставил пересмотреть всю мою жизнь, утверждало, что я наивно взял частный случай из предложенной организаторами иллюстрационной игрушки, и что существуют сгибы, отличные от “Valley/Mountain Fold”, где нету первой линии пересекающей лист бумаги целиком от края к краю. Буквально он сказал, что если мы возьмем все многоугольники из описания проблемы скелетом, и замостим ими первоначальный лист, то проблему мы решили.

Одним словом, для дальнейшего продвижения мы предположили (оставим доказательство в качестве легкого развлечения читателю), что все многоугольники в решении - выпуклые.

Поэтому в начале второго дня я для дальнейшего решения написал находилку всех выпуклых многоугольников среди скелета проблемы (см рисунок), добавив в скелетон сначала ребер, если на некоем ребре существовала точка, принадлежащая другим ребрам, но не делящая его на 2 ребра изначально (на рисунке нижнее ребро первоначальной фигуры было голубым (целиком), пришлось ввести туда доп. точку и разбить на оранж и зеленое)

И вот, имея набор всех многоугольников, следовало начать с какого-нибудь и нагенерить из них квадратную область (развертку), так чтобы сумма была 1 и чтобы удовлетворялись условия остановки.

Любопытно, что суммарная площадь найденных многоугольников иногда была равна единице, но в основном нет. В этом случае наверняка некоторые многоугольники должны были присутствовать на развертке несколько раз, а некоторые не должны были участвовать, тк придуманы зря. На протяжении контеста мы всего лишь прикрутили несколько видов ограничений “использовать максимум 1 экземляр, или 2 или 4”. Но после контеста встретили здравую мысль, что можно было “посчитать площади и решить рюкзак” (чисто площадями, таким образом прекрасно найдя полный набор многоугольников), что могло сработать для большого объема случайно сгенерированных задач, для которых рюкзак бы складывался в единственном варианте.

Решение которое я наимплементил далее, выглядело как priority queue с вариантами решений с постоянно растущим расползающимся разложением смежных фигур (смежность фигур бралась из описания проблемы после разбиения ее на выпуклые многоугольники). Каждая новая фигура начинала новое “поколение”, для которого с помощью мемоизации можно было получить повороты ее соседей в этом поколении (берешь соседа из предыдущего поколения как он там есть, и отражаешь так же как была отражена основная фигура в этом поколении, если она участвовала, конечно, в отраженном виде). В очередь ложились немутабельные структуры, ссылающиеся на родителя, поэтому все было не очень-очень тормознуто, ну, конечно не сишечка. Перебор давал несколько сотен валидных поколений в секунду на ноуте, и несколько тысяч на амазонском многоядерном сервере.

Было написано несколько критериев останова (суммарная площадь=1, крайние точки находятся на maxx/maxy/minx/miny и соответственно образуют 2 равные диагонали, квадрат длины которых сами знаете сколько) и еще несколько штук еще более дешевых.

Для лучшей сходимости был написан критерий “плотности” решения, чтобы оно не расползалось острыми хоботьями в стороны; он определялся как суммарная площадь уложенных фигур деленная на площадь описанного прямоугольника. Его заюзание в  priority queue сделало поиск немного умнее. Еще я начал писать критерий дающий оценку количества и качества непрерывных линий в текущем поколении, чтобы фигуры сразу складывались более упорядоченно, но недописал, и переборщик их укладывал насыпом, как попало.

Когда tilarids нашел и исправил ряд бажин, алгоритм стал работать еще лучше.

Хотелось бы добавить, что начали мы писать на Java, но после активного использования рациональных чисел и математики с ними стало очевидным переключиться на Котлин, так как там есть переопределение операций, и наиболее смелые товарищи (я) и дальше писали на нем (впервые в жизни), а кто посчитал себя более консервативным, продолжали писать на Java. Котлин рулит!

Уже после контеста я понял, что можно было чуток упростить переборщик, даже и не пробуя прикладывать смежные многоугольники так и эдак (с миррором и без), а прикладывать без миррора, если они не пересекались в проблеме, и всегда с миррором, если пересекались в проблеме.

Других отчетов и кода я еще не читал, поэтому сколько очевидных вещей прошло мимо нашей команды, узнаю позднее 8)

Updates (поздние мысли)

Один человек пишет, что если у многоугольника длины сторон рациональные, то это однозначно угол первоначального листа. https://en.wikipedia.org/wiki/Mathematics_of_paper_folding#/media/File:Haga_theorem_1.svg Стало быть можно взять и начинать разбор с угла, отсекая сразу решения по двум лучам, что сокращает количество.

Еще один пишет, что если грань не имеет соседей, то это край бумаги. Стало быть, другой край бумаги если есть то должен быть на расстоянии 1, если параллельный. Тоже могло бы сократить.

Еще мне пришла мысль, что для того чтобы укладывать фигуры плотно (тк решение суть плотно уложенные фигуры), можно ложить только фигуры, плотно касающиеся 1 или двух фигур только. И обязательно считать периметр и выбирать сначала решения, у которых периметр стремится по форме к окружности (для этого считать отношение периметра и площади, брать лучшее). Периметр легко считается инкрементально при выполнении усливия касания максимум 2 фигур (и необразования дыр)

Отчет от svg

TBD?

Отчет от mask

В этом году во вторник, за 3 дня до ICFPC, я начал интересоваться, кто хочет поучаствовать в контесте. В среду днем меня заинвайтили в скайп чат команды THIRTEEN. Часть команды находилась в Харькове, поэтому где-то в течение часа я договорился за участие в составе команды, взял билеты (из Киева) и уже в четверг вечером был на месте.

Задачу выложили в 3 ночи в пятницу. Надо было написать развертку оригами, свернутого из листа 1х1. По условию задачи давался результат (силуэт) и список “ребер”, по которым это оригами сворачивали. Нужно было найти разделение листа 1х1 на многоугольники и размещение этих многоугольников (используя конгруэнтную трансформацию) на плоскости так, чтобы в результате получился силуэт из условия.

Организаторы дали UI для сворачивания, отдельно отметив, что там можно получить не все возможные оригами.

Сначала все прочитали задачу, потом обсудили, чтобы синхронизировать понимание условия. После чего мы скачали все начальные задачи организаторов (101 шт) и написали визуализатор, чтобы представлять, с чем имеем дело. Настало утро, и я решил пойти и хоть немного выспаться, т.к. это было утро пятницы. Днем мне было необходимо присутствовать на нескольких рабочих митингах, поэтому пришлось поработать и в перерывах поспать, пока остальная часть команды занималась, собственно, контестом. Тем не менее в перерывах между сном и работой я пытался придумать решение задачи, записав условие в разных формулировках. Где-то днем я понял, что по факту у нас есть конгруэнтное отображение, которое все многоугольники из разбиения квадрата 1х1 отображает на плоскость так, что в результате получается силуэт. А границы между исходными многоугольниками образуют скелетон. По факту можно было взять многоугольники из результата разбиения и сделать из них квадрат 1х1. Самый простой вариант — тупой переборщик, для отсечения лишних поддеревьев перебора нужны были эвристики. С этим я и пошел вечером в офис.

Прихожу — а тут уже написаны и визуализатор, и solver для каких-то типов задач, и уже даже есть полностью решенные задачи. После обсуждения примитивного варианта переборщика, возможных эвристик и того, что было написано на данный момент, я решил писать свой вариант переборщика на С++ из рассчета на то, что JVM может стать ботлнеком. В результате поиска библиотек, в которых есть и big rational, и что-то из геометрии был найден CGAL.

Тем временем первые сутки контеста почти закончились. Ровно через сутки после начала могла быть опубликована одна задача от каждой команды. Мы этот момент пропустили и, соответственно, остались без первой опубликованной задачи.

До самого утра субботы я писал переборщик, а потом ушел спать. Вечером в субботу я пришел, продолжил написание переборщика, поздно ночью в воскресенье снова ушел спать. Днем в воскресенье я понял, что до конца контеста осталось около 12 часов, и в любом случае дописать и отдебажить я не успею. Тут brox предложил посчитать условие для задачи, которую в принципе нельзя сделать сворачиванием бумаги от края до края, и после нескольких итераций вычислений (сначала неправильных) получилась задача 6136. В результате эту задачу решили 12 команд — на основе этого можно оценить, у кого был хотя бы примитивный полный переборщик.

Дальше до конца контеста я выписал на доске и сдал вручную решение задачи #100 (по бумажной развертке brox’а), еще какой-то очень простой задачи, которую наш переборщик не находил, пытался сделать из ручного folder’а код для создания условия задачи (не получилось, folder слишком хитро хранил результат, там не каждый результат можно было просто взять и развернуть в условие), смотрел оставшиеся задачи, которые нашими solver’ами не были решены, смотрел на количество решений наших задач. Leaderboard был заморожен за 6 часов до конца, но по каждой задаче все равно можно было посмотреть список resemblance для решений от команд. Наши задачи были решены все, из них только 2 задачи решила всего одна команда, остальные задачи были решены как минимум двумя командами.

В общем контест был организован очень хорошо.  В leaderboard’е была видна гонка команд, а система начисления баллов сильно поощряла тех, кто умеет полностью решать чужие задачи и выдавать сложные задачи, как и должно быть.

Лирическое отступление

Программисты изо всех сил грызли задачу:

И днем и ночью...

San стоял на подоконнике в 20 см от пропасти. Временами его сменял tilarids.

Иногда моделировали “вживую”. Иногда доска заполнялась “матаном”

Формальный результат

На момент, когда была “заморожена“ таблица результатов, мы были 18-е, но еще несколько часов продолжали решать и сабмитить, из всех стволов, включая 36-ядерную виртуалку на амазоне. Всего нами было полностью решено более 2000 из 3528 задач. Так что есть хорошая вероятность подняться места до 12-го. Впрочем, такая же хорошая вероятность и упасть)

А организаторам контеста из страны восходящего солнца - отдельное аригато. どうもありがとう

Update 22 Сентября: Официально 19 место - полимеры невозможно найти.

Очередная заметка на следующий раз: писать графический визуализатор солвера УДОБНЕЕ И СРАЗУ.