• Имя команды: Concrete mixers
• Итоговый балл: Weighted Total Score 2852.2285 (14 problems solved)

Начало

Узнал я про проведение ICFPC в течении 27-30 июня внезапно и всего за пару дней. Отправился в конференцию pythonua@cjr, и быстренько нашёл там среди знакомых имён тех, кто собирался участвовать. Собирались мы в секретной комнате на том же conference.jabber.ru :) Это был наш первый опыт участия в ICFPC, а для меня — и вообще в подобных соревнованиях (xa4a и tilarids уже участвовали в Sapka contest). Забегая наперёд, я думаю, что справились мы очень хорошо, даже отлично и должны быть где-то в первых 10% итоговой таблицы. Конечно, теоретически можно было и лучше выступить, но теоретически все могли лучше выступить :)

День 0, вечер

xa4a заранее создал приватный репозитарий на битбакете. Контест начинался в девять часов по киевскому времени, и, конечно же, ровно в девять его сайт практически перестал работать и или отваливался по таймауту, или выдавал страничку в течении пары-тройки минут. Кто-то из первых скачавших спецификацию сразу выложил её на зеркале и показал ссылку в irc-канале #icfp-contest@freenode, поэтому особых проблем с получением задания не было. На сам сайт первым пробился tilarids через несколько минут после начала, и зарегистрировал нашу команду — мы были уже 129-ми.

Суть задания — нужно управлять спутником на околоземных орбитах. Чуть больше часа мы читали задание, вникали в суть и обсуждали как это нужно делать. Если вкратце — у нас есть двумерное пространство (x-y), в котором у нас есть Земля и спутники. Всего четыре типа заданий, и для каждого есть четыре разных набора данных:

• Перевести спутник с одной круговой орбиты на другую. Задание засчитывается после 900 секунд полёта в пределах одного километра от заданного радиуса.
• Состыковаться со спутником на другой круговой орбите. Задание засчитывается после 900 секунд полёта в радиусе одного километра от цели.
• Состыковаться со спутником на эллиптической орбите, причём стартовая орбита тоже может быть эллиптической. Засчитывается так же, как второе.
• Пролететь в радиусе километра от одиннадцати спутников. Держаться 900 секунд возле каждого не нужно.

Организаторы выдали три бинарника — соответственно пёрвым трём типам задач, которые нужно выполнять на виртуальной машине, и собственно спецификацию к виртуальной машине, форматам файлов, и всему прочему. VM элементарна — четыре арифметические операции, операции сравнения с нулём, копирование данных и ввод-вывод. Четвёртый бинарник пообещали выдать спустя сутки — после окончания lightning round.

Где-то в 22:20 я начал писать парсер бинарников, через двадцать минут он был готов, а ещё минут через пятнадцать в нём были выловлены все допущенные ошибки :) Ещё через час (в полночь) у меня уже был готов базовый вариант виртуальной машины — хотя я писал её первый раз в жизни :) VM запустилась, и смогла выполнить каждый из бинарников не упавши. Ура!

Спецификация написана в некоторых местах очень мутно, и спустя час была уже третья версия — в соответствии с которой я исправил и свою VM. Всё это время мы параллельно обсуждали как управлять спутником, какой должен быть интерфейс общения решателей проблем (надо было их называть мистерами Вулфами ;) ), виртуальной машины и чего-нибудь ещё буде оно появится.

Получилось так — есть порты для входящих данных, и есть для исходящих. Даём виртуальной машине входящие данные, исполняем полностью весь код задачи и получаем исходящие данные. Каждый такой проход — секунда внутреннего времени. В портах ввода мы задаём номер задания (только для первой итерации), а также задающие воздействия на актуаторы — двигатели нашего спутника. Ускорение, которое произойдёт в течении последующей итерации — то есть, разница скоростей между временами t и t+1 задаётся в м/с и указывается вектором — отдельно для координат x и y. Например, мы можем сказать спутнику — «по оси x изменить скорость на 40 м/с, по оси y — на 452,4 м/с».

