Dmitry Astapov (_adept_) wrote,
Dmitry Astapov
_adept_

Category:

ICFPC-2016: день первый

(Это первая часть рассказа, а вот вторая и третья)

В этом году ICFPC был про оригами.

Вам дается контур сложенной из бумаги плоской фигуры (в виде координат точек) и вы должны ее сложить. Для тех, кто уже офигел и не знает, за что хвататься, дается дополнительная подсказка - еще одна "картинка", показывающая все ребра и складки в этом контуре -- представьте, что вы смотрите оригами "на просвет", однако при этом все точно совпадающие складки и ребра сливаются воедино. Организаторы называли это "контуром" и "скелетом". Еще про оригами известно то, что оно сложено из листа бумаги размером 1x1.

Вот на картинке контур закрашен красным, а линии скелета выделены:


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

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



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


Если у вас это получилось, то вы получаете 1/(N+1) очков от "стоимости задачи" (где N - количество таких же молодцов, как и вы), а если получилось не очень хорошо, то вы получаете 1/(N+1)/M очков (где N - количество молодцов, а M - некое число, зависящее от количества таких же неудачников, как и вы и степени похожести вашей фигурки). Очевидно, что точно решенные задачи приносят намного больше очков.

Был интерактивный leaderboard.

По истечении 24 часов открывалась возможность засылать свои задачки и решать чужие. Авторы задач получали (5000-размер задачи)/молодцов очков, что по первым прикидкам было чуть больше, чем дофига (если твою задачу никто не решил).

День первый

В моей временной зоне все начиналось в час ночи. Собрав волю в кулак, я пошел спать до того, как было опубликовано задание, и на следующий день проснулся аж в 10:00 и засел читать условие. Первые впечатления были смешанные. Ура, в этом году без навязшего в зубах AI. Ура, leaderboard. Ура, не надо готовить свой код для исполнения на сервере организаторов. Ура, просто засылаем решение в каком-то простом формате, а решать можно на чем угодно и как угодно.

С другой стороны - оригами. У меня не очень хорошо с оригами. И с геометрией. И с оригами. И с написанием гуёв. И с оригами. Ах да, и два человека, с которыми я собирался участвовать - отвалились буквально перед самым началом процесса. И как это предполагается решать? Начиная с квадратного листа и сворачивая его? Или наоборот - пытаясь представить, какой именно свернутой бумажке соответствует скелет и разворачивая его?


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

REST API, говорите? С примерами на curl? Замечательно, заворачиваем все в bash, суем в нужные места "sleep 0.5", чтобы сервер не ругался на слишком много запросов (еще 0.5 секунд добавляют тормоза баша), и скрипт для выкачивания задач готов.

Это задало определенный тон на все соревнование -- больше, больше шелла и скриптов. Я колебался, что именно брать для рисования задач -- cairo2 или ocaml'овский graphics, и в результате выбрал gnuplot + все тот же bash.

Для lightning round организаторы дали 100 задач, сложность которых росла очень медленно. Квадратик. Квадратик, сдвинутый из начала координат. Повернутый квадратик. Чуть меньший квадратик. В 12:00 я заслал первое (идеальное) решение для тупого квадратика и был доволен собой. И тут внезапно (зацените всю красоту гнуплота, кстати - на статической картинке этого не видно, но можно было щелкать мышкой и включать-выключать видимость контура и скелета по отдельности):



Или вот:


Это нифига не очевидно с первого взгляда, но такую фигуру нельзя сложить без так называемого inside reverse fold. Это мне очень вовремя объяснила жена, у которой с оригами не в пример лучше моего. То есть, нужно сделать несколько сгибов, а потом один из них вот этак вытащить наружу (или наборот - заправить внутрь под уже сложенные слои бумаги).

Я понял, что я вообще не понимаю, как это можно 1)распознать по описанию задачи 2)запрограммировать. Но унывать нельзя, надо что-то делать. И я сделал програмку, которая распознает задачи, являющиеся переносом-повотором квадрата 1х1 и решает их. Чисто чтобы отладить парсер заданий, принтер решений, работу с числами (которые были в виде натуральных дробей -- привет, Num) и все такое прочее. "Такое прочее" заняло у меня порядочно времени (как всегда бывает), и этот игрушечный солвер был у меня готов только к 15:00.

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

Дальше я понял, что раз "лыжи не едут", то надо делать хоть что-то. Этим хоть чем-то оказалась идея, которая пришла в голову, думаю, всем без исключения - можно в качестве решения отсылать листик 1х1 без всяких сгибов, заботливо положеный поверх требуемого оригами. Это давало какие-то небольшие очки, но все-таки лучше, чем ничего. Опять же, можно написать еще скриптов - чтобы решать все задачи, засылать все решения и т.п.

К 18:00 я накрыл квадратиками все задачи и неожиданно поднялся на 18 место. Приободренный, я подумал, что я могу пойти на один шаг дальше -- если оригами меньше квадрата 1х1, то я могу положить оригами в угол моего листа, загнуть правый и верхний края, и результат будет лучше (т.к. получившийся квадратик с подгибами будет "более похож" на результат). Прелесть в то, что структура такого решения всегда одна и та же -- лист бумаги будет разделен сгибами на четыре прямоугольника, номера точек и номера вершин прямоугольников всегда одни и те же, отличаются только их координаты (в зависимости от того, насколько сильно подогнут листик). Но координаты-то как раз посчитать легко. А все остальное можно захардкодить.

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

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

К 23:00 у меня появилось первое приближение к коду, который загибает уголок у листа бумаги (это я так думал, на самом деле там не работало примерно ничего, но я об этом узнаю только завтра). После полуночи закончился lightning (я был где-то на 18-м месте), организаторы опубликовали первую любовно сделанную моей женой задачу, на нее никто в течении часа не позарился, и я получил где-то 4000 очков и взлетел до 13 места. Окрыленный этим результатом, я пошел спать.

Хронология взлетов и падений:


Продолжение.
Tags: icfpc
Subscribe
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 8 comments