thirteen

Результаты ICFPC 2011, THIRTEEN team

Мы заняли 16-е место, а могли бы и влететь. Другие харьковчане - 14-е. Им поздравления!

Zombie Apocalypse - tilarids

The contest is already over, but it was so awesome that I couldn’t stop writing programs in “Lambda The Gathering” and trying to implement some crazy strategies that were discarded during the contest. I’ll show you one of my latest programs, but let me first tell you a few words about syntax of our programming language.

This programming language was developed during the contest and it’s easy to write *and* optimize “Lambda The Gathering” programs in it. It is not possible to check the player/opponent state during the execution with it so we’ve used Java code for that. Program example:

power@0 = 8192; // C++ style comments work fine
@24 = (attack 0 0) (get 0);
@24 = (attack 1 0) (get 0);
pois@1 = ^x. (help x x @power);
!clear @0;
part@0 = \x. ((@pois x) (copy (K 0 x)) (succ x));
!clear @1;
part_func@1 = ^z.^y. ((get 0) (y z));
@128 = (S zombie @part_func);
// optionally decrement 0 from Java code
@128 += @@ 0;
address@2 = 66;
@129 ~ zombie1 = (zombie 0 (@part_func @address));
// optionally decrement 0 from Java code
!continue zombie1;
@2 += dbl @@;
@130 ~ zombie2 = (zombie 0 (@part_func @address));
// optionally decrement 0 from Java code
!continue zombie2;
!clear @2;
@2 = 198;
@131 ~ zombie3 = (zombie 0 (@part_func @address));
// optionally decrement 0 from Java code
!continue zombie3;

The code above destroys the dummy opponent in 177 turns(we’ve invented faster solution after the contest but the code above is what was submitted). The syntax is straightforward. You can put any lambda/SKI expressions to the slots(\ and ^ are interchangable), you can assign some identifiers to slots (e.g., power, pois, part) and you can use @power, @pois syntax to get field from the identified slot. Also with “+=” syntax you can apply some card to the existing field. “!clear” clears the slot. Interesting part is “!continue” syntax. You can stop evaluating any expression, evaluate something else and then continue the evaluation of the initial lambda. Using it you can prepare a zombie, then prepare a gun, and fire the gun and put zombie in 2 turns making it impossible to revive the slot. There are also some cool features of the language, but the description above should be enough to understand the code below.

During the contest we discussed a lot of crazy ideas. One of the ideas was “Zombocalypse”. That is, prepare some zombie for the oponent slot that will zombie proponent slot that will zombie oponent slot and so on. It is one of the ways to implement recursion. We even haven’t tried this approach because of its complexity. But after the contest I’ve remembered about the idea and tried to implement it. Soon enough I got the understanding that I’ll need at least “inverse” function that will do (255-i) for me. I know the only one way to implement it - Church numerals(if anyone knows simpler ways, please inform me). But using Church numerals means you can’t do anything useful in 1000 applications. So I’ve decided to weaken this restriction.

Side note: I think that this 1000-application rule is absolutely awesome. E.g., it will be possible to end the game in 85-89 turns with 3839 applications. So this rule made all the fun!

After deleting that restriction, I’ve written some functions to work with Church numerals:

church_zero@0 = \f.\x. x;
church_succ@1 = \n.\f.\x. f (n f x);
church_pred@2 = \n.\f.\x. n (\g.\h. h (g f)) (\u. x) (\u. u);
church_iszero@3 = \n.\t.\f. n (\x. f) t;
church_sub@4 = \m.\n. (n @church_pred) m;
convert_from_church@5 = \n5. (n5 succ zero);
church_mult@7 = \m.\n.\f.\x. m (n f) x;
church3@8 = \f.\x. f (f (f x));
church5@9 = \f.\x. (f (f (@church3 f x)));
church15@10 = (@church_mult @church3 @church5);
church17@11 = @church_succ (@church_succ @church15);
church255@12 = (@church_mult @church15 @church17);
inverse_church@13 = \x. @church_sub @church255 x;
church_not@14 = \x. (@church_iszero x (\f.\xx. f xx) @church_zero);

The code to make the zombie portal:

power@15 = 8192;
@16 = (attack 1 0) @power;
@16 = (attack 0 0) @power;

And the most interesting part - Zombocalypse itself:

get_next@17 = \n. (@convert_from_church (@inverse_church (@church_succ n)));

