Отчет участника Rst7

(san) Эссе о пользе математики

(san) Новые подробности детектива.

Formal report in English

Отчет участника Rst7

Итак, ICFP 2009 Programming Contest завершился. По результатам на 4 часа до окончания контеста наша команда занимает второе место . Однако, десять решений, попавших в десятку  лучших, организаторы еще будут тестировать на предмет универсальности, а не заточенности под конкретные исходные данные.

Я не буду рассказывать, что есть ICFPC (есть гугл), а попробую по горячим следам в двух словах описать ход нашей работы над проектом.

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

…День нулевой…

Собравшись вечером 26го июня и вытащив спецификацию, мы увидели что орги приготовили нам следующее развлечение:

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

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

в) Собственно задания (”проблемы”) - переход с одной круговой орбиты на другую; встреча со спутником, болтающимся на другой круговой орбите; аналогичная встреча, но орбиты могут быть эллиптическими; и последняя жесть - облет десятка спутников, при этом в мире есть Луна и один из спутников летает вокруг нее.

г) Имелась система начисления очков за выполнение заданий - была некая пропорция между затраченным временем и израсходованным топливом - где-то между крайними случаями лежал оптимум с максимальным количеством очков. Правда, орги допустили баг в подсчете очков за выполнение первого задания, и топливо было выгодно сжигать целиком. Что, собственно, особо не влияло на конечный результат, если изначально оптимизация траекторий велась по максимизации количества очков (требовалась только замена весовой функции, что и было проделано).

д) Результаты надо было сабмитить на сервер оргов в виде лога своих команд, посылаемых через порты ввода в виртуальную машину. Собственно, сервер прогонял решение на референсной VM, и, согласно полученному количеству очков, устанавливал место команды в топлисте.

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

В качестве исходного толчка для тех, кто вообще не в курсе дела, был приведен пример перехода с круговой на круговую орбиту по гомановской траектории - это случай минимального импульса, но максимального времени выполнения маневра.

Итак, задание было раскуренно и мы приступили. Сразу же было принято решение делать не VM в обычном смысле этого слова, а произвести трансляцию бинарного кода в исходный код на Java, затем банально выполнять уже его.

В течении первых нескольких часов был написан компилятор и визуализатор - теперь стало возможным увидеть, что происходит в мире. Где-то в этот момент я отправился спать.

…День первый…

Далее началась имплементация гомановского перелета и обсуждение последующих задач (по мере продвижения решения первой проблемы).

В этот момент я немного отстранился от обсуждения/педаленья для того, чтобы вспомнить все, что мне известно об астродинамике. В детстве/юности было прочитанно достаточно много книг по этой тематике с возрастающим уровнем сложности. Последняя книга, попавшаяся мне лет пять-семь назад, была “Механика космического полета в элементарном изложении” и была тогда с удовольствием прочитана. Собственно, в этой книге были разобраны вопросы с качественной точки зрения (ведь “в элементарном изложении”), теперь пришло время количественного решения задач. Кроме того, рассудив здраво, я понял, что практически проблема с большим номером включает в себя решения проблем с меньшим номером.

Примерно помня, какие методы применяются профессионалами для проектирования орбит, и освежая память гуглем, было найдено несколько серьезных книг по астродинамике (как буржуйских, так и наших), в которых было дано описание решения проблемы Ламберта.

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

а) Выбиралась длительность перелета.

б) Запуском VM с текущего состояния на время, равном длительности перелета, находилось положение конечной точки.

в) Положение начальной и конечной точки плюс время скармливалось решателю проблемы Ламберта, на выходе имели два вектора скорости.

г) Собственно перелет представлял из себя сообщение нашему спутнику импульса, равного разности текущего вектора скорости и вектора скорости в начальной точке траектории перелета (это нам вернул Ламберт, после импульса мы выходим на траекторию перелета), затем ожидание (то самое время, которое мы выбирали на этапе “а”), и сообщение выравнивающего импульса, равного разности текущей скорости в конечной точки и скорости цели (т.к. до цели мы уже долетели, разность координат стремится к 0, осталось только выровнять скорость). Благо, было совершенно пофиг, весь импульс (хоть 50км/с) можно было приложить за один тик мира (1 секунда). Кроме того,  в этом виртуальном мире топливо ничего не весило ;)

