ICFPC-2016: день первый
2016-08-09 12:31 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
dastapov(Это первая часть рассказа, а вот вторая и третья)
В этом году 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 места. Окрыленный этим результатом, я пошел спать.
Хронология взлетов и падений:
Продолжение.
В этом году 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 места. Окрыленный этим результатом, я пошел спать.
Хронология взлетов и падений:
Продолжение.