вторник, 30 июня 2009 г.

ICFPC-09 отчёт

Я давно ничего не писал в блог, но сейчас появился отличный повод! Речь идёт о недавно завершившемся мероприятии под названием ICFPC (ICFP contest, или соревнование приуроченное ко всемирной конференции ICFP).
ICFPC — ежегодное международное первенство по программированию, проводимое среди всех желающих уже более 10 лет. Особенностью данного мероприятия и отличием его от других алгоритмических контестов состоит в общем настроении и характере заданий. Решение задач на ACM-подобных соревнованиях у меня всегда ассоциировалось с необходимостью владения множеством специализрованных алгоритмов и умением быстро выбрать подходящий для конкретной задачи. Тут же, наоборот, меня привлекает то, что при решении задач могут понадобиться знания из абсолютно разных областей, порой не связанных с ИТ вообще. С другой стороны ICFPC — это одна глобальная задача, в рамках которой, кроме локальных оптимизаций тех же алгоритмов, необходим и комплексный взгляд “сверху” на всю проблему вцелом, с необходимостью принятия обдуманных, оправданных архитектурных решений.
Я наблюдал за этим мероприятием уже не первый год. Два года назад узнал о нём только по окончании и тогда впервые попробовал свои силы в решении. В прошлом году уже планировал принять участие, но обстоятельства помешали. В этом году хотя и выделял время заранее, несколько планов от этого пострадало. Как выяснилось, оно того стоило!
Хотя формально начало контеста было запланировано на 21:00 пятницы, организаторы решили добавить интриги и начали выкладывать намёки на предстоящее задание ещё за несколько дней, о чём и заявили в FAQ на сайте контеста. Несколько дней участники icfpc-комьюнити на icfpc@c.j.r и #icfp-contest@FreeNode ломали головы над тем, что же зашифровали в “подсказках” организаторы и ближе к непосредственно началу все были уверенны, что тематика контеста в этом году будет связана с космосом, и что-то мы должны будем в этот космос запускать.
Итак, пятница, 21:00 по Киеву. Первые счастливчики уже получили спецификации с заданием, остальным же оф. сайт соревнования демонстрирует полное нежелание делиться информацией, потому полученная спека быстро расходится по файлообменникам и все полчаса сидят довольные, изучая этот 16-страничный документ.
Попробую описать его парой абзацев. В нём описывается некоторая система моделирования космических полётов, которую участникам предстоит реализовать в виде виртуальной машины. Параметры моделирования организаторы обещают выдавать в виде готовых бинарников, предназначенных для выполнения в этой ВМ. Кроме того каждому бинарнику соответствует одно из четырёх заданий, отличающихся по сложности. Сами задания заключались в оптимальном управлении данным участникам спутником, используя информацию о его положении в плоскости, и положении других тел. Все тела, в каждой из заданных бинарниками систем, дрейфовали на околоземных орбитах, а целями, разделяющими их по сложности были:
  • перевести спутник с одной круговой орбиты на другую;
  • перевести спутник на другую орбиту и состыковаться на новой орбите с летающим там спутником;
  • состыковаться со спутником на другой орбите, причём орбиты уже эллиптические вместо круговых;
  • летая вокруг Земли управлять подконтрольным спутником так, чтобы по пути пересечься ещё с десятком спутников бороздящих просторы космоса
Из возможных манёвров нам была доступна придача нашему спутнику некоторого импульса в произвольном направлении, причём всё маневрирование было ограничено количеством топлива, заложенным в спутник.
Задача, как оказалось, довольно интересная и нетривиальная. Из подсказок организаторы оставили только небольшой обзор алгоритма Гомана, который хоть и не является оптимальным, но показал всем в каком направлении нужно думать. Спустя некоторое время, комьюнити обнаружило книжку “Orbital Mechanics for Engineering Students”, подмышкой с которой мы и провели всё время до конца соревнования. По тексту — в ней нашлись ответы на все необходимые задания, и оставалось только реализовать прочитанное программно, в чём и получилась основная загвоздка. Думаю каждый из нашей команды просидел не один час хоть над одной из нелепых ошибок/опечаток в коде управления спутником.


Нельзя также забывать и о первой части задания — реализации самого окружения для моделирования системы. Построение виртуальной машины (в котором мне почти не удалось поучаствовать, т.к. сразу полез читать про орбиты) — по-моему как раз то, что соответствует формату icfp контеста. О ней могу сказать только то, что она была готова к работе уже на следующее утро, после начала, и с тех пор не менялась, тоесть была вполне приличной. Тут же огромное ударение стоит сделать на визуализации. Многие команды пытались решать задание без визуализации совсем, или ограничивались, например, текстовым выводом координат. Я считаю, что полученная нами картинка — это почти половина понимания задачи. Она позволила в реальном времени следить за поведением объектов и, сразу же “по картинке” видеть проблемы и недочёты. Несколько примеров:



В последний день контеста я уже был порядком измученным и мозг отказывался проводить сколь-либо сложные операции, потому мои действия ограничивались обсуждением в командной конференции и мелкими фиксами.
Таким образом на момент заморозки таблицы результатов — за 4 часа до конца соревнования — наша команда Concrete Mixers занимала 32-е место из 317, получивших положительное количество очков. Мы считаем, что это вполне удовлетворительный результат, как для первого раза. Конечно, получено немало уроков, сделаны выводы.
Если подрезюмировать все ощущения за эти выходные — получится следующее:
не понравилось:
  • местами, было похоже на олимпиаду по физике
  • организация местами подкачала (9 версий спек, заDoSеный вначале сайт, ошибки в коде)
  • мне показалось, что в прошлых годах было интереснее (icfpc уже не тот =) )
понравилось:
  • тонны ”фана”
  • посмортел, как делать вм, как питоном генерировать питон-код и использовать его
  • познакомился с астродинамикой :)
  • пообщался вдоволь с интересными людьми — сокомандниками и другими участниками
И да, решил дальше учить хаскель!
Пара отчётов от сокомандников:
Остаётся только оставить для интересующихся ссылку на хоумпагу команды, на которой вы можете найти исходники решений, и линк на репозиторий

Комментариев нет:

Отправить комментарий