part_func@18 = \n.\b.\f.\id. (help (@get_next (id n)) (@get_next (id n)) @power)
                             (zombie (@convert_from_church ((@church_iszero (id b)
                                                                            @church_succ
                                                                            I) (id n)))
                                        ((id f) ((@church_iszero (id b) @church_succ I) (id n))
                                                 (@church_not (id b))
                                                 (id f)));
zombie_func@19 = \ii. (help 0 0 (ii @power))
                      (help 254 254 (ii @power))
                      (zombie (ii 0) (@part_func @church_zero @church_zero @part_func));
@255 = (help 255 1 10000); // make portal for opponent zombies
@20 = zombie 0 @zombie_func; // spread the infection

Each zombie prepares the room for the next zombie and zombies opposite slot. The preparation takes 1750 turns. It works as expected - in 254 turns after the infection there is none alive in the world except one slot (let’s call this slot Will Smith or simply “The Legend”). And if you count the max applications you’ll end up with the enormous number - 822840! That’s the cost of Church numerals, arithmetics and if-expressions. I believe it’s possible to make the preparation to take less time and it’s surely possible to decrease the number of applications. But it doesn’t matter right now for me, what really matters is the REAL FUN I got writing this code and ALL THE FUN I got from the ICFPC 2011. Thank you, organizers!

ICFP Contest 2011 отчет (writeup) - San

Провели соревнование в 2011 году классическим составом в том же месте.

Контест удался.

Принимало участие на удивление постоянное количество человек - семеро. Почетным гостем в этом году был маэстро dzhulgakov, и собирается продолжать! Мы использовали Java, как lingua franca для большинства участников.

Накануне мы успешно разобрали картинку на сайте организаторов, нашли там изображение омега комбинатора и намек на MTG, что дало повод всем прошерстить литературу по комбинаторной логике. Как оно ни страшно выглядит, но после всего прочитанного задание выглядит уже не так заумно, а когда мы сразу увидели комбинаторы в виде птичек, то стало ясно, что наконец-то функциональщина. В первый день сразу было написано почти всё (компилятор из лямбды в последовательности загрузки комбинаторов в сервер). Язык выглядит так (его расширения не приведены в этом примере)

@1 = 8192;
@0 = (^x.
 (help x x ((get 1)))
 (get x) x) 0;

Расскажу о прочих находках и интересных вещах, вперемешку.

* Мыслители sas и rst7 придумали само-модифицирующуюся программу. В нее приписываешь ноль, а у нее растет хвост из команд SUCC, и после вызова она становится длиннее, а внутри у нее число 0+длина доступно как аргумент, чтобы там может кого-то подлечить или атаковать. Это однотактовый (1 такт на запуск) сканирующий выполнятель.

* Рекурсию, ограниченную 1000 редукциями, можно делать как использованием Y-комбинатора, так и с использованием команды GET, с последующим к ней примененем своего операнда: @0 = x. (dec (K 5 x)) ((get x) x)).   Если добавить нолик, то он попадет в x, выполнится DEC 5, а затем возьмется копия самого себя (GET 0), и применится снова нолик, и всё повторится. Это не совсем рекурсия, тк у нее нет условий, а скорее tail call.

* Мы пробовали нумералы Чёрча, и они работают, но сами понимаете. С другой стороны на них удобно тестировать парсер и конверторы из одной формы в другую.

* Наш компилятор кажется не до конца оптимальный. Чего-то мы не поняли. И еще этот язык не ленивый, а вовсе даже strict. Это из-за того, что оно всё приводится в нормальную форму уже при загрузке, сервером. Это неприятно, т.к. код получается больше чем мог бы быть. Dzhulgakov расширял наш лямбда-язык до последнего дня, дорасширялся так, что стало страшно смотреть, с самого начала выйдя за уровень лямбда-калькулюса ВНИЗ к уровню комбинаторов, так сказать, прагмы компилятора. Javacc оказался в умелых руках dzhulgakov-a мощным инструментом. Теорию о преобразовании lambda v SKI нашли в википедии. Преобразование SKI в право-лево аппликативную последовательность увидели у организаторов на примере.

* Понятное дело, мы смоделировали всю runtime-систему, так что знаем состояние и врага и наше собственное точно как положено.

