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

Для начала, тем, кто не знаком, с тем, что такое IFCP Contest - прошу ознакомиться. Если, все же, лень, то это ежегодное соревнование контест для программистов со всеого мира. Одной из идей контеста было привлечение интереса к функиональным языкам программирования. Во всяком случае, без него, я бы, наверное, не так скоро узнал о таких вещах как Haskell. В свое время, я пытался разобраться с Prologom - достаточно хорошо выворачивает мозг. Хаскелл - тоже. ;) Довольно приятно осознавать, что научился мыслить немного по-другому.
Да. Отвлекся ;)

За много дней до начала

То, что такое ICFP, я знал уже не первый год, но мне все никак не получалось в нем поучавствовать, по разным причинам. Приятным исключением был прошлый год, когда была задача про управление марсоходом. К ICFP Contestу 2009 я готовился заранее - собирал команду, предупреждал всех за месяц. часто посещал http://icfpcontest.org, и следил за каждым изменением информации о нем. Так что, в моем случае, не получилось так, что ICFP свалился как снег на голову - все было распланировано заранее.

За пару дней до начала

Организаторы контеста (вторая подсказка)

Организаторы выкладывают информацию о точном начале проведения контеста. Прочитав быстренько инфу, я  ничего особоенного не замечаю, зато замечает Рома, который обращает внимание на время начала контеста - 13:00:16. Это сразу навело на мысль, что это первая подсказка. Собственно, ICFP Contest и пленил меня тем, что подсказки могут быть где угодно.

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

Вторая подсказка была дана, когда организаторы вывесили свою фотографию на странице сайта. Мы сразу же отсканировали ее на предмет всякого рода teaser’ов, но тоже не нашли - фотография, как фотография. Зато, на IRC канале контеста узнали, что статуя, рядом с которой стоят организаторы просто не может там находиться. Это была статуя Икара. В результате. Что мы имели? 13:00:16 и Икар. Теперь, когда знаешь чему посвящено задание, такие подсказки вполне логичны. Однако они нас немного поставили в тупик. В конце концов, их цель - заинтересовать и, возможно, подготовить людей.К тому же еще правило работать на работе еще никто не отменял, так что подсказки были отложены до пятницы(21:00:16 по Киевскому времени).

26.06.09 (21:00:16) Пятница

Организаторы, как и обещали, выложили задание. Сайт, как обычно упал за минуту до этого. После нескольких попыток зайти на сайт была очень шустро скачана Chatzilla, и я зашел на IRC канал #icfp-contest. Буквально во втором сообщении, был линк на зеркало с выложенным заданием, которое тут же ушло на печать. Задание заключалось разработке программы, позволяющей управлять космическим аппаратом. Расчет всех параметров эмуляции “мира”, в котором существует Земля, спутники и коспический аппарат автоматического управляения происходит в симуляторе, для запуска которого было необходимо написать интерпретатор.  Собственно. первой задачей(для меня) и стало написание интерпретатора - ибо время было позднее, после тяжелого рабочего дня. Так что програмирование по четкой спецификации - это было единственное, на что я был способен в таком сотоянии.

Надо сказать, с этой задачей я довольно хорошо и быстро справился - видать, ВМ была очень простая. Так что где-то к 00:00:16-ти у меня уже была вполне рабочая ВМ. И вполне без багов, только для того,чтобы убедиться в этом, мне понадобилось еще два часа. Как оказалось, был баг в спецификации, коорая к тому времени уже обновилась до версии 1.2. Впрочем, так как мы договаривались не сидеть долго, а лучше с утра прийти все собраться командой на работе, то лег я спать рано - в 2 часа ночи.

После описания первого дня соревнований, вспомнилось то, что совсем не гладко обстояли дела с ВМ у меня в эту ночь. Во всем были виноваты Маленький и Большой индейцы. а именно Big-Endian и Litle-Endian encoding. Java любит Большого индейца, и все стандартные классы, сохраняют данные в таком формате, как скажет Би.  Причем, ночью меня сильно испугал данный факт. Ибо, если как перевернуть порядок байт в Integer, я представлял, то как из 8-ми байтов составить переменную типа double - это было нечто невозможное. А проблема эта была решена очень быстро. Благодаря Open Source, были найдены классы, отвечающие за чтение/запись данных, оттуда были “вырезаны” куски кода, а порядок чтения/записи байт поменян на обратный. Так что закон Мерфи тут не сработал.

27.06.09 (08:00:16) Суббота(1й день)

Гомановский переход

Да. пока не забыл ;) в 13:00:16 29.06.1995  произошла стыковка станции “Мир” с американским комическим аппаратом.  То есть в конце контеста (13:00:16 29.06.2009), мы тоже должны были уметь проводить стыковку на орбите. ;) Как ни странно, это одна из задач, которая нам поддалась только на второй день.

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

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

Потратив еще некоторое время на копание с ВМ, я пошел жаловаться на нее в IRC канале.  Мне довольно шустро подсказали, что я забываю подставить на входы ВМ нужную конфигурацию (сказалось невнимательное чтение спецификации). Конфигурации имели вид типа 1001,1002, 1003, 2001, 2002 и т.п. всего 16 штук - по четыре подзадачи на каждую проблему. Как только прооблема со спецификациями была решена, оказалось, что мы достаточно точно решаем первую задачу(1001). Рома, как разработчик каркаса приложения засел за реализацию формата решения, а я  занимался переводом спутников с одной орбиты на другую. В результате ко второй половине дня у нас было 4 решенных задачи, и мы отправили решения этих четырех задач. Как раз тогда организаторы вывесили таблицу текущих результатов, и мы оказались на 30-м месте.

Оставшийся день прошел в поисках решения второго задания, в котором необходимо было сделать то же самое, что и в первом, только нужно было выйти в определенной точке орбиты, чтобы встретиться со спутником и продержаться рядом с ним 900 секунд. О том, как догонять/перегонять спутник, я узнал только на следующий день…