Однако, сначала я решил исследовать поведение решателя проблемы. Был взят MATLAB и сделан первый вариант, подсмотренный в Atmospheric and space flight dynamics

К сожалению, код, приведенный в книге, правильно расчитывал тестовое задание (приведенное там же), но почему-то дико глючил на тестовых векторах из нашего мира. Было найдено еще несколько алгоритмов в других книгах, различающихся в деталях решения и, в конце концов, родилась собственная имплементация (пока на MATLAB’е) - основное отличие - использование половинного деления в итерациях, а не метода Ньютона, который почему-то плохо сходился.

Где-то в этот момент я отвлекся (для отдыха) и помог в решении проблемы неточности прилета нашего спутника в конечную точку по гомановской траектории. Был заимплементен алгоритм, который банально доруливал до нужной орбиты и выравнивал скорость. После чего вернулся к проблеме Ламберта. Краем уха и глаза я наблюдал, как SAS и Brox пытаются комбинацией гомановских перелетов решать вторую и третью проблемы.

Исследования поведения проблемы Ламберта при различных входных t (с постоянными радиус-векторами на входе) показало, что имеются различные минимумы требуемых импульсов. Было принято решение заимплементить простой перебор времени перелета и найти максимальный счет (функция от времени и суммарного требуемого импульса). Кроме того, имело смысл ввести  дополнительную регулируемую задержку первого включения двигателей для поиска оптимального “стартового окна”.

В этот момент, я нашел нужным объявить всем, что у меня в общих чертах готов универсальный алгоритм, который позволит решить нам все четыре проблемы:

а) Проблема номер один - вешается псевдоспутник, и производится перелет на него (несмотря на то, что первая проблема на данный момент была решена общими усилиями других членов нашей команды).

б) Проблема номер два и три - для моего алгоритма не отличаются.

в) Проблема номер четыре - требует просто бизнес-логики как надстройки над моим алгоритмом - в простейшем случае просто десять последовательных перелетов либо какой-то более умный выбор последовательности (что и было в конце-концов заимплементено).

После некоторого сопротивления, я заставил San’а бросить твиканье текущего решения и заняться имплементацией моего алгоритма. Примерно через час-другой алгоритм заработал и начал приводить нас к цели с довольно приличной погрешностью (километры) (что и было закомиченно на svn San’ом в виде ревизии 874 с весьма льстящим мне комментарием). Что вообщем-то меня не очень испугало, так как я четко понимал, что результаты интеграции уравнений движения (расчет мира в виртуальной машине) и расчет кеплеровского эллипса (проблема Ламберта) не будет сходится с достаточной точностью. Посему, San’у была дана команда заимплементить коррекцию нашей траектории (которую нам дал Ламберт) любым удобным способом - например, градиентным спуском по результатам симуляции траектории. Сам я отправился спать, а под утро San сообщил мне, что все готово (и теперь настала его очередь отдыхать).

…День второй…

Примерно к обеду моя тестовая “кровать” (RstTestBed.java) вполне хорошо решала проблемы 2 и 3 и было принято решение переходить к проблеме 4. “Кровать” так и осталась в проекте до конца, как платформа для решения всех задач.