* Самым важным куском бота, дающим нам большую фору, если не 100% победу, является программа (rst7/sas/tilarids), запускающаяся самой первой, которая пробивает брешь в 255 ячейке противника, заселяет туда зомби, который один сносит 64 ячейки подряд под ноль с использованием рекурсии и двух команд help. Программа запускается 4 раза с разными аргументами, и это позволило нам покрыть всего противника нулями. Кое-кого это убивает к 177 ходу целиком. Программу написали и отладили за 4-5 часов до конца, так и оформили окончательный сабмит.

* Как и в любой игре, существуют защитные стратегии, и нападательные. Надо было найти баланс. Смешать всё вместе. Поэтому после зомбо-бомбера у нас грузится сначала маленькая программа-камикадзе, которая умеет рубить с плеча подозрительные цепочки врага. Потом, пока она их рубит, в промежутках подгружается следующая программа-камикадзе, которая на всякий случай умеет делать это быстрее. А когда и она загрузилась и даже работает, то грузится третья программа, которая умеет убивать тоже быстро, но не тратя собственных сил. Для этого она  выстреливает во врага, а потом себя лечит, всё в пределах 1 хода. Кушает она из ячейки с жизнью 65535, каковой баланс и поддерживает. Стреляет (когда сканируя) - за 2 такта на выстрел (инкремент цели + запуск). Пока делается подгрузка и расстрел противника, специальная программа, с более высоким приоритетом, мониторит на тему убитых ячеек (у которых жизнь 0) и восстанавливает их, приостанавливая выполнение прочей задачи в текущей точке. Потом прочая задача продолжается. Каждая программа (записанная в виде примера (см выше)) знает в какие слоты она грузит свой код, и слушая глобально изменения врагом своих слотов, может отменить свою дальнейшую загрузку (т.е. уже мусор в слоте), а потом рестартовать загрузку.

* Сразу после загрузки какой-то подпрограммы, мы копируем ее в известное место. Если одну из копий убьют, то она восстанавливается тут же из второй (get XXX). При запуске участвует только одна. С самым большим приортетом среди прочих программ дейтвует проверялка, не убили ли кого-то за последний шаг. Если да, то запускается лечилка тоже с макс приоритетом.

* Кое-где константы генерятся в текущем контексте  - вдруг можно украсть у оппонента, или скопировать и проинкрементить. Все возможные варианты генерируются в виде строк, потом компилируются и выбирается самый короткий вариант (на крайний случай есть 1 способ генереции константы с помощью dbl/succ/zero , он вам известен)

* Способ выбора слота врага для отстрела вначале был реализован собиранием статистики по активности его по ячейкам (записи в ячейку), и потом выбирается ячейка с самой длинной программой самая последне-модифицированная. Она и убивается. Затем был написан другой алгоритм, который определяет, какая ячейка читается (get) в процессе работы вражеских программ за последнее время (таким образом, выбирается самая “горячая” часть программы). Мне кажется, надо было брать больший срез времени для нахождения этого места, но работало не хуже, а сильно оттестировать не успели.

* Из нереализованного: анализ вражеской программы на сайд эффекты, с целью украдания. Был написан анализатор (трассировщик), который собирал сайд-эффекты, но использовать эту информацию и стырить произвольный код не успели. Потенциально можно было бы строить аттакера, а лечилку стырить, или строить лечилку, а аттакера стырить.

* Из нереализованного: запустить публичный сервер, к которому можно подсоединиться и сыграть в онлайне, и анонсировать его на IRC. Позволило бы нам, и другим посмотреть на чужой лямбда-код 8-). Не сделали это, т.к. у меня были сомнения, что хоть кто-то прийдет и вот так откроется. На удивление, моральных преград я не испытывал 8), т.к. организаторы явно не запретили это делать в своем задании.

Конечно, была куча косяков, и после бурного успешного развития бот из-за своей сложности начал крениться и падать. В начале, не защищающийся бот выглядел очень неплохо, но потом его начали убивать, и он стал защищающимся. Защита замедлила выполнение атаки и баланс резко изменился. Вот тут и следовало бы искать золотую середину, но бот уже несколько накренился в смысле сложности кода, и середина искалась с трудом.

