ICFPC '09,
или Some Rocket Science!,
или Почувствуй себя Говардом Воловицем

О существовании ICFPC я узнал пару лет тому назад, из отчетов жжюзера _adept_ о вакханалиях 2006 и 2007 годов. ICFPC стрясаются ежегодно, длятся обычно несколько дней, а задачки на них варьируются от интересных и заковыристых до настоящих произведений искусства. Особенно тут отличился конкурс 2006 года, посвященный "вычислительной археолингвистике".

Невзирая на свою тормознутость, дикость, отсталость, темноту и каменновечность, я настолько проникся энтузиазмом, что решил обязательно как-нибудь да поучаствовать в этом безобразии.

Однако конкурс 2008 года я успешно профтыкал, из-за чего сперва расстроился, а потом возрадовался: задание по выездке полуслепых марсоходиков не блистало артистическим флером Эндо и Универсальной Машины, зато звучало крайне зубодробительно и занудно; а страшные истории участников о Жутком ЛайвСиДи и Синдроме "Да Где Же Этот Сервер?" окончательно убедили меня в том, что потерял я немного.

Зимою я несколько недель возился с пресловутой У.М. 2006 года—написал свою имплементацию, порешал некоторые задачки, среди которых мне сильнее всего показались язык O'Cult, конспироложеский текстовый "квест" и функциональный язык с блок-схемным синтаксисом; все это, естественно, не в конкурсном режиме долбить-долбить-долбить!, а изредка пару часиков для удовольствия. Сие занятие понравилось мне настолько, что я твердо решил в 2009 году свой шанс не упустить.

Подготовка

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

В порядке общей подготовки к, и вящего воспитания характера я загодя решил для себя пару важных вопросов.

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

Во-вторых, я составил шорт-лист языков для применения в. Очень меня тянуло на всякие эксперименты—кругом стока всиво вкуснава! но я остановился на C++ и PHP. По очень простым соображениям.

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

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

Круг DSL'ов я ограничивать, конечно, не стал: на то они и DS, чтоб по обстоятельствам.

Увы, но приняв все эти четкие и ясные философские решения, я безбожно протупил несколько важных практических аспектов подготовки.

Я так и не собрался отряхнуть пыль со своего сабвершновского репозитория. Мысль о нем крутилась где-то рядом постоянно; но я все думал, что, мол, один же играю, чо там возиться, да ну нафик. I really ought to know better by now. Это была серьезная ошибка.

Я не подготовил себе хорошее рабочее окружение для C++. Надо было хотя бы поднять boost, dinkumware держать наготове, освежить в памяти Gtk2 или WxWidgets какой-нибудь, ну и вообще быть в курсе, где есть что полезного, и как это ставить. В результате так и жил с голым STL'ом.

И наконец, я не попытался разгадать хинты организаторов. Ах если б догадаться, что речь о программе "Шаттл-Мир"...

Конкурс начался 26 июня в 13:00:16 по какому-то там американскому времени; в девять вечера по Латвии.

День нулевой,
в котором я ставлю задачи на следующую пятилетку трехдневку

Через пару минут после официального начала {~0:02—здесь и далее в фигурных скобках время с начала конкурса} я полез на официальный сайт и давай себя регистрировать, даже не пытаясь читать что-либо о задании. Название "team wobble" было избрано в честь слова "wobble", которое с неподражаемым прононсом говорил косящий под психа Роуэн Аткинсон в последней серии "Блэкэддера". И оказалось оно пророческим—поскольку конкурс был об орбитальной механике, и злосчастные мои спутники только и делали, что wobbled в эпсилон-окрестности намеченных целей. Номер мне достался 55—arguably, also the wobbliest of them all.

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

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

Чтение википедии произвело на меня двоякое впечатление. С одной стороны, первая задачка показалась мне абсолютно тривиальной (переход с одной круговой орбиты на другую... в двумерном космосе). С другой—сведения о более сложных эволюциях были либо расплывчаты, либо мозгоплавны. Около полуночи {3:00} я отложил все эти математики с физиками и сел читать собственно спецификацию. Выяснилось, что:

