Снова лето, снова август, и снова ICFPC. Я уже полтора раза принимал участие в этом соревновании (чуть-чуть в 2014-м, полноценно в 2015-м) и пока что ни разу не пожалел о проведённом времени. Так что и в этом году снова собрался с товарищами из codingteam@conference.jabber.ru и на три дня погрузился в атмосферу сложных задач, соперничества с другими командами и, конечно же, разочарования в себе как программисте ☺

Команда в этом году претерпела некоторые изменения. Из выступавшего в прошлый раз состава остались только ForNeVeR, portnov, grouzen и я. К нам вернулся Hagane, в последний раз игравший в 2012-м. Также планировалось, что с нами будут ещё два цодингтимовца, но не срослось. Ну, ничего — чай, не последний раз выступаем; успеем ещё поиграть.

В качестве командного языка в этот раз снова взяли Haskell.

За пару недель до соревнования мы с Портновым потренировались немного на задачках с Timus. Они, конечно, не имеют отношения к тем задачам, что дают на ICFPC, но мозги размять никогда не вредно.

Пятница, часть первая

В этот раз контест для меня начинался в три часа ночи пятницы, для grouzen — то ли в полночь, то ли в час, для portnov — в пять утра, а для ForNeVeR и Hagane — в семь.

Вечер четверга в командном чатике прошёл за угадыванием задания. Организаторы в течении недели твитили всякую бессвязную ерунду: fizzbuzz на Ruby; опрос об эквивалентности двух функций; программу на Brainfuck, выводящую «Hello, fold/unfold»; ссылку на странную традицию в сумо; наконец, вопрос «check or fold?», который в icfpc@conference.jabber.ru приняли за отсылку к покеру. Позалипав немного на визуализацию выполнения Brainfuck-кода, мы постепенно разбрелись спать.

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

Задача (зеркало) в этом году состояла в определении складок, образующихся на бумаге при сборке плоского оригами с заданным силуэтом. В качестве подсказки нам давали «скелет» оригами, где видно все рёбра бумаги. Думаю, с картинкой будет понятней:

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

В задании картинок не было, только спецификация на текстовый формат, описывающий задачу. В три часа ночи часть про скелет я хоть и прочёл, но не понял, поэтому мысленно задача у меня свелась к «угадать процесс складывания оригами по силуэту результата». Прифигев со сложности, я отправился спать в искреннем недоумении касательно того, с какой стороны ко всему этому подходить.

Пятница, часть вторая

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

Суть идеи заключалась в том, чтобы последовательно «разгибать» скелет, аж пока не придём к единичному квадрату (который является исходной фигурой). Руководить процессом будет, конечно же, A*; цена перехода будет константной и равна единице, эвристика — степень похожести текущей фигуры на единичный квадрат. Просто и понятно!

С этим и пришёл в чат. Оказалось, что portnov уже решил вручную первый десяток задач, и мы на leaderbord не в самом низу. grouzen ушёл в изучение литературы, так как Википедия намекала, что математики уже не раз обращали своё внимание на оригами — может, придумали что-то полезное и для нашей задачи? Также у portnov и ForNeVeR вырисовывались какие-то идеи касательно складывания единичного квадрата в целевой силуэт, но я не видел в этом подходе каких-то очевидных преимуществ над разворачиванием скелета, поэтому не вникал.

Прежде чем приступать к реализации каких-то идей, нужен был инструментарий для работы с геометрией. Нагуглить удалось только некий clipper, с помощью которого можно было считать пересечения площадей, но с ним был целый ряд проблем: он специфически собирается, его нет в Stackage, для представления координат используется Int64 (а у нас в задачах встречаются числа вроде 1267650600228229401496703205376, что на 10^12 больше того, что влезает в 64 бита). Поэтому в первую очередь я взялся писать функции для перемещения и масштабирования задачи в единичный квадрат и обратно. Насколько я знаю, clipper мы забросили примерно сразу же после того, как я эти функции дописал :)

Пару часов спустя пришёл Hagane, и мы наконец вышли на крейсерскую скорость.

Я вбросил в чат перечень подзадач, которые видел в «разворачивалке» скелета, а именно:

1. поиск всех рёбер, по которым можно разогнуть скелет;
2. определение «половинок» листа по скелету и ребру, вдоль которого выполнен сгиб;
3. собственно функция, которая «разогнёт» скелет по заданному ребру;
4. какой-то контроллер, который будет всем этим рулить. Он должен как-то умно смотреть на список возможных рёбер и решать, по какому разгибать на следующем шаге.