В выходных портах мы можем прочесть заработанные очки, количество оставшегося топлива, свои координаты и радиус целевой орбиты. Оставшееся топливо меряется просто напросто в м/с — удобно. Заработанные очки равны нулю, пока ничего интересного не произошло, -1 если у нас закончилось топливо или спутник погиб при ударе о Землю, и какому-то определённому числу, если мы выполнили задание. Они зависят от количества использованного топлива и от времени выполнения задания.

Для подсчёта очков на сервер загружаются трейсы — файл с определённым заголовком, в котором указаны идентификаторы команды и задания, и список входных портов: как и когда они изменялись.

В общем, ещё спустя минут сорок-пятьдесят усилиями xa4a мы увидели картинку в гнуплоте, а усилиями tilarids у нас был визуализатор на pygame, с анимацией и наблюдением в реальном времени. Рисовало как наш спутник летает вокруг Земли, и толстой зелёной линией целевую орбиту. Красота! :)

В то самое время у некоторых людей из конференции icfpc@cjr VM была в зачаточном состоянии и они ещё даже не пытались её запускать. В этот момент я порадовался что мы продвигаемся достаточно неплохо и отправился спать.

День 1

Я проснулся в половину восьмого утра и пошёл смотреть что же успели накрутить товарищи за то время, пока я спал. Оказалось, что у нас за ночь появился нерабочий логгер трейсов и код, который пытался перевести спутник между орбитами по Гоману… Но спутничек почему-то не долетал пару тысяч километров до нужного радиуса. Тем временем спецификации выросли уже до седьмой версии, да так, что опять пришлось исправлять VM :)

Ещё за час я в несколько раз ускорил визуализатор tilarids’а и поменял константы (гравитационная постоянная, масса Земли) в считалке орибт — там использовались данные из реального мира, а нужны были такие, как в спецификации. Таким образом мы получили решения для трёх задач — 1001, 1002 и 1003. В четвёртой задаче спутник изначально вращался в другую сторону, что создавало некоторые проблемы для того решения, что было, и я решил пока переключиться на второй тип задач.

К полудню начали активизироваться другие участники, и у нас появилось решение для 1004-й, потом появился рабочий логгер — и мы заслали на сайт решения для всех задач первого типа. А к трём часам дня подоспел подарок от tilarids’а — он переписал за полчаса-час виртуальную машину с обычного интерпретирования на генерацию питоновского кода, чем ускорил её раз в десять-двадцать :)

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

• Применять специальные методы-фазеры. Если мы опережаем цель, то нужно выходить на внешнюю орбиту, если отстаём от неё — на внутреннюю. Чем ниже орбита, тем быстрее по ней движется спутник и тем меньше длина орбиты, ну и наоборот :)
• Ждать некоторое время на своей орбите, и в чётко выверенный момент начать переходить на целевую орбиту.

Из-за того, что управление у нас дискретное, а скорости значительные (единицы километров в секунду), то в некоторых случаях погрешности на выходе составляли не сильно удобоваримые единицы километров — а нам нужно находиться ближе километра! При помощи таких-то слов и ручной подстройки времени отлёта (плюс-минус 1-3 секунды) в двух задачах из четырёх я смог подобраться на расстояние меньше километра и продержаться так в течении 1200 секунд… И ничего! Никаких очков нам это не давало! В #icfp-contest и icfpc@cjr наблюдалось несколько человек с подобными проблемами, причём в icfpc@cjr был даже человек, который подбирался к цели буквально на расстояние в миллиметр — и крутился так в течении многих тысяч секунд, и никакого результата это не давало.

Кстати, в некоторых случаях метод задержки давал ошибку в 350 километров, что значительно — ошибался со временем старта почти на 300 секунд. В чём может быть проблема мы так до самого конца соревнования и не поняли, а жаль.

Потратив несколько часов чуть ли не на биение головой об стенку, около семи часов вечера я нашёл корень проблемы. И он оказался в мутной спецификации — оказалось, что на самом деле нам указывается сдвиг Земли относительно спутника, а не сдвиг спутника относительно Земли. То есть, наши координаты нужно инвертировать по знаку. После того, как я это сделал пришлось ещё починить определялку направления вращения. Ну и, естественно, нам стали давать очки за вторые задания, которые мы тут же отправили на сайт.