• для начала надо написать нехитрую виртуальную машину—даже без управления PC; он просто обнуляется между итерациями с сохранением всего остального стэйта,—которая сможет запускать таинственные бинарники, оказавшиеся симуляторами задачек—тут у меня оказался Нечестный Эдвэнтич, поскольку в памяти был свеж опыт имплементации У.М. (клево!);
• потом надо написать Решалки, которые из недр виртуальной машины будут получать ворох нехитрой информации—декартовы координаты разнобразных объектов с центром координат на управляемом нами спутнике—и возвращать обратно Δv—все это с дискретностью в одну секунду;
• задачек четыре: переход с одной круговой орбиты на другую; два спутника на круговых орбитах, их нужно "повстречать"; то же, но с эллиптическими орбитами; жуткий Ужос с облетом двенадцати спутников и дозаправкой; каждая задачка ценится вдвое выше предыдущей—(блин!) все это Нечестный Эдвэнтич ценителям Orbiter'а :-));
• все свои попыхивания трастерами надо писать в трэйс-файл определенного формата и отсылать организаторам для верификации.

Покурив спецы, я прикинул, что на написание примитивной ВМ у меня должно уйти три-четыре часа, что хохманновский переход нелеп и тривиален, и его можно нарисовать за час; и что если в субботу меня будут не очень доставать, то к концу лайтнин-раунда (т.е., через 24 часа после начала состязаний) у меня должны быть какие-то очки за первую задачу. Затем я отправился спать {3:45}.

День первый,
в котором я выполняю намеченную программу

Севши утром в поезд {10:45}, я сразу достал еее, и в течение сорока минут методом креативно-адаптивной копипасты лепил из сорсов У.М. скелет Орбитальной Машины. На работу приехал в девять {12:00}, и был внутренне готов к тому, что на конкурс придется рррезко забить. Однако в силу субботнести и проч., день выдался крайней медленный; так что я до вечера за малыми перерывами манкировал обязанностями по кнутованию и моргенштернению подотчетных гамадрилов.

У.М. оказалась большим подспорьем, простуда—большим неудобством. По сумме факторов вышло где-то по нулям. Обедать я не пошел, и к часу дня {16:00} у меня в неспешно-простудно-тормозном темпе была готова вполне рабочая ОМ без трэйсинга.

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

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

От эмбеддинга скриптового языка я отказался все из той же экономии времени; к тому же меня волновал вопрос работы с 64-битными даблами. Ну и, да, PHP, сколько помню, эмбеддится не очень элегантно; а луа с питонами, которые очень,—я не очень хорошо знаю. В общем, нунафик, C++ ftw!

Да еще ведь надо в лайтнин-раунде каких очков добыть!!1

И я сел писать первый актуатор, который реально что-то делал бы.

Хохманновский алгоритм я и вправду написал меньше чем за час {16:50}, но... невежество + дискретность + ляпы и недоработки = спутник мой улетал черт знает куда.

Я почесал репу. Математический гений если и дремал во мне, то в труднопробуждаемости был подобен Ктхулху. Я плюнул. И подошел по-говнокодерски. То есть, стал твичить. Твичил я без малого три часа {19:35}, NaiveHohmannActuator превратился в HohmannWickedActuator, и где-то в половине пятого, через пень-колоду, на очередном переполненном магическими числами алгоритме коррекции орбиты, добился наконец первого позитивного результата. Спутник прилетел в окрестность заданной орбиты, и, бепсощадно^TM пердя двигателями, wobbled от ней неподалеку все девятсот секунд. Первые ~шестьдесят очков. (УРА!)

Да, но было "но". Трэйсы моя ОМ писать еще не умела. Поэтому очки оставались сугубо виртуальными. Я быстро-быстро накатал логгер, отослал четыре трэйса—по одному на сценарий,—и стал ждать... {~20:15} Ждать пришлось долго, уж и "рабочий" день закончился, а я так ничего и не дождался (что странно, впоследствии трэйсы проверялись много быстрее).

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

Сев в микроавтобус {21:30}, я снова достал еее, и с ужасом обнаружил, что мои трэйсы помечены как CRASHED! (блин!) Изрыгая жуткие ругательства, я стал читать спецы и шевелить волосами. Далеко не сразу до меня дошло, что я забыл последний таймфрейм, что к его таймстампу не нужно добавлять единицу, и что на нулевом таймфрейме обязательно нужно сконфигурить Волшебный Порт Сценария (зачем? в хедере же есть—правда, интом, а не даблом). Тут еще выяснилось, что номер порта я пишу шортом, а надо интом... в общем, только к {~22:25} первый трэйс успешно прошел верификацию.

Раздалось дикое гиканье.

Через несколько минут у меня было 250 с копейками очков, и я находился на сто тридцатом примерно месте. (УРА!) М-да, правда лидеры к этому моменту набрали около двух с половиной тысяч... (блин!) За час рандомными твиками я додавил свои решения до 290, отослал сорстри {~23:45}, порадовался успешному выполнению Плана На День и взял тайм-аут на пару часов. (УРА!)