Для получения вменяемых результатов по быстродействию было принято решение закэшировать положение всех других спутников в течении 3х миллионов секунд (это ограничение сверху на длительность решения проблемы, которое фигурирует в условиях). После этого поиск траектории через решение проблемы Ламберта стал весьма быстр и появилась возможность производить выбор спутника для посещения с точки зрения максимизации счета. Однако, после этого недостаток быстродействия стал вылезать процедуре finetuning’а траектории методом градиентного спуска. Было принято злое решение - захачить непосредственно код оргов для виртуальной машины, чтобы он считал исключительно нашу траекторию, а другие спутники не считал (ведь их положение не зависит от нашего поведения и они закэшированны). Я попробовал было врукопашную захачить java-код, который был сгенерен компилятором из бинарника, однако, удовлетворительных резульатов полученно не было, и San предложил реализовать создание дерева всех референсов регистров данных внутри бинарника, после чего “заказать” компилятору компиляцию только того кода, у которого есть референсы (вложенные в том числе, конечно) к интересующим нас регистрам. Через пару часов результат был получен - примерно десятикратное ускорение расчета градиента. Так как такое решение пахнет отсутствием универсальности, Brox занялся изготовлением тулчейна для получения кастрированных виртуальных машин по заказу, что и было выполено ближе к концу соревнования. Теперь наш код собирается скриптом с автоматической компиляцией нужного кода. А мы в это время продолжили свои занятия: San - имплементацией greedy-алгоритма поиска наилучшей последовательности облета спутников, я - довел до ума задачи 2 и 3 - теперь можно было полностью избавиться от доводчика в нужную точку в конце траектории - импульс торможения теперь учитывался при градиентном спуске, что дало свой результат - попадание в заданную окрестность (мы приняли 200 метров, достаточно было 1км) с ошибкой по скорости в пятом знаке.

Правда, иногда метод градиентного спуска плохо сходился, и было принято решение ввести коррекции - если за вменяемое время результат finetuner’а не получен, то оптимизация прекращается, производится пролет по наилучшей пролученной траектории половину расчетного времени и опять выполнение  нашего алгоритма (ламберт,  градиент, и т.д.). В результате мы научились делать коррекции траектории в процессе полета. Причем, обычное значение импульсов в точках коррекции были порядка 0.5-10м/с. В общем, схемы полетов, генерируемые нашим софтом, стали очень походить на схемы полетов  больших братьев из реального мира. Это лично мне добавило количество полученного fun’а.

В этот момент орги заменили четвертый бинарник - оказалось, что Луна не гравитировала. При использовании нашего алгоритма на новом бинарнике неучет Луны приводил к разбиванию о ее поверхность. Было принято решение заимплементить переключение системы координат при решении проблемы Ламберта из геоцентрической в селеноцентрическую, если наш спутник находился в сфере действия Луны. San был отправлен спать, Brox и я занялись внесением необходимых перерасчетов. Часа в четыре утра Brox отправился спать, а я продолжил и в 7.28 утра третьего дня закомитил полеты с учетом Луны. При этом, если траектория пересекала границы действия Луны, то происходило переключение системы координат и перерасчет остатка траектории в  другой системе. После чего поднял San’а и Brox’а, доложил им результаты и рассказал про мегажопу - летать мы летаем, флаги посещения спутников в портах вывода виртуальная машина выставляет, а счет - не ведется - летаем впустую! Баг надо было найти и зафиксить, но это легло на плечи San’а, SAS’а и Brox’a - сам я ушел спать с требованием разбудить меня или около трех часов дня (~6 часов сна для очищения головы, если вдруг товарищи не справятся с фиксом и понадобится свежий взгляд) или воплями об удачном фиксе бага (тогда можно просыпаться, вроде особых проблем впереди не будет).

…День третий и последний…

Полдня я проспал, был разбужен воплями о фиксе (оказалось, что замена printf(”%G”) в компиляторе VM на прямой ввод бинарных данных проблему решил), спросил - “какие-то проблемы сейчас есть?”, получил отрицательный ответ и доспал до трех часов дня. Проснувшись, выпив чашку кофе и покурив (табак! не подумайте;) ), я решил посмотреть, кому какая помощь нужна.

Оказалось, что SAS решил допилить проблему номер один под использование решения проблемы Ламберта, однако, кое-что у него не получалось и мы общими усилиями довели дело до ума. При этом был получен максимальный счет - 97 очков за подзадание (хотя, многие в конференциях утверждали о 96ти очках максимум).