По результатам мы далеко не первые. Хотя наша лямбда со 177-ходовым результатом кажется превышает всё что мы видели во время соревнований на тестовом сервере (и только что наткнулись на ссылку со 187-ходовым алгоритмом таким же), но, по-видимому, победители знают что-то еще, до чего мы не догадались. И таких людей, которые что-то знают, будет человек 20-25, думаю (я боюсь еще оказаться оптимистом).

Примечательно, что в этом году ICFP (fp - это functional programming) наконец-то был функциональным (хотя бы по форме), после трех лет непонятно чего. Функциональности было достаточно, и она постоянно стояла на пути (оптимизация кодов, думание в комбинаторах и лямбдах). Хоть основной алгоритм (игровой) был без привязки к лямбдам. Наверное этот факт и вызвал наибольший подъем духа участников. И, я смотрю, не только у нас, а и в отзывах на irc/jabber. У нас были полностью и в удовольствие заняты все участники команды. По этому поводу мы скажем троекратное: УРА! УРА! УРА!

P.S. отчет tilarids-a, отчет brox-a.

P.S. Наш сабмишн лежит в лямбде 8). Или по адресу http://thirteen.static.tor.hu/THIRTEEN.tar.gz

Ссылки на

Специально рекламирую тусовочную на jabber:icfpc@conference.jabber.ru  которая обычно активна в процессе контеста (там есть логи, что хорошо)

Свои значащие следы в интернете оставили также:

_adept_:  http://users.livejournal.com/_adept_/106759.html

TBD: http://www.forumlocal.ru/showflat.php?Cat=&Board=prog&Number=9571897&fullview=&src=&o=&tistart=all&vc=1&showlite=&fullview=

hack-the-loop: http://xoposhiy.livejournal.com/106201.html

thiscodeismade:  http://codeforces.ru/blog/entry/477?

пока еще ничего больше не нашел.

Team THIRTEEN отчет ICFPC 2010

ICFPC удался.

Всего приходило и втыкало в задание человек 11, но одновременно присутствовало максимум 9, а в субботу и позже коллектив был в среднем 6 человек, а в последний день 4. Задание было как раз такое, что думать могло много человек одновременно друг другу не мешая, а только конструктивно делясь идеями, и можно сказать, что задумка набрать толпу - удалась.

Активно программировали только 2 человека: tilarids сидел и на питоне делал интерфейс к сайту для перманентного сабмита решений, а я (sannysanoff) на Java реализовывал идеи,  которые опускались ко мне сверху, из облака наших думателей (RST7, SAS, Сева Демидов, Морозов и др.).

Вначале:

Мы собрали пустую фабрику из входа и выхода, и получили ихнюю зашитую последовательность, которая шла с сервера на фабрику. Потом взяли какую-то типовую фабрику (чуть ли не из примера), и смоделировали ее на компе. Но так как мы не знали внутренностей гейтов из которых она построена, то пришлось матрицу внутренней логики находить перебором: запустить с каждой матрицей истинности и посмотреть на выход от фабрики и сравнить его с эталонным (с сервера). Так, на эмуляторе, подавали  ихнюю вычисленную последовательность на фабрики, и в конце однажды получили такую же выходную. Текущая матрица была искомая.

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

Самое интересное было создать фабрику, которая по их зашитой последовательности генерирует тот же самый префикс. Для этого все мозгом очень долго придумывали макроэлементы: генераторы константных последовательностей и задержки. Исписаны тонны бумаги. Наконец, используя цепочки задержек, создали первый генератор произвольной последовательности. Попутным выводом стало то, что он не должен зависеть от входа. Т.к. вход мы знаем только первые 17 символов. Этот генератор на каждый символ содержал (позиция символа * генератор_задержки + 2 блока), и стало быть увеличивался геометрически с длиной требуемой последовательности.

Тем не менее, мы могли генерировать некоторое топливо. До тех пор, пока формат топлива был неизвестен, подобрали топливо 2,2,1,1,1,1,2,1,1 которое что-то давало, и даже кормило какие-то машины. Счет был открыт, ура.

Произошло это еще в пятницу к ночи.

Как только произошел первый контакт, люди разбились на хакателей топлива, оптимизаторов фабрик, сабмителей на веб.  Достославный RST7 за компанию с SAS и Morozov провели 60% времени оптимизируя фабрики и дооптимизировали их до состояния 1.6 гейта на символ, уже после середины контеста.

Тут же существующие “generic” топливы, которые подходили к многим машинам, перекодировали в новые фабрики, и стали снова заливать.