В одинадцать вечера {26:00} я снова взялся за клавиатуру. Впрочем, сначала я прочитал последнюю спецификацию, скачал бинарник для четвертого задания (который в первые сутки не выдавали), погоревал о том, что в коде бардак и волшебнозначество, да еще вместо нормальной математической библиотеки или комплексных чисел я использую маразменный маразм std::pair<Scalar, Scalar>... затем я прочитал фак. Из фака я узнал две оч-ч-чень интересных вещи:

1. В бинарнике первого задания есть нелепая, муа-ха-ха, бага, из-за которой очков дают тем больше, чем меньше осталось топлива (то есть перед концом лайтнин-раунда я час портил свои решения). Организаторы знают и смирились.
2. Конкуренты додумались клонировать ВМ для предсказания будущего. Я идею оценил, и в дальнейшем даже нарисовал болванку OracleInterface. Впрочем, не прикотиилас. (блин!)

В течение часа {27:30} я вяло вычищал из кода некоторые виды бредятины, а затем, приуготовляясь ко сну, сформулировал задачи на следующий день:

1. Вычистить существующий код хотя бы от самых вопиющих безобразиев.
2. Трохи порефакторить—не забегая вперед, но про некоторые вещи уже ясно, что они нужны во внятном виде. ((блин!) Пефектным хайндсайтом вижу, что нужен был абстрактный актуатор, который умел бы внутре себя инициировать хохманновский маневр, производить орбитальную коррекцию и преследовать объект—но вот как раз этот-то важнейший аспект я и проигнорировал, из-за чего актуаторы превратились в болото копипасты!)
3. Выдавить остатки очков из первой задачи.
4. Решить вторую хотя бы на уровне кучи магических чисел.

[За первый день я написал около тысячи строк кода (wc -l, а не Настоящих LOC), примерно половина—жуткое месиво.]

День второй,
в котором я волочу ноги и занимаюсь фигней

С одинадцати часов {38:00} и до 16:20 {43:20} я неторопливо чищу код. Результат не очень впечатляет: выглядит все немного приличнее, но все еще используются всякие нелепые самопальные типы данных, а одиозный HohmannWickedActuator хотя и стал выглядеть цивильнее, но все еще содержит функциональность как общеполезную, так и узкоспецифичную.

К тому же я немедленно принимаюсь его обратно децивилизовывать с целью выдавить еще очков из первой задачи. Результат опять не впечатляет, за два с копейками часа возни {~45:45} я получаю семьдесят очков (всего 360). Правда, актуатор выглядит довольно аккуратно—спутник нервно осциллирует между низкими орбитами с целью сжечь топливо, а потом уже выходит на окончательную.

Наследую у хохманна актуатор для второй задачи. М-да, actuate() все равно тупо скопипасчен, только в конце влеплен makeFreefallAction()—думает как хохманн, говорит как хохманн, только не делает ничего.

Для начала (из спортивного неспортивного научного интереса) руками нахожу оптимальные задержки на начальной орбите для всех четырех сценариев. К сожалению, мой Преследовательный Интеллект несовершенен и догнать цель все равно не может, хоть ты тресни. Так и вижу, два спутника пролетают друг мимо друга на относительной скорости в 5 км/c, причем из моего, невзирая на безвоздушность, доносится вопль "бллллдджжаааааааааад!". (Здесь бы хорошо смотрелся кадр с Шелдоном в костюме эффекта Допплера.) Закомментариваю весь этот разврат, и начинаю писать не менее развратный Постепенный Орбитальный Приблизитель.

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

Фак проясняет—в отличие от предыдущей задачи, здесь нужно выдержать девятсот секунд рядом с целью без трастеров. Отламываю какую-то ненужную деталь в Догонятеле, отчего он становится немного смирнее, и может даже найти и удержать орбиту в течение девятисот секунд с отклонением всего на несколько сотен метров.

Подгонкой кучи бессмысленных констант и бесконечными прогонами нахожу решения для 1, 3 и 4 сценариев {47:30}. К сожалению, в процессе обнаруживается, что валидатор некоторые найденные мной решения зарубает по крэшу или таймауту, и почти всегда по-другому рассчитывает очки. Это тревожит.

К концу вторых суток {48:00} у меня есть безобразный Решатель для второй задачи, который работает весьма неуверенно, и 930 очков на счету.