San засабмитил на сервер оргов все подрешения четвертой проблемы - в результате мы вышли на первое место в топлисте с суммарным счетов в 5025 очков. Правда, через некоторое время появилась команда (человек?) pepsiso, у которой суммарный результат был 5171, и мы спустились на второе место. Где-то в это время общая таблица перестала обновляться, и дальнейшую смену мест мы не знаем.

Затем SAS и я допилили решение проблем 2 и 3 для получения максимальных результатов. Однако, выигрыш был невелик, буквально, 2-3 очка (проблема оказалась в неточном соответствии нашей функции подсчета очков и функции, имплементированной оргами в виртуальной машине) (счет достиг 5036 очков).

В общем, возврат на первое место на данный момент зависел только от San’a, который оптимизировал перебор спутников - там можно было вполне выиграть 150 очков. Все подключились к решению задачи, однако, в последние часы более оптимального алгоритма полученно не было - оказалось, что иногда очень медленно сходится градиент и нам просто не хватило времени на вычисления.

Собственно говоря,

…21 час по киевскому времени…

был встречен без каких либо воплей разочарования - “ну второе место, так второе”, кроме того, еще предстоит запуск решений оргами на других задачах, там посмотрим, как себя поведут наши и чужие алгоритмы…

Следует небольшой релакс, первое спокойное обсуждение и подведение итогов - все сошлись во мнении, что каждый получил достаточную дозу fun’а. Ну, как собственно и планировалось.

И на посошок, лично мои общие впечатления:

а) Мы (как команда) уже третий раз участвуем (ICFPC2008, Sapka и уже прошедший ICFPC2009) - каждый раз ощущения от происходящего все лучше и лучше. Кроме того, намного лучше расчитали свои силы. И я, торжественно пообещав в самом начале, что тупить не буду (как на ICFPC2008 - ниасилил не то, что заимплементить, а даже подумать о применении банального PID-регулятора для управления ровером), свое обещание выполнил - выдал универсальный алгоритм, который лег в основу решения всех проблем.

б) Отрицательные впечатления о стиле программирования “пишем скелет функции, втыкаем точку останова, запускаем и допиливаем все на ходу”. Именно такой стиль программизма у San’а. Я так не могу, не хочу, не буду и вообще - “Это не наш метод!” (С).

from San:

это один из двух подходов к решению задач. Вначале наблюдаем, потом обобщаем, потом автоматизируем (алгоритмизуем). Именно так мы видим нерегулярность работы градиентного спуска, проблемы, которые возникают там, и именно так рождается решение - в руках есть проблема (а не в голове).

в) Зря бросил MATLAB. Надо было поисследовать поведение градиентного спуска.

Но в целом - fun получен, все - rulezzz!

(san) Эссе о пользе математики

Мысли через 2 часа после соревнований:

Вот, организаторы. Из года в год они организовывают соревнования. Они - профессора и доктора: они уже Там, а нас Туда зовут. Как им звать? Они собирают толпу каждый год и дают им задачу. А люди задачу решают, три дня полного погружения, они поворачивают себе мозги. Вот она, дверь в другое измерение, кто можешь - с усилием войди. По эту сторону двери - численные методы, итерации, градиентные спуски и прочие методы ньютона, аппроксимации. А по ту сторону - другое измерение и они - профессора. И то, что у нас делается тысячью итераций, у них делается обобщенным аналитическим методом, в один проход. Человек хочет кинуть камешек, и целится, еще чуток повыше, и еще немного левее, и еще чуть, чуть, чтобы закинуть камень в дырку. У него это его нынешний опыт, более удобного способа простой кодер считай и не знает. Перелет и недолет. А в это время математик берет силу гравитации, массу камешка, расстояние и высоту до мишени, и сразу имеет ответ, без итераций. Он работает с высокими материями. Это позволяет ему ныне заниматься более интересными вещами, а не чуть-чуть туда или чуть-чуть сюда целиться. Например, математик может сказать, куда пустить бабочку, чтобы она вызвала ураган, чтобы упало дерево и завалило дом, в который целится обычный кодер методом итераций. Это требует, конечно, некоторого напряга, но не того, что у простого люда.