Затем RST7 и кто-то еще занялись декодированием структуры топлива. Декодирование целочисленных констант велось следующим образом:

1) заметили в последовательности топлива циферку. 2) Заменили ее на следующую циферку (инкрементнули) 3) сгенерили фабрику 4) засабмитили к какой-то машинке 5) почитали сообщение об ошибке - там было написано “топливо 5 танков из 9 ингредиентов”.

Если число какое-то поменялось, значит нашли новое представление.

Числа представлялись с переменной длиной. Мы вычислили, что

0 = 0

1 = 1

220 = 2 (типа такого)

2210 = 3

2211 = 4

….

2210000 = следующий интервал

2210222 = конец интервала этой длины

22220022222 итд

Написали декодер и енкодер чисел, и отдали RST7 сотоварищи на декодирование _структуры_ топлива.

В это время я и tilarids тратили время декодирование машин: целочисленные константы и их

троичное в машинках. Еще оказалось, что числа в машинах (ссылки на танки) закодированы иначе:

0 = 0

10 = 1

11 = 2

итд (отличается от констант в топливе).

ВСЁ ВРЕМЯ МЫ МАТЕРИЛИ ТОГО, КТО ПРИДУМАЛ ЭТО ПРЕДСТАВЛЕНИЕ ЧИСЕЛ. Оттого полного понимания у меня на момент написания отчета не осталось, а бумажки мы выкинули. Остался код, который работает, декодит числа.

Полный и верный енкодер машинок был написан за день до окончания.

Полный и верный енкодер топлива был написан за 7-8 часов до окончания. До того какие-то топлива НЕ работали, и я очень нервничал, потому что решалка машинок решала их правильно, а сайт топлива к ним не принимал,  и говорил “у тебя лезет из нижней трубы”.

С помощью jabber.ru (Алексей Щепин) и _adept_ (Дмитрия Астапова) был осознан правильный (а не шаманский) формат топлива, как раз за 7-8 часов до окончания, за что им и спасибо! Сразу все решенные машинки залились на сервер ок.

Т.к. последовательность наших мытарств не представляет интереса для публики, то сразу опишу наши 2 алгоритма, представляющие какой-то интерес: генерилка фабрик и решалка машин.

Генерилка фабрик by RST7 and SAS:

(google docs hosted)

Слева представлен самогонный аппарат со своим змеевиком по левым входам и выходам гейтов 0..2). На практике он делается размеров требуемой цепочки. В момент T-нулевое на свои правые входы он ожидает единоразовой подачи некоторых констант, которые, смешавшись с нулем на соседнем входе, подадут некоторые ингредиенты в змеевик, которые затем, подымаясь с каждым тактом и модифицируясь проходимым ими гейтом, каждый в свое время выйдут на выход.

Важно понять, что выходная последовательность  эта будет константной и определяться будет единственно константами на правом входе самогонного аппарата (на рисунке это C, C2,итд).

Для генерации этих констант требуется симуляция (или очень умная голова, которые у нас были заняты другими делами). Подбираем константу на 0 гейте, чтобы получить требуемый выход первого символа. Запоминаем, и больше не меняем. Затем варьируем константой при 1 гейте. Она произведет какой-то результат в этом гейте, потом он подымется, модифицируется 0-м гейтом, и попадет во вторую позицию потока. Поварьируем константой  при 1 гейте, найдем вариант, когда этот второй символ станет требуемым. Зафиксируем ее.  Подберем константу при гейте 2, итд, до низу.

Обратные связи отмечены волной на рисунке (почти везде).

В реальной жизни для формирования константы НОЛЬ на правом входе гейта используется просто обратный линк с самого гейта. Для формирования ДВОЙКИ используется блок с зацикленной левой стороной (см рисунок справа посередине). Для ЕДИНИЦЫ используется некое свойство гейта и троичной арифметики, которое позволяет заменить операцию “подключение константы ОДИН на правый вход” операцией “подключение константы ДВА на левый вход, а змеевик здесь пустить на правый вход”.

Так как на 2 из трех симоволов требуется по 2 гейта, а на оставшийся символ - 1 гейт, стало быть размер этой фабрики - 1.6666 от размера сообщения, справедливо считая, что констант где-то поровну.

И это всё о генерируемой фабрике.