Я скриплю зубами, шевелю волосами, переписываю Орбитальный Приблизитель на более разумный алгоритм, который следит за относительным положением цели, и корректирует орбиту на более низкую или высокую. К сожалению, все еще много магических констант, к тому же остался ненайденный глитч, из-за которого иногда не срабатывает определение орбитального обгона. Кроме того, я переделываю свой Догонятель, отчего он становится много эффективнее, обнаруживаю, что ускорение свободного падения у меня всегда, волосы шевелятся на голове!, 9.8, вылавливаю формулу из википедии, исправляю, пишу воркэраунд для второго сценария, который использует найденную руками магическую задержку, и к двум часам ночи {53:00} у меня 1090 очков и восемь решенных сценариев. ЙА ФСОТНЕ! (УРА!)

(Моя внутренняя, вся такая честная оценка решенности сценариев—0.99 для 1001, 1002, 1003, 1004, 2001, 2003, 2004 и 0.4 для 2002.)

Если за "второй день" принять мой биологический день, а не "вторые сутки с начала конкурса", и если не обращать внимания на уродливые хаки и окончательно плачевное состояние кода, то план на день выполнен в полном объеме.

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

День третий,
в котором я падаю духом и говорю очень много дурных слов

Снова в поезде {58:45}: пытаюсь сделать глупейшую вещь... за несколько минут делаю актуатор, который использует только Догонятельный алгоритм. И, о чудо! он решает три из четырех сценариев третьей задачи! Смотрю отладочный вывод—в этих сценариях цель стартует на расстоянии меньше двух тысяч километров! Фигли там догнать с ресурсом Δv в 50 км/c!

Это еще тысяча очков!!115 (УРА!)

И тут меня ждет очередной облом. Все трэйсы таймаутятся. (СУКА!)

Приезжаю на работу {60:00}. "Трудный день" забыт, твичу, твичу, твичу, результат нулевой, валидатор упорно отлупливает все решения. Лезу в фак, и:

Q: We're having problems with submission of attached trace for scenarios in problem #3. For instance, attached trace for 3001 works ok on our simulator and produces a score. In fact, we get within 55m of the target and stay there for >900 seconds without firing the engine. However, when I submit this trace, I get timed out error instead of a score. Our simulator appears to work correctly, since we have been able to work through other scenarios (except for problem #3). Can you explain why we're seeing this result?
A: It is good practice to check where you are is where you think you should be, and compensate for any simulation or rounding issues.
(This example failed for us on 3 different VMs, on different architectures, and appears to settle into an orbit 4000M away. We realize this is frustrating, we recommend adding compensation code, because it can read live data from our VM-based sensors.)

Выглядит это очень благородно, но если таки вчитаться в смысл, то обнаруживается, что организаторы как бы говорят нам: "Сосните хуйцов, лузеры!"

Я прихожу к выводу, что: либо они используют немного другой бинарник (вряд ли), либо у нас отличается математика с плавающей точкой. А я помню, интел неправославен относительно IEEE 754... Несколько часов читаю мануал gcc, кручу свитчи во все стороны, -mfpmath=sse орет благим матом, запрещаю регистры, бьюсь головой в дисплей, собираю третьим и четвертым под x86 и x86_64, в отчаянии закидываю сорсы на свой WDMBWE (arm), собираю там... и не то что не могу найти правильное решение... я не могу добиться хотя бы того, чтобы моя ОМ выдавала хоть немного другой результат!!! (СУКА!)

Достаю SoftFloat, с ломом и матом прикручиваю его к ОМ, в процессе обнаруживаю, что при -O0 и -O1 вместо трейсов пишется полная белиберда, причем -fstrict-aliasing тут совершенно не при чем (а что при чем—я так и не понял), седею, потею, лысею, хуею, пишу arg = float64_to_floatx80(*reinterpret_cast<float64 *>(&((*data_)[W_OM_SR((*prg_)[pc_])])));, поскольку есть подозрение на подлый sqrt() у организаторов, который может считаться в 80-бит, потом раундиться в 64...

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

Незадолго до скорбод фриза в {68:00}, отсылаю наименее изуродованную версию без SoftFloat (wc -l: 1995), ресабмичу трэйсы, которая выдает именно эта версия, сваливаюсь до 1060 очков и 121 места из 317. До окончания еще немного вожусь, пытясь понять, как же такое может быть, но так ничего и не добиваюсь...

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

Только вот с установкой на борьбу с задачей не сложилось. Hack-hack-hack-kludge-tweak-hack-tweak-tweak-kludge-hack...

Огр-выводы

Организаторы должны организовывать тест-сьюты для виртуальных машин.

Больше Думать!

Невзирая на. Было охуенно. ПЫЩЬ-ПЫЩЬ.

ps.

pps.

ppps.

pppps.