И вот, организаторы. Они пытаются зазвать нас в тот мир, заставить нас вывести законы, или поискать законы, которые избавят нас от итераций. Которые позволят сразу сказать, куда кинуть камень, чтобы сила тяготения, изогнув его траекторию, направила его прямо в шишку на сосне. Они зовут тянут нас к себе, в конечном итоге. А мы-то думаем, что мы соревнуемся так, между собой….

В этом году задание было на небесную механику. Была дана программа, которая вычисляла положение небесных тел (спутников), и вычисляла положение нашего спутника, летящего по тем же законам, и позволяла его немножко контролировать. Задания были перевести спутник на орбиту, подлететь и сопровождать спутник летящий на другой орбите, и затем, облет множества спутников, летающих на разных орбитах. Решением задачи были управляющие команды на спутник. Задача была дискретная по времени, с шагом в 1 секунду и реальными константами из нашего мира.

Понимающие математику! О, они подобны музыканту, берущему нотную запись незнакомого музыкального произведения, и начинающему играть ноты, претворяя их в жизнь. Понимающие математику берут с нужной полочки формулы, и знают, что в них к чему! Для того, чтобы перевести тело из одной любой точки в другую в орбитальном пространстве земли, нет нужды методом приближений искать нужный вектор приложения сил, запуская каждый раз прилагаемую программу, и наблюдая, чем это закончится, а потом чуть-чуть изменять вектор и пробовать еще раз, приближаясь к нужному варианту. Так делаем мы, люди, но не математики. Те лезут в книжки, которых в инете полно, и сквозь дебри интегралов видят то единственное место, которое затем, нависая над нами, объясняют нам, и помогают забить в простую арифметику, ну, с одним маленьким циклом, итераций в 2-5 на вычисление.

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

На этом наш математик (rst7) счел, что его роль как математика закончена. Потому что с его формулой мы избежали самых накладных расчетов. Представьте. сколько нужно итераций для остальных расчетов, и что внутри них еще тысячи других итераций. Без внутренних же как-то проще, и больше сделать можно, так? Но затем, раз формул больше нет, то вернемся к нашим итерациям.

Предположим, вместе с нами по соседней орбите, вытянутой или нет, вращается спутник, к которому нам нужно. Мы находим разнообразными переборами время, в которой нам лучше отправиться, и время, которое нам лучше лететь так, чтобы результирующие импульсы, которые нам нужно давать на старте и торможении, были минимальны, потому что топливо расходуется. Это чистой воды поиск (непростым) перебором, с ограничениями на длину ожидания до стартового импульса (ждать у моря погоды можно вечно) и на длину перелета (потому что время тикает), Взяв интересующие нас t1 и t2, прокручиваем время на t1, получаем нашу исходную точку. Прокручивая еще на t2, получаем спутник назначения в конечной точке. Используя формулу из книги, по двум точкам и по t2 получаем два импульса, которые оцениваем, устраивают они нас или нет. Если нет, то ищем другие. Или может лучше на другой спутник полететь? Так строится маршрут.

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

По некоторым причинам, всё совсем не так безоблачно. Проблемы начинаются с того, что формулы-то не работают до конца точно! Почему? Потому что в четвертом задании присутствовала Луна! Она дает искажения, не учитываемые в формулах.

И приходится… уточнять! Уточнять можно в реальном времени, пролетев половину пути, затем пересчитав, немного повернуть, пролететь половину пути, снова поправить направление итд. Это чревато большим расходом топлива. Поэтому рассчитать можно заранее точно. Это работает почти всегда нормально, кроме некоторых важных случаев, и медленно. Делается это так: в текущий момент состояние мира (организаторской ВМ) копируется, и появляется условная вселенная, в которой мы долетаем по вычисленным параметрам куда долетится, и получаем некоторую разницу. Потом меняем немножко стартовый импульс, и повторяем процедуру. Похоже на описанного выше человека, но делается это один раз, когда уже выбрали куда лететь. Поэтому, как видите, итерации у нас на несколько ином уровне. Зато вот потом, ежели в условном мире мы туда прилетели, в нашем мире мы гарантированно туда попадем.

