Тексты

  Тексты:

Пхова 2004
ICFPC 2007
ICFPC 2008
Sapka 2009
ICFPC 2009
ICFPC 2010
Защита от взлома

  Переводы:

Природа Будды
Махамудра



Если обнаружите в тексте ошибку, выделите ее мышкой и нажмите Ctrl-Enter.

ICFPC 2009

29 июня 1995 года в 13 часов 0 минут и 16 секунд по Гринвичу состоялась первая стыковка шаттла Атлантис и космической станции Мир.
29 июня 2009 года в 13 часов 0 минут и 16 секунд по центральной временной зоне закончилось соревнование ICFP Contest 2009, в котором участники должны были управлять космическими аппаратами, производя всякие орбитальные маневры и стыковки.

Задание

Опубликованное за 72 часа до этого знаменательного момента задание содержало описание несложной виртуальной машины, задающей процесс вычислений, и несколько бинарных исполняемых файлов для этой ВМ, моделирующих движение спутников в разных задачах. На каждом шаге моделирования ВМ получала некие входные значения (такие как моментальные изменения скорости) и выдавала некие выходные (например, относительные координаты спутников, остаток топлива, набранные очки). Для каждой задачи участники должны были сгенерировать такую последовательность входных значений, которая, будучи подана на вход ВМ, заставляет наш спутник проделать нужный маневр. Если цель маневра достигнута, то по описанной в задании формуле в зависимости от потраченных топлива и времени вычисляются очки. Очки за разные задания умножаются на коэффициент сложности и суммируются, определяя общий балл команды. Таким образом получается объективный критерий оценки решений, и нет привязки ни к какой платформе или языку, т.к. на сервер организаторов посылается лишь файл с командами, а уж как он получен - не важно. Основных заданий было 4, в каждом по 4 разных набора исходных значений (сценария).

Процесс решения

С учетом моего часового пояса соревнование для меня началось в час ночи в субботу. Прочитав задание, я отправился спать и засел за решение лишь за 12 часов до конца первых суток (решения присланные в первые 24 часа участвуют в отдельном Lightning round'e). Участвовал опять в одиночку, а в качестве рабочего языка программирования опять выбрал OCaml. Написать на нем простой интерпретатор ВМ получилось очень быстро, поэтому я сразу потратил еще время на то, чтобы его ускорить. Две оптимизации, детали которых описаны отдельно здесь, позволили ускорить ВМ в 2,5 раза и получить на первой задаче скорость 650 000 итераций в секунду (одна итерация - 266 команд) на процессоре в 2,33 GHz.

В первой задаче нужно было перейти с текущей круговой орбиты вокруг Земли на другую круговую орбиту и оставаться на ней (в пределах километра от заданного радиуса) без использования двигателя в течение 900 секунд. Прямо в задании была ссылка в википедию на маневр, описанный в 20-х годах Вальтером Гоманом (Hohmann, так и хочется назвать его Хохманом :) и Владимиром Ветчинкиным. Маневр состоит из двух моментальных импульсов, в первом из которых мы с круговой орбиты переходим на эллиптическую, один конец которой проходит через первую орбиту, а второй - через вторую. Второй импульс производится в противоположной точке эллиптической орбиты и переводит нас на искомую круговую.

Во многих ситуациях данный маневр является наиболее экономным по топливу. Формулы для этого маневра очень просты и описаны в интернетах многократно:

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

Такой подход позволил получить на каждом из 4 вариантов первой задачи не менее 95 очков из 100 возможных. Однако поиск хороших параметров для подруливания на орбиту и первого импульса занял у меня очень много времени, на первую задачу я убил 2 первых дня. Когда мой спутник только учился рулить, выяснилось, что вместо ускорения он тормозит. Оказалось, что у меня неправильно использовались координаты - на вход поступают не координаты спутника относительно Земли, а наоборот, это не влияет на расчеты геометрии, но влияет на ускорение. Решил обойти очень просто - при подаче команды двигателям менял знак вектору изменения скорости. Потом когда нужный маневр делать получилось, реализовал запись последовательности команд в файл в том виде, в котором нужно посылать решение на сервер организаторов. Посылаю такой файл, а сервер возвращает CRASHED. Это может значить что угодно - неправильный формат файла, непроинициализированный сценарий, перерасход топлива или столкновение с Землей. Довольно скоро причина была найдена - при записи трассы забыл инвертировать знаки, в результате мой cпутник тормозил вместо разгона и падал на Землю.

Во второй задаче нужно было не просто выйти на другую круговую орбиту, но состыковаться там с другим спутником. Задача считалась решенной, если в течение 900 секунд подряд наш спутник без использования двигателей находился в пределах километра от второго спутника. Оценивались экономия топлива и времени. Тут уже отлично подходил переход Гомана, и оставалось лишь выбрать правильный момент для начала маневра. Изначально оба спутника двигаются по разным круговым орбитам и следовательно имеют разную угловую скорость. Переход Гомана составляет ровно 180 градусов, поэтому нужно лишь дождаться момента, когда спутники будут в 180 градусах друг от друга относительно Земли. Угловые скорости вычисляются элементарно, и момент старта маневра тоже легко вычисляется аналитически. Реализовал этот алгоритм, мой спутник подлетает ко второму, крутиться с ним на орбите достаточно долго, а задача все никак не засчитывается. Стал разбираться, оказалось, что я при переводе относительных координат второго спутника в абсолютные ошибся порядком операндов и в результате гонялся за призраком, в то время как на самом деле второй спутник был с другой стороны от Земли. Исправил, все заработало как надо.

В третьей задаче тоже нужно было состыковаться с другим спутником, но теперь он летал по эллиптической орбите. Хорошего аналитического решения я не нашел, поэтому пошел по такому пути. Сначала мой спутник методом Гомана переходил на круговую орбиту, вписанную в эллипс орбиты второго спутника. Там моя угловая скорость была намного больше, чем у другого спутника, и крутясь на ней, можно было дождаться момента, когда расстояние между ними будет минимальным. Таковой момент находился путем простой симуляции на 3 миллиона секунд вперед ( максимальное время для задачи). Дальше мой спутник дожидался этого момента на этой вписанной орбите, после чего начинал сближение со вторым, установив свою скорость равной скорости второго спутника плюс некая дельта, обеспечивающая сближение. Когда спутники оказывались достаточно близко, включался переборный поиск оптимального вектора изменения скорости, который бы привел к наиболее продолжительному полету в пределах километра друг от друга.

Единственное затруднение возникло в одном из 4 вариантов: траектория сближения проходила через Землю. Пришлось писать отдельную логику, отслеживающую, не проходит ли планируемый вектор скорости через Землю, и корректирующую его для облета родной планеты.

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

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


© Dee Mon, 2004-2010.