Решение автомобилей - подбор топлива - про критерию Димы Шутя (dshoot) методом случайных чисел.

Как выяснилось по ходу дела, автомобиль представлен отсеками, которые суть матрицы определенных типов, к которым слева умножается вход (вектор - воздух), и затем получается результат (вектор N) который идет на сравнение с таким же вектором M, получаемым из нижней трубы.

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

Далее, этот метод очень плохо работал на задачах, в которых именно противоречие chambers составляло всю суть. Потому что мы оптимизировали матрицу под первый chamber, а потом, когда появлялось решение, лишь проверяли, удовлетворяет ли оно остальным чамберам. Чаще случалось, что не удовлетворяет….

Но другого метода мы не написали. Зато он работал на многоингредиентных топливах, и на одноингредиентных одинаково.

Это всё о методе.

——-

За 5 часов до окончания стали вливать довольно примитивные автомобили, которые решались нашим же генератором. Влили до количества 69 штук, с залитыми ранее. Всего мы решили около 700 чужих автомобилей. Рассуждения показали, что надо было лить автомобили как можно раньше, всё равно за них получались бы баллы понемногу.

Решение оформлено в виде Java программы, куда кормишь текст машины в командной строке, а она генерит или не генерит описание фабрики для топлива на стандартный выход. Для этого проходит декодирование машины, поиск матрицы, кодирование решения в триты, генерация фабрики (многократная эмуляция на модели и подбор коэфф), генерация её в текст . И вот там сидит  товарищ tilarids со своим питоном и регулярно запускает это всё, выбирает получившийся или неполучившийся ответ, и если что, то сабмитит на сайт. И на нашем конце содержит базу: что было успешно отослано или нет.

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

Наше место таки чётко тридцатое. Снизу нас подпёр _adept_ сотоварищи, а jabber.ru на 21 месте, где ему и привет!

Наше участие в 2010 году

Команда приняла участие в ICFPC 2010, за час до конца была в тридцатке, отчёт последует здесь.

Algorithm used in submission, team THIRTEEN, ICFP Contest 2009 [eng]

There were several requests from english-speaking audience about the algorithm

which was used by our team. So, this article may give some description.

Full source code is in at the end of that post (subversion url).

Team Thirteen algorithm contains the following parts:
————————————————————

1) Lambert transfer: given the

• current coordinates
• motion vector
• exact desired transfer time T
• destination point,

calculates the impulse vector. This is done analytically (matlab+books), and very fast algorithm is implemented (10 iterations max). The results are not exact, but are used as a basis for

• estimating the travel costs to any satellite
• actual transfer setup (see “9)”)

2) Choose the right time to start. Given the

• current position
• destination satellite
• 2 time brackets

calculates the delay (t0) before Lambert transfer and duration T of the transfer, so that transfer has optimal parameters (speed or fuel usage).

3) Moon gravity - when some “earth/moon” point is passed, Earth gravity is not taken into the account when calculating Lambert, and moon-centered calculations are performed.  Otherwise, moon is excluded from the Lamber equations same way.

4) bin -> java compiler. Produces java class for fast calculations, for each task. Input/Output as per specification, 1 time tick is calculated. ”clone” method for previews of the future.

5) Simulator: given the initial impulse and delta T, calculate final state of the world (T iterations of VM).

6) For task 4001-4004, bin -> java compiler which does NOT calculate all satellites, only earth/moon/traveller coordinates. This is done by tracking data dependencies in bin file and excluding all non-relevant calculations which result in non-needed ports. 15-20x speedup is achieved.

7) caching of satellites position for the whole time range of problem, for faster lookup at any time point (done once per problem). Together with “6)” it gives fast “future preview” ability with regard to satellites.

8 ) Travelling salesman problem, reducing the use of fuel, without visiting fuel station. By the way, score was added for visiting it (later we discovered it). When choosing next satellite, we optimized t0, and T (see “2)”) and used search depth of 2 satellites (current, next, one after next), and criteria was to minimize sum of fuel spent.

9) Precise meeting. Given the satellite, using the Lamber transfer, get the initial impulse. Then, minimize the function distance_to_destination_with_initial_impilses(Ix, Iy) function is implemented as a simulation flight using fast java implementation of formulas from bin file (see “4)” and “6)”). Using gradient descent for optimization. Problem: when travelling towards earth, calculates very slowly due to unsophisticated algorithm.