Приблизительно в это же время выяснилось, что организаторами в первой задаче была допущена ошибка в подсчёте очков — там давали больше очков за сжигание топлива, а не за его сохранение. Вместо того чтоб подправить задание, орги подправили спецификацию — оригинальный путь :) Некоторые люди обсуждали стратегии выжигания топлива аж до конца третьих суток. Предлагали выходить на далёкую орбиту и потом возвращаться на целевую, предлагали дёргать орбиту туда-сюда внизу под тем предлогом, что внизу скорости больше и затраты топлива тоже будут больше… Я сделал самое очевидное — вышел на нужную траекторию, разделил всё оставшееся топливо на две части, и сделал два импульса — половиной толкнул вперёд, половиной толкнул назад, за пределы допустимого километра такой манёвр спутник не выбросил, и отлично. Так мы получили за первые задания 95-96 баллов вместо 60-67 начальных.

Мы начали экспериментировать с разными трансферами и третьим заданием, где-то в этот момент закончился lightning round — к сожалению, в его топ20 мы не вошли, и на тот момент таблица результатов была только для топ20, полную вывесили гораздо позже. Мы набрали где-то 945 баллов, а для попадания в топ20 нужно было около 1100. Минут через двадцать выложили бинарник для четвёртого типа задач, и в очередной раз обновили спецификацию — оказывается, там ещё и Луна есть в четвёртом. xa4a начал рефакторинг наших тупых решателей в более-менее удобоваримые state-machine — до этого у нас был просто метод run() с циклом и переменной state, и длинной простынёй условий, потом начал делать негомановский трансфер.

Я всё это время ещё медитировал над хоть каким-то стабилизатором орбиты или чем-нибудь подобным. К полуночи я придумал и написал совершенно убогую хрень, которая, тем не менее, смогла как-то догонять цели, которые летели в нескольких километрах от нашего спутника и у нас были решения для всех четырёх задач второго типа — это выразилось в увеличении счётчика баллов до 1127 очков. Я ещё минут двадцать пообщался в разных конференциях и около часа ночи опять отправился поспать.

День 2

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

Я скачал и начал изучать замечательную книгу Orbital Mechanics, которая к тому моменту была уже у всех, кто хотел :) Потом мы решили провести ещё один рефакторинг и собрать весь код в одном месте, плюс к тому я написал удобную запускалку, которая вызывалась просто как ./run.py <task number>. Я ещё написал контроллер-визуализатор для четвёртой задачи, который пока ничего не делал. Но зато он мог показывать все одиннадцать спутников и их траектории движения, собранные спутники выделял другим цветом и даже рисовал где находится заправочная станция.

Да-да, в четвёртой задаче была заправочная станция — если пролететь мимо неё, то она восстанавливала запас топлива в баках нашего космического коня :) В этом задании топлива у нас было не в пример меньше. Луну рисовать я обломался, потому что в большинстве случаев она была далеко за пределами изображаемой области. Такой мы выбирали масштаб, чтоб было видно более подробно что же происходит в околоземном пространстве.

Информацию о всех искусственных и натуральных спутниках Земли, в том числе и АЗС мы доставали из всё тех же портов вывода. Там указывались все координаты относительно нашего управляемого спутника, “поприветствован” спутник или нет, запас топлива на орбитальной АЗС и координаты Луны тоже. На всякий случай уточню — все спутники кроме управляемого летают по одним и тем же траекториям и никак не пытаются упасть на Землю, сгореть в Солнце или отправиться колонизировать Марс или Альфу Центавру :)

Практически весь оставшийся день мы все втроём усиленно читали Orbital Mechanics, пытались как-то определять параметры орбиты, пытались как-то переходить между эллиптическими орбитами и ещё всякая такая муть. У нас ничего не получалось, там постоянно вылазили проблемы с углами, куда что направлено, что где считать и всё такое. Где-то к половине второго меня осенило, и я вспомнил что в питоне есть встроенный тип данных — комплексные числа. С их помощью очень легко производить все векторные вычисления на плоскости, определять углы, радиусы и т.п. На их основе я за полчаса сделал отличную догонялку под названием naive_chase(), которая презрев все законы астрофизики просто напросто летела в сторону цели. Работает догонялка так:

