dump -0f - /dev/mind

Gather round and settle down for the next instalment of the ICFPC write-ups.

ICFPC stands for ICFP Contest (and ICFP, in turn, stands for International Conference on Functional Programming), and I have been participating in them since early 2000s and writing up my adventures here. My most famous writeup (in Russian) about the best ICFPC so far -- 2006 -- could be found here.

TL;DR: This year, our team name was "Folding at home", there were three of us + my wife who solved a bunch of puzzles manually (but did not write code). We wrote an interactive computer-aided solver in OCaml and finished 36th in the Lightning Round and 21st in the Main Round. I liked this year's contest more than 2020 (but less than 2006 :). Puzzle was somewhat similar to the Origami puzzle from ICFPC-2016.

And if you want to know more than just TLDR, prepare for the wall of text :) ( Let's go )

This is part two of the ICFPC-2020 write up. Part one is here.( Read more... )

А вот как оно работало.

Сборка:


Разборка и переделка:

Тем временем незаметно подкрался очередной ICFPC: https://icfpcontest2018.github.io/

В этом году программируем нано-3D принтеры.

Пока пишу сам, на ocaml-е. Если кто хочет за компанию - пишите :)

Предыдущие части : день первый, день второй.

На третий день (традиционно, в 10:00) я обнаружил, что сполз до 42 места (из около 200 активных участников). Какое-то время ушло на вытягивание новых задач и разглядывание того, как другие участники решают мои задачи. В 11:00 я вернулся к написанию солвера.( Read more... )

(Это первая часть рассказа, а вот вторая и третья)

В этом году ICFPC был про оригами.

Вам дается контур сложенной из бумаги плоской фигуры (в виде координат точек) и вы должны ее сложить. Для тех, кто уже офигел и не знает, за что хвататься, дается дополнительная подсказка - еще одна "картинка", показывающая все ребра и складки в этом контуре -- представьте, что вы смотрите оригами "на просвет", однако при этом все точно совпадающие складки и ребра сливаются воедино. Организаторы называли это "контуром" и "скелетом". Еще про оригами известно то, что оно сложено из листа бумаги размером 1x1. ( Read more... )

Во-первых, поздравляю человека и парохода jabber.ru с победой в lightning раунде.

Во-вторых, на этом месте мог бы быть отчет, но писать особо не о чем. В этом году я пробовал что-то сделать самостоятельно, но буквально сразу увидел (кажется, на IRC) слово SECD и в результате отвлекся на чтение книжки Хэндерсона "Functional Programming Application and Implementation", которой явно вдохновлялись организаторы. В результате я узнал много нового и интересного о том, как можно использовать camlp4, чтобы реализовать "компилятор" из сделанного тобой DSL в OCaml, а также о том, что такое SECD-машина (как она дана у Хэндерсона, а не урезанный вариант из задачи этого года).

После возни с полноценной SECD-машиной мотивация делать обкоцанную SECD-машину у меня как-то пропала, и я для себя на этом ICFPC-2014 закрыл. А что у вас?

Если вдруг кто еще не знает, то в этом году ОНО будет с 25 по 28 июля. Кто собирается участвовать?

Вот они, родимые.

Мы - на позорном 131 месте. Где-то за 20 минут до финиша, когда мои товарищи по команде вырубались после бессонной ночи, возник вопрос - какой же солвер сдавать в качестве финального?

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

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

На мелких картах второй тред успевал перебрать все (или почти все) и выбраться из практически любой ловушки. На больших же картах он рисковал со временем пожрать всю память и быть убитым OutOfMemory Killer-ом (который живет в ядре linux). Если бы это произошло, то мы бы на такой карте не набрали ничего. Осознание этой засады пришло слишком поздно, и сделать какой-то монитор/ограничитель мы уже не успевали.

Забоявшись out of memory, я убедил полусонных Женю и Ваню, что сдавать надо первый вариант. В результате мы вылетели в первом раунде.

Второй вариант набрал бы как минимум 7200 очков (я запускал его на оценочных картах с лимитом в 30 секунд, а за 150, думаю, он мог бы набрать и больше) и мы были бы где-то в районе 50-60 месте. Ну, как известно, если бы да кабы ... :) Мораль придумайте сами.

Посмотрим, что будет в следующем году.

А кто что себе думает про ICFPC-2012? Кто собирается участвовать? На чем писать? Я в этом году твердо намерен не пропустить мероприятие - кто хочет объединить усилия?

UPD: договорился с _navi_ и antilamer.

Кстати, а кто из участников ICFPC-2010 был из Киева? Я знаю себя и murkt (уверен на 90%), а кто еще?

Этот пост - о том, как мы строили машины, фабрики и гнали бензин на ICFPC-2010.

Кто еще не знает, что это такое - может пройти в сад почитать мой отчет об ICFPC-2006. Всех же остальных я не буду мучать долгими вступлениями и сразу перейду к сути.( Read more... )

Имя команды: li-monad (спасибо aleksey/jabber.ru за идею)
Состав: я, endless-world, iakovz, при участии blancus.
Итоговый бал: 2234.7171 (12 problems solved)

Поскольку scoreboard традиционно перестал обновляться за пару часов до окончания соревнования, мне сложно сказать, какое же место мы заняли в конце-концов. Если все остальные участники расслаблялись перед финальным свистком и ничего не делали, то это будет 59-е место.  Но скорее всего в расстановке сил перед самым финишем наверняка произошли существенные изменения, и я буду рад, если нас не "выдавят" хотя бы из первой сотни.

( Читать в деталях )

Сорока на хвосте принесла новость о соревновании для (русскоязычных) программистов, которое будет проводится с 5-го по 12-е марта.

Организаторы обещают фан на уровне ICFPC. Надеюсь, образца 2006-го года :)

Читаем и участвуем: http://stanfy.com.ua/contest/

Под катом - немножко ссылок на ICFPC-шные дела( Read more... )

Это вторая часть рассказа. Линк на начало.

12 Jul 2008.

Однако, я только и успел, что выписать определения сообщений, которые придется принимать от марсохода и передавать ему. Сразу после этого в jabber-е прорезался yvl, который двигает науку в области робототехники. Сам он по стечению обстоятельств в соревновании участия не принимал, но интересовался моим мнением о задаче.

У нас завязался увлекательный разговор, первые пятнадцать минут которого напоминали скорее монолог: yvl вещал, я записывал на листик неизвестные мне термины и понятия. В результате я вынес из нашего общения несколько ценных крупиц знаний:
1)Все могло бы быть и хуже( Read more... )