Об остальном написал Rst7.

После прошлого контеста, с марсианами и ездящими марсоходами, я ходил между людей и чувствовал, как на меня действует инерция, я рассчитывал повороты, я вписывался в коридоры. Я смотрел на мир по другому.

Нынешний контест нас вплотную познакомил с задачами, которые наши продвинутые ученые решали в 50-х годах. Мы почувствовали, что все мудреные названия, которые мы знаем из области космонавигации, они просто имена определенных физических процессов, которые происходят на орбитах, и что при определенной практике к иной физике привыкаешь, и начинаешь размышлять с ее учетом. И я прочувствовал, что математика это действительно измерение высшее относительно нашего мира. Что из этого измерения наше будущее видно отчетливо, как собственная ладонь.

(san) Новые подробности детектива.

Всплывают в памяти новые подробности.

В самом начале в четвертой задаче мы решали задачу минимизации топлива. Это позволяло нам вертеться не спеша вокруг Земли, вылавливая спутники по очереди, и дало высокий счёт. Но больший счет был бы достигнут при более быстром их облете. Было решено сделать следующий вариант: полностью израсходовать топливо, но очень быстро облететь все спутники. Этот вариант требовал возвращения на базу каждый раз после полета к спутнику, потому что полет был наиболее эффективным и съедал всё топливо (почти, чтобы уложиться суммарно). Но возникли проблемы с возвращением на базу (плохо сходился градиентный алгоритм расчета траектории возврата, то есть он иногда сходился очень, неприемлемо медленно). Чтобы минимизировать это “иногда”, я стал решать более полную задачу - летать за спутниками более эффективно с точки зрения по топливу, чтобы 3-4 спутника облететь за один раз. Эта задача была решена, но возвращения на базу остались проблемными - для нахождения точного импулься требовалось слишком много циклов перебора при градиентном спуске.

И сейчас я понимаю, почему. Потому что при возвращении вниз к земле очень малое изменение направления в начале траектории очень сильно влияет на конечную точку вблизи земли. Вспомните, с какой скоростью спутники вращаются вокруг земли! Там время как бы “идет быстрее”.  Оптимальная “дырка” в плоскости решений становится очень маленькой, на порядки меньше, оттого и время для ее решения. Обратная задача, при взлете, или при переходе с орбиты на орбиту - более простая.

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

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

В результате его неиспользования, мы прекрасно облетали 4-5 спутников за один круг (!!! это выглядело великолепно на визуализаторе!!), и залетев однажды на базу (получалось!) набирались топлива, после чего нам надо было поймать следующие спутники, часто на более высоких орбитах (втч вытянутых), таким образом на базу нужно было возвращаться всё чаще (раз 5-6 всего), и на этом месте нас застал финальный свисток.

Далее, баг с посещением всех спутников, но необъявлением нам результатов, о чем Rst написал.  На самом деле баг со счетом состоял в том, что надо было подождать 2 миллиона секунд, пока прийдет счёт. Так что 4-я проблема была таки решена верно, и мы добавили просто ожидание.

В обед третьего дня (см внизу) RST был разбужен решением другой проблемы, а именно:  на сервере организаторов, после сабмита, наши прекрасно решенные проблемы 2000 и 3000 уходили в бесконечность (timeout), что означало, что условие остановки не достигнуто, и спутник улетел мимо, и крутится себе где-то на левой орбите. Нашим возмущениям не было предела: у нас решаются задачи о посложнее, значит VM реализована правильно, а наше решение считается неверным у организаторов. В задачах 4000 мы получали около 260 очков, что означало что мы-таки что-то ловим, но не всё.