9a) when optimization fails due to very long computations, travel anyway with best found impulse, then calculate new impulse in the middle of travel. Repeat if needed.

10) another algorithm of travelling salesman, where speed of travel was optimized, but fuel was refilled at the base station, was developed, but due to competition time constraints, was not polished, and used as backup algorithm. This helped to solve 1 problem, where main algorithm failed (!) during the separate top-10 competition in the aftertime.

Материалы по теме ICFP Contest 2009

http://vimeo.com/album/126865/video/6613815 - видео с ICFP Conference с разбором полетов

http://san13.habrahabr.ru/blog/68995/ - популяризаторская статья на ICFP тему

http://vidiowiki.com/watch/m844dyn/ - интервью с победителем этого года (японец).

http://shinhoge.blogspot.com/2009/09/icfp-programming-contest-2009.html - его блог (англ).

http://john.freml.in/icfp-contest-2009-debrief - человек подбил итоги по top10

THIRTEEN заняли второе место на ICFPC 2009

Пришла почта от организаторов, наше - второе место. Результаты еще не опубликовали в инете (кто в танке - сам контест был летом, про спутники вокруг земли).

Тем не менее, вчера в Эдинбурге на ICFP конференции было награждение первых мест (первое в блице, первое в основном зачете, и приз симпатий жюри).

Мы собрались туда поехать, но визы нынче делаются дольше, чем 2 недели, и даже сегодня еще не готовы. Поэтому поедем позже в Эдинбург просто погулять, если всё будет хорошо.

Первое место заняла команда shinh (C++) из Японии, которая заняла второе место в прошлом году. Первое место в прошлом году заняли гугловцы.

Первое место в этом году в блиц-раунде занял человек из Севастополя по имени Aleksey, и в прошлом году тоже он.  Он тоже не получил еще визу, и не смог вкусить лавров.

До следующих встреч!

ICFP Contest 2009, Java vs Haskell performance investigation

Джентельмены!

Я взял в руки Хаскель, и за один световой день (суммарно) написал компилятор бинарных файлов от ICFPC 2009. Он компилирует формулы из obf файлов в быстрый Haskell вычислитель. Ну, вместо интерпретатора.

Я преследовал следующие цели:

• вспомнить Хаскель (а то в последнее время я уже его позабыл), и написать идеальный компилятор. В нашем блоге существует ссылка на аналогичную разработку.
• замерять время, за которое я это напишу (тест провален - медленно. Но я делал это на мини-ноутбуке на коленках, и иногда отвлекался на детей и жену)
• написать программу для товарищей чтобы смотрели как это выглядит на Haskell.
• измерить lazy/strict имплементацию в Haskell по скорости
• сравнить производительность с нашей текущей VM (на java)
• сравнить производительность с идеальной VM, написанной на java.

Что я могу сказать по этим пунктам? Хаскель на данной задаче рвет Джаву на куски (Haskell в 2 раза быстрее чем Java).

Задача: задание 4001 целиком (все объекты), посчитать итерации/сек.

Environment: Intel Q6600, Arch Linux 64bit, GHC 6.10.3, JDK 1.6u14, all single-threaded

Результат:

• Java version (as sent to contest): 22K iter/sec
• Java version (ideal): 44K iter/src
• Java version (ideal, 32bit): 32K iter/src
• Haskell version (lazy): 1.73K iter/sec, up to 8.1K iter/sec ==> fail.
• Haskell version (strict): 96K iter/sec.

Идеальная VM на Java выглядит так:

