Skobochka ICFPC-2009

Участники:

  1. dmitry_vk
  2. turtle
  3. '()
  4. lexa_

hg: https://developer.bazon.ru/hg/icfpc-2009/

Передача опыта:

Начало

В этом году я так и не успел собрать команду, да, если честно, особо и не старался. Хотел выступить на ICFPC и посмотреть что да как. До этого пытался участвовать в ICFPC-2007, но после первого дня завалился срочной работой, и ICFPC-2008, но там весь кайф обломали наличем сложной системы с LiveCD, поэтому я участвовать не стал и уехал. В этом году же я вроде как решился, и день приблизился резко и неожиданно. За несколько часов до начала в конференции lisp@… появился dmitry_vk и задал вопрос: "Понимаю, что уже довольно поздно спрашивать, но вдруг. Нет лиспников, желающих составить компанию/пригласить в команду в ICFPC?" В общем, лисперов, желающих поучаствовать оказалось немного, поэтому создали конференцию lisp_icfpc@… и репозиторий для исходников. И на этом я пошёл домой. Смысл задания в этом году состоял в управлении спутниками на орбите земли. Управление происходило путём подачи нужного вектора ускорения, на что расходовалось топливо двигателя. Вся симуляция происходила внутри программы внутри виртуальной машины, а ускорение подавалось путём установки нужных значений в определённые порты машины. Итак, задач управления было четыре:

  1. Перевод спутника с одной круговой орбиты на другую;
  2. Перевод спутника на другую круговую орбиту, но так, чтобы встретиться с другим спутником на этой орбите;
  3. Встреча со спутником, находящимся на эллиптической орбите;
  4. Посещение нескольких спутников, находящихся на разных орбитах;
  5. И просто ещё одна задача, не шедшая в зачёт, для управления кучей спутников как нравится.

Виртуальная машина

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

Проблема Хохманна-Ветчинкина

Как уже и описывалось, необходимо было перевести спутник с одной круговой орбиты на другую. Для этого даже прилагалась страница в википедии http://en.wikipedia.org/wiki/Hohmann_transfer. В принципе, сложного ничего абсолютно нет. Нужно подать два импульса - один в начале манёвра, чтобы сойти с орбиты, второй по завершению, чтобы закрепиться. Первые попытки подачи импульса привели к тому, что спутник улетал непонятно куда. Только затем в беседах в конфе я понял, что начальное положение спутника находится не на оси, как в википедии, поэтому касательная скорости будет другая. После расчётов спутник стал достигать орбиты. То же проводил dmitry_vk, но программным способом. Я предложил написать писалку файлов решения, но вынужден был уйти. Когда пришёл, то обнаружил, что solution dumper написан, но сабмиты не прошли. Просмотрев что там происходит, подправил под своё понимание и залил файлы решения. Так мы получили первые очки.

Проблема встречи со спутником на круговой орбите

Следующей задачей было встреча с другим спутником, находящимся на круговой орбите. dmitry_vk предложил сменить орбиту, а затем разгоняться/тормозить. У меня была мысль расчитать время начала манёвра, чтобы по завершению положения обоих спутников совпали. dmitry_vk попробовал свою идею, но спутник уходил по эллиптической орбите, и он ушёл по делам. А я остался воплощать свою идею. Странно долго тупил с трактовкой относительных координат. У dmitry_vk было сделано rel-x - x и я интуитивно с этим был не согласен. Сначала думал, что в потоке данных идут относительные координаты до целевого спутника, но подставление x + rel-x давало невменяемые результаты. И лишь более внимательно прочтя спецификацию я понял, что это относительные координаты от целевого спутника до нашего, т.е. x - rel-x. Затем расчитав время, совершал манёвр. В общем, в этот день что-то очень хотелось спать, как и в предыдущей, и я в полубреду не понимал, почему угловая разница между двумя спутниками получалась от 5 до 30 градусов. Впрочем, на каком-то из шагов у меня получилось, что разница составляет 1.5 километра до спутника, но это решение я потерял. Вернулся dmitry_vk и решил положить всё это под математическую основу и расписал мою идею в терминах математики. Реализовав, получил разницу в несколько километров. После обсуждения пришли к выводу, что проблема заключается в дискретности времени, поэтому необходима корректировка орбиты после завршения манёвра. После некоторых поисков по книжкам нашли, что это называется фазированем орбиты, но я уже плохо соображал и пошёл спать.

Окончание

Проснувшись, я обнаружил, что у нас уже 7 задач в зачёте, а не проходила задача 2002 и давала разницу градусов 30. В этот день была куча дел, да и на работе, поэтому время практически не уделял. Решил зайти на icfp@… и почитал что там люди делают. Некто sunnysanoff_icfp бросил клич о том, что у него есть интересный алгоритм, но у оргов решение падает и поэтому нужна другая виртуальная машина для проверки. В общем, нам терять было особо нечего и я предложил ему свою, но узнав, что она на лиспе, он вежливо отказался. :) Потом я вспомнил, что где-то видел на яве оную и дал ему ссылку. Спустя некоторое время их команду THIRTEEN уже наблюдали на первом месте. dmitry_vk нашёл ошибку во второй задаче и у нас стало 8 решённых и приступил к решению перехода на эллиптическую орбиту. Но у него тоже закончилось свободное время и он выбыл. Я попытался модифицировать хохманна с тем, чтобы потратить побольше топлива, но у меня спутник уходил с орбиты. В общем, у меня опять появились дела и я выбыл. Итого по таблице - 152 место, но нас могли вытеснить до конца соревнований.

Выводы

Было классно. Но всё же, что могло бы быть лучше?

  • команду неплохо бы собирать задолго до начала соревнований и вместе определиться с ролями каждого;
  • математика - царица наук, её и по жизни знать неплохо, а в этих соревнованиях и подавно;
  • визуализатор был в SVG, но всё же хотелось более удобный;
  • всё же начинать соревнование нужно с книжек, которые мы начали искать только на 3-ий день;
  • ну и не хватало количества участвующего народа.