• определяет векторные скорости цели и управляемого спутника;
• вычисляет разницу скоростей, которую нужно скомпенсировать для того чтоб выравнять их скорости, то есть результирующие векторы скоростей будут направлены в одну сторону
• добавляет к этой разнице небольшой вектор в сторону цели (3..50 м/с в зависимости от расстояния);
• ждать пока не догоним, если расстояние начало увеличиваться — пересчитать и скорректировать траекторию.

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

В результате её применения к 2002-й у нас выросло количество очков с 1127 до 1133, потом ей же решил 3001 и 3004 — получилось 1897 баллов, и ещё 3002 и 3003, и улучшенные 3001 и 3004 — 2364 балла! За двадцать минут мы резко рванули вверх в турнирной таблице :) И опять на такой радостной ноте я пошёл отдыхать :)

А если не делать никаких задержек, и включить сразу Гомановский переход, а потом догонялку, то получилась бы такая картинка.

День 3

Проснувшись с утра, я увидел, что наши результаты за ночь ещё чуть-чуть улучшились, и я ещё чуть-чуть покрутил решения третьих задач, получив 2588.7917 очка и 21 место в таблице — из трёхсот.

Опять почти весь день мы пытались что-то сделать с математикой определения эллиптических орбит и перехода между ними, я пытался развернуть спутник на 4004 задаче… Кстати о развороте спутников, есть несколько способов (для круговой орбиты):

• На месте где находится спутник просто развернуть тангенциальную скорость (касательную). Для этого нужен импульс, равный двойной скорости. В 4004-й спутник на старте летел по низкой орбите со скоростью около 7 км/с — импульс нужен величиной в 14 км/с, а у нас топлива есть только на 10 км/с. При попытке развернуться - фейл.
• перейти на вытянутую эллиптическую орбиту и где-нибудь в средине обратного движения переломить траекторию на другую эллиптическую орбиту, и обойти Землю с другой стороны. Таким образом основную работу по развороту мы перекладываем на Землю — чем-то похоже на гравитационную пращу. Метод применить не удалось — опять запутался в математике.
• Выйти на вытянутую эллиптическую орбиту и в её апогее опять же развернуть тангенциальную скорость. Можно легко совместить с переходом на другую орбиту — очень похоже на би-эллиптический переход. Топлива требуется значительно меньше, чем в первом варианте — раза в два-три (чем более вытянутая орбита, тем меньше топлива)

Я смог без особых проблем реализовать третий метод, но ничего на его основе я уже сделать не успел. За четыре часа до окончания контеста таблицу с достижениями заморозили, и уже никаких движений видно не было. Последние часа два-три мы пытались хоть что-то подкрутить и заработать хоть какие-то очки в дополнение к тем, что были, и нам кое-что удалось — мы поймали три спутника в 4001 и два спутника в 4003 задании, что выразилось в итоговых 2852.2285 баллах.

Да, в четвёртом задании не обязательно было ловить всё — нужно было поймать хоть какой-нибудь спутник. Последний спутник (третий в 4001) поймал tilarids и закинул на сайт буквально за несколько минут до окончания контеста. Всё, хана! :-D

Итоги подведём

Море фана, удовольствие когда что-то начинает получаться и летать, и всё такое. Что можно было сделать лучше:

• раньше вспомнить про комплексные числа;
• попытаться во все формулы вручную подставлять числа и смотреть, что же там не так;
• было бы неплохо всем вместе находиться в одном месте — если бы можно было обсуждать математику с маркером у доски, а не переписываясь по джабберу, то было бы гораздо проще.

Я считаю что мы выступили отлично, и особенно — как для первого раза. Если кроме нас особо никто за последние четыре часа ничего не придумал, то мы заняли 21 место, но это вряд ли. Так что, учитывая некоторое творчество других команд, я думаю что мы занимаем где-то 25-30 место (из 320). Ура! В следующем году тоже постараюсь поучаствовать.

P.S.Отчёт tilarids, xa4a.