public class Vm {
  double m2039;
  {m2039=0.0; }
  public void fw(double[] i, double[] o) {
      double t60=((6.67428e-11*t59));
      double t61=(((((t53*t53)*t53) != 0) ? t60/((t53*t53)*t53) : 0));
      m2039=(t12+1.0);
          o[0]=((((Math.sqrt (((t1989*t1989)+(t1987*t1987))))-6357000.0)<0) ? ...
  }
}

Что мы здесь имеем? Все временное в пределах итерации вынесено в локальные переменные, постоянное в members, выражения приведены в скобках (кроме повторно использующихся, которые пошли в локальные переменные). Константы сделаны константами. Порты сделаны массивом, можно было дать им персональные имена, но их мало, и на производительность это не влияет. Один вызов функции переводит объект в новое состояние (тик +1). Приятной особенностью задания (или решения?) является отсутствие ссылок вперед во временных переменных.

Неидеально откомпилированная виртуальная машина  выглядит так: вместо временных переменных - members. Вместо вложенных скобок - сохранение результата в members на каждом шаге. То есть, практически один к одному по спецификации, выданной в PDF к заданию:

d57 = d2042;
d59 = (d13 == 0.0 ? d56 : d57);
d60 = d34 * d59;
d61 = (d55 != 0.0 ? d60 / d55 : 0.0);
d62 = d45 * d61;
d63 = d62 + d41;
d64 = d63 * d4;
d65 = d2114;
d66 = d9 * d9;
d67 = d11 * d11;

Теперь смотрим Haskell. Здесь не принято модифицировать объект, и не имеется легких средств для этого. Вместо этого мы описываем объект (algebraic data type), затем функцию, которая создает первоначальный экземпляр, и еще пишем функцию, которая создает из одного экземпляра другой, отстоящий от него на 1 тик. Код получается похожий на Java, но временные переменные отсутствуют, вместо них let- bindings. Тестирование состояло в выводе на экран результатов после 45000 итераций, всего состояния (чтобы вычислить все ленивые цепочки).

data VMState = VMState { m2039,...,o101::Double }
initState = VMState {m2039=0.0....}
nextState x (i16000,i3,i2)=
  let ....
      t18=((if t13==0 then 3.84399e8 else m2051 x)) :: Double
    in 
     x { m2039= .... , o39=(if (t1699-0.0)==0 then 0.0 else 1.0) }

В типе VMState параметры конструктора сделаны ленивыми. Если экземпляр VMState был порожден от другого экземпляра указанным образом, то он содержит ленивые заглушки (thunks, не знаю как сказать), которые находятся в куче. А если у нас 50000 тиков просчитать надо, то это надо пройти через 50000 экземпляров, у каждого из которых порядком параметров, и все ленивые. Короче, этот код дает нам 1.73К итераций в секунду, и это ужасно. Но стоит только заменить их на strict,

data VMState = VMState { m2039,...,o101:: !Double }

как тут же всё начинает шустро бегать. (96К iter/sec). В профайлере смотрим, что выделения лишней памяти практически нет (только экземпляры VMState), и нагрузка на GC крайне мала..

В принципе, этого может быть и достаточно, но, возможно, промежуточные варианты дадут нам какую-то надежду на lazy. В большинстве случаев нам в задачах 4001-4004 нужна только наша собственные пространственная позиция в ответ на импульс. Попробуем требовать только позицию, а не всю структуру с координатами планет и т.д. Нашей позиции соответствуют поля o2, o3 (output ports 0×2, 0×3 из спецификации). Скорость расчета получается 4.5К iter/sec, что в два раза быстрее, потому что прочие значения не рассчитываются!

Теперь попробуем оставить эти два поля strict, а все остальные поля сделать lazy! Скорость получается 8.1K iter/sec! Это наверное оттого, что garbage collector-у надо делать чуть меньше работы, потому что после присвоения strict-полю цепочка ленивых вычислений может быть освобождена сразу же, а не только после вывода результата в конце всех итераций. Она становится быстрее и легче доступной для сборки.

Почему Хаскель быстрее чем Java на нашей задаче? Наверное потому что он компилирует в бинарник, даже притом, что сгенерированный в нем код ужасен по сравнению с тем, который выдает C/C++. И, наверное, здесь лучше работает компилятор, который может быть уверен, что  одинаковые куски в выражениях (например, “m12345 x == 0″) достаточно вычислять только один раз. Роскошь, которую себе не может позволить Java. Для Java пришлось бы писать дополнительный код, который детализирует эти нюансы, а для Haskell вот, не надо.

Комментарии по коду компилятора (который лежит тут) :

1. он генерит full lazy variant (strictness annotations были добавлены руками по результату)
2. константы вставлены в user-friendly формате, а не побитово (надо побитово)
3. там внутре код который генерирует Java, он неактивен, но есть.
4. код компилятора с комментариями и пустыми строками, и веткой на Java - 238 строк.
5. компилятор достаточно производителен для bin4.obf (4 задание), код не оптимизирован (красоты для).

Улучшения и замечания к компилятору приветствуются. Спасибо за внимание.

This article was slightly tuned for google translation from Russian, hence the language.