Category: литература

eye

ICFPC 2009


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

Суть заданий описана у _adept_(Таких не берут в космонавты!), так что повторяться не вижу смысла.

О контесте я узнал за два дня до его начала, так что о команде речи не шло. И хотя удалось собраться втроём ( mr_aleph, nealar), задание им не понравилось, так что команда распалась, не собравшись. Позже nealar  приходил и хотел помочь, но я к тому времени уже наваял код, который не соберётся без соответствующих библиотек.

После чтения спецификации я занялся реализацией VM копанием в своём стороннем коде и вообще посторонними вещами. Сыграло мнение других участников, что задание не ахти. Однако через 5-6 часов, доделав дела, я начал писать VM. Считаю, что правильно сделал, выбрав C++ для этой задачи, так как кода было мало (284 строки на VM и "визуализатор"), а работало всё сразу и достаточно быстро, так что я к нему больше и не возвращался.
Протестировав работу, написал биндинги к Haskell, дабы основное решение писать уже там.
Почитав википедию на предмет предложенного варианта решения, я написал "в лоб" решения первых 4-х задач, а затем вторых 3-х. Вторая задача (из второго блока) не поддавалась — результирующая орбита была очень далеко, так что я попадал в цель, но недостаточно близко.
Было утро субботы, а я не спал уже с 20 часов четверга, но полученные быстрые очки дали уверенность, что "вот ещё чуть-чуть" и сделаю почти всё. Хрен! Третьи задачи были сложнее, и реализовывать их тем же методом, что и первые, было уже нереально. Очевидно, что управление спутником в данных задачах — state-машина. И вот тут я сделал большую ошибку. Вместо того, чтобы использовать yield (продолжения, или монаду Cont), меня чёрт дёрнул использовать игрушку, с которой я игрался на днях — акторы а-ля Erlang c selective receive и прочими свистоперделками. И беда тут была вовсе не в том, что это сделанная на коленке реализация (как выяснилось, как раз в ней багов не было), а в том, что опыта её использования у меня нет никакого. С другой стороны, этот опыт я получил :)
Переписанная на акторы реализация давала возможность в обработчике получать сообщения от VM и переключать состояния направо и налево, что, собственно, умеют и продолжения. Написав решение для первой задачи в новом стиле, я вдруг обнаружил, что иногда спутник не реагирует на мои команды. Точнее, он либо реагирует раньше, либо позже, либо завершает всю обработку в самом начале полёта. Повтыкав liftIO $ putStrLn "I am here" и прочего, я вдруг заметил, что спутник стал слушаться. И тут я сделал вторую фатальную ошибку, которая отняла у меня всю субботу и часть ночи воскресенья. Я грешил на ленивость, так как уже сталкивался с чем-то подобным (разумеется, виноват был я, а не компилятор). Если бы я был выспавшимся и с незамутнённым сознанием, то сел бы и подумал над своим решением, а тут я стал вставлять разные логирующие выводы и искал баг совершенно не там — в библиотеке акторов, которая как раз работала прекрасно.
Как выяснилось к утру воскресенья, все проблемы возникали от того, что я никак не синхронизировал прогон VM и обработку каждого шага своей функцией. В итоге в виртуальной машине уже могло быть сделано 10000 шагов, тогда как обработчик работает над сообщением из 1000-го шага, но при этом располагает актуальными данными! Т.е. в обработчике шаг был тысячный, а данные он получал уже с десятитысячного. После этого, исправив код вставкой везде, где можно, syncHost, посыпав голову пеплом, я таки отправился спать в районе 4 часов утра. Можете посчитать, сколько я не спал в сумме.
Полноценно вернуться я смог уже только к утру понедельника, проспав более суток. Здесь мне надо было бы сходить на разведку и узнать, что есть книга Orbital Mechanics: For Engineering Students, где подробно расписаны все варианты манёвров на любой вкус, чего было бы достаточно с головой. Но я сел и стал изобретать собственные методы, в последствии узнавая их реальные названия :) Плюс зачем-то стал писать всякие "подруливатели", которые могли держаться на орбите в пределах 1-2 метров, или догонять впереди летящий спутник с высокой точностью. Толку от них почти никакого, а времени я опять же потратил.
Дописав различные манёвры, посжирав топливо в первом задании, я опять ушёл в отключку.
Проснулся за 2 часа до конца и реализовал наконец-таки вторую задачу из второго бинарника. Принялся за третью, и к самому окончанию успел попасть в пределах двух км. Казалось бы, ещё чуть-чуть, и сделал бы одну-две (а то и все) задачи из третьего файла, но ещё чуть-чуть уже не было.

В общем и целом, мне понравилось, но я, можно сказать, слил. Жаль, по своей же глупости.

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

Суммарный объём кода:
Haskell: 1347 строк
C++: 284 строки

Код: http://voidex.org/icfpc/svn/trunk/
В архиве: http://voidex.org/icfpc/2009/voidex_icfpc_2009.zip