Доехал, наконец, гонец из Пизы

[jsn]

...вернее, из Эдинбурга. Не хотел писать отчёт об ICFPC до первых результатов, и -- вот они.

13 июля мы, как обычно, участвовали в ICFP Programming Contest-е. Команда наша называлась, как обычно, nbu (а ваша как?). Задачу этого года описывать не буду, вот у sorhed-а и вот у _adept_-а. Pun на тему "Lambda Lifting" и всё такое. Вот здесь можно попробовать поиграть в игру, в которой соревновались программы участников контеста. По сути, задача была на hill climbing, явно не то, что мы любим больше всего, но свою дозу фана мы вполне получили. Поменьше, может, чем в 2011-м, но куда больше, чем в 2009-м. Впрочем, за себя говорю, не знаю, как brohm.

Участвовали: brohm и искренне ваш, а также kolomaxes (guest star). Мы с brohm-ом делали основной heavy [lambda] lifting, kolomaxes делал всякие мелкие обвязки (а также нарисовал нам пару карт, которые демонстрировали недостатки стратегий, это было ценно).

Сразу после прочтения таска стало понятно, что это про hill climbing, и надо, скажем, запилить A* для начала, а там уж думать дальше. Также было понятно, что людей у нас мало, поэтому всё, что можно было бы реализовать, реализовать не получится, и надо как-то особо не растекаться мыслью. A* я запилил на Си с libgc, натурально. (Вообще, по опыту всех этих контестов, почти в каждом из них в нашем решении был центральный кусок инфрастуктуры, написанный на Си и в значительной степени мной. Разве что в 2011-ом я писал такой центральный кусок на scheme. Наводит на мысли).

К окончанию первых суток (lightning division deadline) у нас было, на мой взгляд, нечто вполне приемлемое для сельской местности. Но, к сожалению, мы что-то напортачили с отправкой решения организаторам, и теперь не узнаем, как наше изделие смотрелось бы на общем фоне. А жаль.

Дальше двое суток мы собирали и тьюнили A*-оские метрики, и искали способы сделать A* менее перфекционистским. И то, и другое принесло кое-какие, не то чтобы сногсшибательные, результаты. По-хорошему надо было на этом этапе делать как минимум двухуровневый A*, в котором верхний перебор идёт по грубо сформулированным целям, а нижний -- по траектории. Мне это было ясно ещё к исходу первых суток, но не менее ясно было, что в существующем составе мы этого скорее всего не успеем. Поэтому было решено высоко не прыгать, и т.д. В результате минут за 5 до дедлайна отправили изделие, которое пробует четыре разных варианта A* и выдаёт наилучшее найденное решение. ~ 1.3k строк Си ~ 50 строк перла для обвязки, плюс-минус.

Учитывая всё это (и задача не самая любимая, и рук драматически не хватало), я был бы доволен нашими результатами, если бы мы вошли в верхний квантиль. Однако, удивительное дело -- сегодня опубликовали первые результаты, и по ним мы в Top 10. Неожиданно. Woo-hoo, так сказать.