thirteen

Ссылки на

Специально рекламирую тусовочную на 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.

Youtube

Перезалили несколько штук на youtube еще (все старые).

http://www.youtube.com/watch?v=mFPd2xtcseI
http://www.youtube.com/watch?v=m5pyK4hYjrI
http://www.youtube.com/watch?v=1xipQH3PGog
http://www.youtube.com/watch?v=39ZtWqZoPUo

episode 4002, speedy algorithm, score 723

Это посчитано кодом, который ушел в сабмит, но не заенаблен, потому что он не считает все случаи хорошо. Точнее, оказалось, что он считает 4002 случай лучше чем официально заенабленный алгоритм, но это нашли токо сейчас.

Оригинал 3.5М

(brox) Don’t Panic

А чего это я распереживался? Оказывается, наши последние сорцы из svn прекрасно работают, и выдают на гора соответственно:
4001-613.653
4002-678.975
4003-563.734
4004-610.659
Просто надо было запускать с параметром false, а не 0.
Т.е. Problem4Solver 4001 false
Так что я тулчейн подпилю слегка, и готово дело.