Была предпринята попытка проанализировать код VM на предмет ошибок, но буква в букву спецификация сходилась. Была попытка обратить внимание организаторов на вопиющее безобразие. Но они качественно отморозились.

Тогда я понял, что нужна VM сторонних производителей, и пошел на jabber просить милостыню. Там добрая лисперская душа дала мне ссылку на чей-то java интерпретатор (не компилятор), и я его прикрутил, и увидел, что в 4000 задаче нашим решением ловятся только первые 2 спутника, а потом мы гуляем безрезультатно. Это был уже результат: проблема была изолирована. Я стал смотреть код, и он был почти точной копией нашего компилятора. Нет, он был совсем точной!. Ошибок быть не могло. И тут на меня стало снисходить озарение, что ошибки-то в числах! Я внезапно стал уверен, что десятичное представление плавающего числа, каким мы его перенесли в наш симулятор из бинарника (initialization of member variables), в начале работы программы было скомпилено из java кода в другую константу, отличную в битовом представлении от тех, которые в были бинарнике.  Решение было тривиальным, и я пошел будить RST7.

Formal report in English

Algorithm used in submission, team THIRTEEN, ICFP Contest 2009 

There were several requests from english-speaking audience about the algorithm

which was used by our team. So, this article may give some description.

Full source code is in at the end of that post (subversion url).

Team Thirteen algorithm contains the following parts:

————————————————————

1) Lambert transfer: given the

• current coordinates
• motion vector
• exact desired transfer time T
• destination point,

calculates the impulse vector. This is done analytically (matlab+books), and very fast algorithm is implemented (10 iterations max). The results are not exact, but are used as a basis for

• estimating the travel costs to any satellite
• actual transfer setup (see “9)”)

2) Choose the right time to start. Given the

• current position
• destination satellite
• 2 time brackets

calculates the delay (t0) before Lambert transfer and duration T of the transfer, so that transfer has optimal parameters (speed or fuel usage).

3) Moon gravity - when some “earth/moon” point is passed, Earth gravity is not taken into the account when calculating Lambert, and moon-centered calculations are performed.  Otherwise, moon is excluded from the Lamber equations same way.

4) bin -> java compiler. Produces java class for fast calculations, for each task. Input/Output as per specification, 1 time tick is calculated. ”clone” method for previews of the future.

5) Simulator: given the initial impulse and delta T, calculate final state of the world (T iterations of VM).

6) For task 4001-4004, bin -> java compiler which does NOT calculate all satellites, only earth/moon/traveller coordinates. This is done by tracking data dependencies in bin file and excluding all non-relevant calculations which result in non-needed ports. 15-20x speedup is achieved.

7) caching of satellites position for the whole time range of problem, for faster lookup at any time point (done once per problem). Together with “6)” it gives fast “future preview” ability with regard to satellites.

8) Travelling salesman problem, reducing the use of fuel, without visiting fuel station. By the way, score was added for visiting it (later we discovered it). When choosing next satellite, we optimized t0, and T (see “2)”) and used search depth of 2 satellites (current, next, one after next), and criteria was to minimize sum of fuel spent.

9) Precise meeting. Given the satellite, using the Lamber transfer, get the initial impulse. Then, minimize the function distance_to_destination_with_initial_impilses(Ix, Iy) function is implemented as a simulation flight using fast java implementation of formulas from bin file (see “4)” and “6)”). Using gradient descent for optimization. Problem: when travelling towards earth, calculates very slowly due to unsophisticated algorithm.

9a) when optimization fails due to very long computations, travel anyway with best found impulse, then calculate new impulse in the middle of travel. Repeat if needed.

10) another algorithm of travelling salesman, where speed of travel was optimized, but fuel was refilled at the base station, was developed, but due to competition time constraints, was not polished, and used as backup algorithm. This helped to solve 1 problem, where main algorithm failed (!) during the separate top-10 competition in the aftertime.