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

[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, так сказать.

Comments

[zamotivator.livejournal.com]

И, что интересно, на банальном Си. Видать пофигу на язык...

[sorhed.livejournal.com]

Задача в этом году была не ФП-friendly совершенно.

Вот в прошлом...

[zamotivator.livejournal.com]

Гм, по-моему куда уж более friendly... озвучьте критерии, что ли.
И да, напомните, пожалуйста, какая задача была в прошлом году.

[sorhed.livejournal.com]

Не-friendly — «в области есть множество наработанных алгоритмов, сформулированных императивно, которых удобно писать прямо так, а не пытаться выражать идиоматически для ФП».

Friendly — это когда задача в области, традиционно предпочтительной для ФП-идиом. В прошлом году, например, были соревнования по построению из SKI-комбинаторов разных штук, убивающих ячейки друг друга.

Я мониторю задачи с 2006 года. Friendly были задания в 2006, 2007, (частично) 2009, 2010 и 2011.

Не-friendly — 2008, (частично) 2009, и 2012.

[zamotivator.livejournal.com]

А, вспомнил задачу прошлого года. Я её даже понять толком не смог, не говоря уж про реализацию...

[sorhed.livejournal.com]

На самом деле, конечно, DISREGARD THAT I SUCK COCKS. В смысле, чего жаловаться на идиоматичность, раз мы считаем, что за ФП будущее и оно подходит для всего.

[zamotivator.livejournal.com]

Респект за самокритику

[jsn.livejournal.com]

Наводит на мысли, я и говорю. Забавно, все эти Хаскеллы, Скалы и МЛи выглядят для меня абстрактно-привлекательно, но как только доходит до реальной драки, по факту оказывается, что выбор у меня простой: если задача требует гибкости, то дайте мне какой-нибудь разумный лисп (scheme, ruby, даже перл или питон сойдёт, если всё совсем плохо), а если производительности -- то я возьму Си с опциональным libgc on top.

Причём надо понимать, что Си я беру в руки примерно раз в году ровно по этому поводу. Не то чтобы я на нём в последние лет десять много чего писал, и не то чтобы я в нём в очень хорошей форме.