Отчёт об ICFPC 2016

Дата публикации: 2016-08-08

Начиная с 2012 года наша команда принимает участие в соревновании ICFP Contest. И этот год не стал исключением. В состав нашей команды в этом году вошли:

Ещё за день до начала мне в почту написал старый знакомец ulidtko, и я его тоже пригласил принять участие, но, к сожалению, он по каким-то причинам не смог появиться. Забегал вечером первого дня, отметился и убежал. Аналогично произошло с товарищем Newlifer. rexim, которого мы тоже ждали, заранее сказал, что участвовать в этом году не сможет :(

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

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

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

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

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

В первый день (а это была пятница, так что не все смогли полноценно поучаствовать) Портнов занимался визуализатором, а Минору возился с геометрией. Ближе к ночи подтянулся я с исправлениями визуализатора и Hagane, который начал делать какие-то компоненты для "разворачивалки" скелетов. В этот день нам очень пригодился Haskell Tool Stack, без которого бы мы очень долго возились со сборкой приложений.

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

Я очень сильно расстроился, начал с горя городить реализацию на F#, ругал Cabal почём свет стоит. К счастью, задачу с генератором у меня забрали. Помимо прочего, оказалось, что задачу я понял не совсем правильно, и решать её можно намного проще, чем я пытался к ней подойти. Впрочем, моя попытка сбежать на F# оказалась не единственной: Hagane начал делать генератор на... Racket. Через некоторое время ему тоже объяснили смысл задачи и рассказали про наличие у нас геометрических библиотек, так что он всё-таки переписал реализацию на Haskell (на основании моей предыдущей недоделки, от которой в итоге осталась всего пара строчек).

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

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

Последний день соревнования, воскресенье я потратил на какую-то ерунду: мелкие доделки генератора, попытки раскурить код Портнова и помочь ему хотя бы советом. Минору примерно к этому времени доделал свою продвинутую решалку и тоже начал её тестировать и, кажется, даже публиковать какие-то результаты. У нас появилась идея находить выпуклую оболочку (convex hull) многоугольников и задаваться целью довести решение до этой оболочки (потому что оболочка по определению является выпуклым многоугольником, и поэтому саму оболочку мы очень просто сможем получить).

Минору взялся уже вручную решать самую сложную задачу #101, но, к сожалению, не преуспел. Впрочем, ничего обидного тут нет: по итогам мероприятия точное решение этой задачи дала лишь одна команда.

Ночью в воскресенье мы оформили Readme и подготовили решение к тому, чтобы отправить его организаторам (это было обязательным условием участия).

По последним данным мы заняли 44 место, что вообще-то вполне неплохо по сравнению с предыдущим годом.

Мне очень понравилась задача этого года, и с привычной командой было приятно работать. Результатами команды я доволен — у нас получилось намного лучше, чем в прошлом году; мы растём. Однако своими личными результатами я недоволен, вклад в решение оказался не так значителен, как мне бы хотелось. И при этом мне хочется ещё раз повторить вывод предыдущего года, но уже будучи по другую сторону баррикад: негоже решать контесты на языках, которых не знаешь. Значительное, как мне кажется, время я потратил на сражения с системой типов Haskell, с которой знаком недостаточно глубоко. К следующему разу надо обязательно будет изучить Haskell на промышленном уровне, чтобы сходу просто садиться и кодить.

Наш код опубликован на GitHub, желающих приглашаю ознакомиться.