ICFP'09, день первый

Сегодня (о, ужас) уже среда, а я вот только-только собрался написать небольшой отчет по мотивам конкурса программеров ICFP^[1], в котором мне удалось поучаствовать (правда, с весьма-весьма скромными результатами) в эти выходные. Вкратце, для тех, у кого нет сил и желания перечитывать все подробности и правила конкурса:

• Конкурс проводится уже много лет разными американскими университетами и в нем принимает участие от 300 до 700 команд со всего мира.
• Конкурс проводится летом и идет 72 часа: именно столько времени проходит от публикации заданий на сайте организаторов до того момента, пока еще принимаются решения. В течение нескольких последних лет есть промежуточный зачет на момент 24 часа после опубликования заданий, так называемый lightning round.
• Задания от года к году варьируют, в прошлом году необходимо было написать программу управления марсоходом, в позапрошлом -- расшифровать генетический код пришельца по имени Эндо, до этого было очень интересное задание по археолингвистике.
• В целом на протяжение последних лет (что подтвердилось и в этом году) можно выделить ряд общих черт у заданий:
  • частью задания является реализация виртуальной машины, которая исполняет некий предлагаемый в качестве задания код. Иногда эта часть задания немного завуалирована, например в позапрошлом году необходимо было имплементировать алгоритм трансляции генома пришельца, который по сути является аналогом виртуальной машины.
  • второй, и зачастую самой главной частью задания, является создание некоего алгоритма, допускающего возможности его разнообразной оптимизации и состоящего, как правило, из ряда под-алгоритмов.
  • Основной проблемой конкурса зачастую становится race against time, то есть работать 72 часа без отдыха практически невозможно и приходится оптимально разделять время для того, чтобы успеть сделать максимально.

На всякий случай напомню, что я учусь на 3-м курсе (хотя правильнее сказать -- в 6 семестре) факультета "инженерная информатика" (Informatik-Ingenierwesen) Технического Университета Гамбурга и Харбурга.

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

В общем, с конкурсом подтвердился тот же принцип, который уже много раз срабатывал и в ЧГК: пытаться собрать команду за 2-3 дня до важного мероприятия в большинстве случаев (все-таки, исключения, подтверждающие это правило, случаются от случая к случаю) это "гиблый номер". Так, в общем-то, и получилось {Урок 1}. Однако, не буду забегать вперед, самое интересное, на мой взгляд, читать (да и писать, в общем-то) о конкурсе в хронологическом порядке. Итак...

За несколько дней до соревнования

Итак, решившись поучаствовать в конкурсе и пообщавшись с Себастианом (plaicy) с форума, я выяснил, что пока нас "двое с тобой", то есть для серьезной команды явно недостаточно. Обнаружив совершенно неожиданно информацию об этом конкурсе на моем самом любимом информационном ресурсе Хабрахабр, я попытался дать там анонс, на который откликнулся ровно один человек, да и тот почему-то так и не объявился во время конкурса.

Одновременно с этим я попробовал завербовать кого-то из нашей программы "студент-партнер Майкрософта" (Microsoft Student Partners), бросив в общий список рассылки информационное сообщение. Откликнулась пара человек с комментариями "интересно", но дальше никто не пошел.

За несколько минут до начала соревнования

Учитывая, что за день до этого мне удалили аж три зуба и кровь продолжала течь до часу ночи, а в пятницу мы еще провели 8-часовой мастер-класс по отдельным продуктам Microsoft Office 2007 на факультете экономической информатики Университета Гамбурга, к 20 часам, когда Contest должен был начаться в наших краях, я уже был полностью выжат и даже просто говорить мне было сложно (все еще болела десна на месте удаленных зубов и мешал тромб).

Пятница, вечер [0d0h0m]

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

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

Само "задание" состояло из исполняемого кода, который был написал для виртуальной машины, спецификация для которой подробно описывалась в задании. Машина являлась типичной безрегистровой 14-битной машиной Гарвардской архитектуры (с раздельной памятью для команд и данных): команды кодировались 32-битными числами, данные представляли собой массив из 8-байтовых double. В 14-битной адресное пространство проецировались и (раздельные для входных и выходных данных) порты, при этом входной порт использовался для загрузки текущих скоростей спутника и номера задания (так называемый actuator), а выходные данные (в терминологии организаторов sensor) выдавались в определенные выходные порты.

Организаторы прилагали бинарники для первых трех заданий, которые считывали исходные данные, осуществляли расчет и выдавали координаты самого спутника, нужные данные для решения заданий (величина орбиты в первом задания и положение второго спутника для второго и третьего), а также заработанные очки. Таким образом, с одной стороны, сразу было понятно, насколько твоё решение оптимально (по принципу: больше очков -- лучше решение), а также не было необходимости использовать какой-то Live CD и запускать решение на нем, как это было, например, в прошлом году с задачей про марсоход. За это организаторам большой респект!!

Распечатав спецификацию и бегло прочитав ее, пропуская подробности астрофизики и физики вообще, я бегло отписался Себастиану, что буду через 2-3 часа и мы пошли с женой пить мартини и смотреть "Доктора Хауса".

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

Продолжение следует...

P.S.: Если после прочтения вам (Вам!) стало хоть немного интересно, прочитайте вот этот анонс!