ICFP09 Contest Как это было. Или как летают в космос (ЧАСТЬ 2)

Первую часть можно прочитать тут.

28.06.09 (09:00:16) Воскресенье(2й день)

То, что для одних - выходной, для других - день рабочий. Впрочем, Участие в ICFP - это дело добровольное, как оказалось, поэтому в этот день Саша не пришел нам помогать - видать, ему хотелось заданий вроде 2005-2007 годов выпуска. Впрочем. никто его винить не стал ;) Мне и самому задача показалась скучноватой, но раз дело начато - надо его достойно завершить.

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

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

Как догнать спутник

Такой алгоритм дал очень хорошие результаты. На орбиту мы приходили с допуском +/- 10 метров, что нас вполне устраивало, так как максимальное расстояние, на которое можно было промахнуться - было 1 км. А вот с тем, чтобы встретиться со спутником, возникали вполне определенные проблемы. Мы промахивались на достаточно большие расстояния - от 7ми до 21 километра. Сначал мы растроились, что наши формулы неправильные, но, после, попробовав подобрать оптимальное время старта, обнаружили, что проблема кроется в дискретности времени. Δt = 1s, а старт необходимо проводить, например в 1,573 с. И в случае больших орбит, погрешности выходили очень большими. Правда, два задания, все-таки были решены. А для оставшихся нам понадобился маневр, который позволил догнать спутник с хорошей точностью.

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

В конце дня у меня были все готовые решения ко второй задаче, а Рома пытался сделать рассчеты по выходу на произвольные эллиптические орбиты. Помнится, он мне еще пытался объяснить принципы, но я к тому времени устал очень сильно, и все его слова были для меня белым шумом, из всего что я понял, решение заключалось в последовательном переходе круговая-круговая-эллиптическая. Нужно было выйти на круговую орбиту с радиусом апогея эллиптической орбиты спутника. Ох.. загнул ;) В общем к тому времени, как надо было уходить, мы решили одну задачу из третьего задания, и с пониманием, как решать и чувстом выполненого долга, отправились по домам.

29.06.09 (10:00:16) Понедельник(последний день) 

Четверое задание

Что осталось нам на третий день? Решить три задачки из третьего задания и браться за четвертое. Дело осложнялось тем, что Рома должен был уходить за 7 часов до окончания контеста, и я оставался один на растерзание остальным командам, которые вышли на финишную прямую. Надо сказать, что со своим заданием мы справились успешно, правда пришлось “подсмотреть” и закешировать параметры вращения спутников, но к тому времени, у нас уже был девиз “Все методы хороши”. До часу дня все задачи были успешно решены, и Рома потратил оставшееся время на попытки оптимизировать результаты, а я открыл четвертое задание. Картинка была взята из отчета одного из участников aka jerom. К этому моменту у нас было 2442.9907 очков и 51 место в общем зачете.

Как только я открыл четвертое задания, я сразу понял  - что тут мне делать нечего. “Шеф, все пропало!(с)”. На то время у нас имелись более менее работающие маневры переходов круговая-круговая, круговая-эллиптичекская, но общего решения, которое складывалось бы из последовательности таких маневров не было. А четвертая задача заключалась в посещении 10-ти спутников, которые вращаются вокруг Земли, и одного спутника, который вращается вокруг Луны (она на картинке отсутсвует, потому что находится очень далеко). Но я решил не сдаваться и пробовать. Кроме этого, возле Земли еще крутилась заправочная станция, так как на посещение 10-ти спутников топлива не хватаило.

Для начала я попытался просто “нахалявить” результат, выйдя на круговую орбиту рядом со спутником. Получил 199 очков и сильно обрадовался. Однако, радость моя была преждевременной - очки засчитывались только, если очков было больше 200, и по форбуле (200-х)*4/3. Так что, спутник я не словил. После получасовых рассчетов и проверок, мне удалось выяснить, в чем заключалась моя проблема - мы стартовали с эллиптической орбиты. Более того, Луна, хоть и была далеко от Земли, но тоже вносила свои коррективы в орбиты спутников. С этими знаниями, ко мне пришло осознание того, что все стало только хуже(Лучше бы я вообще не знал, что летаю по эллиптической орбите ;). Оставалось четыре часа до окончания, передо мной лежала груда исписанных листиков с формулами, и у меня ничего не получалось.

Тут я совсем отказался от рамок приличия, и начал подбирать. Примерно зная орбиту спутников, их расстояние до Земли в опеделенный момент времени, я “высчитывал” время, когда надо стартовать, и с каким импульсом. Задача упрощалась тем, что в четвертом задании, для посещения спутника не обязательно было находиться возле него 900 секунд, достаточно было просто возле него пролететь. Результаты очень быстро сходились, и уже через 20 минут, я получил заветные 243 очка за решение задачи! Правда, код после таких подборов выглядел страшно ;)

...
final double rb1 = 1.8818517804189954E7 + 278170.9991007 + 2307.235661063343;

hm = new HohmannManeur(data.getCurrentRadius() - 310, rb1);
setStartTime(currentTime);
hm.initManeurData(currentTime, data);

int hmStartTime = 4660;
...
final double rb3 = 4.243768752758199E7 -2241606 + 685449.5152277425 -281833 /2  -43279 -12905.7179 - 7000 - 1600;
final int satelliteNum = 2;
hm3 = new HohmannManeur(data.getCurrentRadius() - 36000 , rb3);
hm3.initManeurData(currentTime3, data);
int hmStartTime3 = 35761;
....

За два часа, я успел таким образом “словить” 3 спутника в задании 4001, и увеличил количество очков до 2626.0034. И все. Тут мой запал закончился. Дело в том, что после выполнения этих маневров, было необходимо возвращаться к заправочной станции, а топлива уже не хватало. Как, в прочем не оставалось и желания “пересчитывать” маневры заново ;). В общем я рассчитываю на 40-50 место. Если бы под конец дня было немного больше людей, то можно было бы закончить с гораздо большим результатом ;) Но не хватило людских ресурсов на подбор решений ;).

Итоги

Team Name : Stanfy
Score : 2626.0034
Place : 51 (за 4 часа до окончания), и предположительно 40-50 место в окончательном результате.
Team : 1-4 человека
Language : Java

Считаю, что выступили удачно, да и еще весело было, так что в следующем году будем учавстовать еще раз.

З.Ы. Обещаю, более качественно сделать Sapkа’10 :) и искренне  болею и желаю удачи, команде THIRTEEN, которая заняла 0-е место в Sapka Contest.

З.З.Ы. На хабре челове занялся сбором отзывов о ICFP’09. Если интересно, то можете почитать ;)