И пока я занимался написанием жутко багованной функции для разрезания полигона прямой, Hagane взялся помогать мне с первой из подзадач. Идея там была простая: если скелет целиком помещается на одной из полуплоскостей, образованных проходящей через ребро прямой, то это ребро нам подходит в качестве кандидата.

Закончив с функцией разрезания, я полностью углубился в реализацию идеи с «разгибанием» скелета, поэтому времени и сил вникать в идеи остальных у меня уже не оставалось. Так что с этого момента мой отчёт будет в основном о том, что делал лично я. За деталями остальных идей обращайтесь к отчётам моих товарищей: отчёту ForNeVeR-а, отчёту Hagane, отчёту portnov. Grouzen отчёта так и не написал :(

Итак, после реализации некоторых геометрических функций я принялся за вторую из перечисленных выше подзадач. Как и в случае с первой, идея была простой: имея ребро (отрезок), по которому предположительно свёрнут скелет, мы можем найти все последовательности рёбер, начинающихся в одной точке отрезка и заканчивающиеся в другой. В процессе просмотра задач я обнаружил всего один случай, где такой подход не работает — это когда сгиб происходит по нескольким рёбрам сразу. Например, вот здесь, где складка получена путём «впихивания» угла внутрь сложенного пополам листа (пунктир обозначает невидимые части рёбер, заливка — количество наложенных друг на друга слоёв бумаги):

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

В чате тем временем шло бурное обсуждение тонкостей задания. Это всегда так: спецификация большая, фронтов работ много, поэтому при беглом ознакомлении выхватываешь только саму суть, а потом долго ещё возвращаешься к отдельным абзацам, пытаясь выяснить все-все-все детали. Вот и сейчас мы одновременно обсуждали несколько тем: какие же именно преобразования фигур допустимы, а какие нет; как происходит начисление очков за придуманные нами задачи и, соответственно, какую стратегию нам применять при их генерации; и немного Haskell (восхваляли Debug.Trace; ругали сайд-эффекты в API библиотеки diagrams).

В какой-то момент обсуждения ForNeVeR начал подозревать, что можно свернуть из исходного квадрата бесконечную ленту и ею выложить нужный нам силуэт. Ну, или хотя бы нарисовать ею какую-то кривую и заставить соперников решать. Потом оказалось, что это невозможно. Бумажки в четвёртом измерении сворачивать можно (без шуток), а бесконечные ленты делать нельзя? ICFPC уже не тот!

Так и закончился день. Я напоследок разобрался с одной из задач, для которой наш визуализатор показывал пустое поле: оказалось, что там организаторы настолько далеко переместили собранную фигуру от начала координат, что в SVG даже при увеличении в 25600% нельзя было разобрать ни фигурку, ни точку, обозначающую (0, 0). О том, что это та самая задача, что раньше не умещалась в Int64 clipper-а, я допёр только при написании отчёта =\

Часов в одиннадцать вечера мозг стал отказывать, и я, потупив немного в Интернетик и посмеявшись над апгрейдом сервера организаторов, в час ночи ушёл спать.

Суббота

На протяжении субботы я медленно, но верно дописывал кусочки, необходимые мне для «разворачивалки». Ничего интересного не происходило; я просто медленно писал код.

К вечеру наконец-то собрал всё это в кучу, типы сошлись, и я смог натравить солвер на реальные задачи. Тут меня ждал облом: «разворачивалка» осиливала сделать не больше одного шага. Задачи типа «отогнуть один уголок» она решала, но на всём остальном либо сдавалась, либо и вовсе падала (пора писать свою Prelude, с тотальными head и tail). Проблемы вроде того, что вместо эвристики у меня пока что проверка уровня «насколько сильно количество рёбер у скелета отличается от четырёх», внезапно отошли на второй план. (UPD 09.08.2016: тогда я верил, что это валидная, хоть и неэффективная, эвристика. Сегодня после замечания aleksey я понял, что ошибался.)

Есть время привносить баги и есть время чинить баги. С помощью Debug.Trace и визуализации всех промежуточных результатов, до которых смог дотянуться, я обнаружил, что со скелетом при его разворачивании часто случается какая-то беда, из-за которой он теряет одно из рёбер. Ну, а на незамкнутом скелете уже ничего не работает, вот решалка и сдаётся.

Больше трейсов, больше картинок, но всё без толку — баги отловить не выходит. Вот уже и глаза слипаются…

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

На таких скелетах поиск образованных сгибом половинок не работает — с точки зрения решалки на рисунке слева обычный квадрат. Принцип, по которому из скелета убираются рёбра, понятен: перекрывающиеся рёбра просто объединяются. А вот вернуть их обратно не так просто: нужно генерировать несколько вариантов, так как то, что точки лежат на одном ребре, ещё не значит, что между ними до объединения тоже было ребро. В общем, это увеличивает пространство поиска для нашего солвера. Эту задачу пришлось отложить в сторону, так как на фоне багов она была не слишком важна.

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

Воскресенье (и кусочек понедельника)

Утром воскресенья я, всё ещё пребывая в подавленном настроении, читаю в логах чатика идеи portnov о том, чтобы объединить «сворачивалку» и «разворачивалку» с целью устранить некоторые слабости первой. Вздыхаю, т.к. portnov хочет как раз ту часть «разворачивалки», в которой я вчера весь вечер безуспешно ловил баги.

В надежде на то, что это я просто вечером был уставший, предпринимаю ещё одну попытку понять, что же не так с разворачиванием фигур, но нет, баги таки сильнее меня. Бросаю эту затею нафиг.

И тут Hagane упоминает, что задачу с журавликом всё ещё никто не решил. Там нужно собрать классическое оригами, которые вы наверняка видели:

И я, отчаявшись уже написать что-то работающее, решаю заняться этой задачей вручную. В ней совершенно сумасшедшие координаты точек (огромные дроби), и на момент начала решения я ещё не знал, как буду с ними работать; но не беда, время подумать во время сборки найдётся.

Идея решения сводилась к следующему:

1. собираем «журавлика»;
2. нумеруем точки на рисунке выше, после чего переносим номера на бумагу;
3. развернув листочкек, имеем перед собой часть решения (схему складок) с уже помеченными точками;
4. каким-то образом высчитываем новые координаты точек (так как после разворотов и складываний они, естественно, поменялись).

Легко и просто!

Собрал первого журавлика из, наверное, самой плотной бумаги, что была у меня дома. Учёл ошибку, собрал ещё одного из бумаги потоньше. Немного поменял уже имевшийся у нас визуализатор задач, чтобы тот показывал каждую из точек задачи в виде отдельного рисунка; глядя на эти рисунки, принялся нумеровать точки на собранной птичке.

Тут меня подстерегала вторая проблема: задача, похоже, была оцифровкой реально собранного журавлика, поэтому рёбра, которые в идеальном мире с бесконечно тонкой бумагой совпали бы пиксель в пиксель, в задаче были рядышком. Но настолько рядышком, что на глаз одно ребро от другого отличить было невозможно.

Но ничего, ещё полчасика программирования — и вот уже визуализатор показывает «связанные» с текущей точкой рёбра. Опять-таки, по рисунку понять проще:

Но это не помогает, потому что там, где на этих рисунках чёрные линии, у бумажного журавлика пять разных накладывающихся друг на друга ребёр. Или не накладывающихся, т.к. бумага имеет толщину и привносит смещения. Я так и не разобрался, что там куда.

За три часа до конца контеста — в районе двенадцати ночи по моему локальному времени — я сдался.

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

Результат

За шесть часов до конца соревнования leaderboard заморозили (зеркало), но до этого мы были 44-ми из 293. Окончательный результат объявят во время ICFP, то есть 19–21 сентября. Обновление 21-го сентября: объявили. Мы заняли 50-е место.

Весь код опубликовали на GitHub: https://github.com/codingteam/icfpc-2016

Рефлексия

Несмотря на то, что команда в целом показала отличный результат (в разы лучше, чем в прошлом году), я расстроен. Играть было очень весело — особенно в последний день, когда я собирал и разбирал журавликов — но по ощущениям я не могу сказать, что был полезен команде.

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

Зато понял, что резиновые уточки — это попса. Бумажные журавлики — вот что выбирают discriminating hackers!

UPD 09.08.2016:

• После замечания aleksey (команда jabber.ru), понял, что, во-первых, неправильно описал в посте используемую в A* эвристику, а во-вторых, использовал в качестве эвристики функцию, переоценивающую расстояние до цели, что недопустимо и ломает алгоритм.
• Указал правильное время начала контеста для каждого из участников команды. (Пять минут спустя: вот теперь уже точно правильные. Ох уж этот grouzen-путешественник…)
• Добавил зеркало leaderboard-а (после заморозки) и задания (в последней его редакции).

UPD 21.09.2016:

• Добавил ссылку на финальные результаты. Мы заняли 50-е место.