ICFPC 2011

(((S (K (S ((S (K S)) ((S (K (S I))) K))))) ((S (K K)) K)) awesome! was ICFPC)

ICFP Contest 2011 точно войдет в список лучших ICFP контестов всех времен. Причина тому - интересное непутанное задание, которое при этом довольно сложное и хорошо продуманное. Я, как и в прошлом году, принимал участие в составе команды THIRTEEN. Отчёты от команды можно найти на сайте http://thirteen.kharkov.ru(сейчас там только один отчёт). Здесь постараюсь дать описание контеста со своей точки зрения.
Для меня контест начинался вдали от команды(я находился в командировке в Лондоне). Прочтение задания вызвало бурную радость(я как раз готовился к контесту написанием парсера и эвалуатора для лямбда-калькулюса). Из-за удаленности от команды я решил код не писать, а сосредоточиться на изучении того, что мы можем сделать с помощью карт. Это оказалось правильным решением - мои коллеги написали всё намного быстрее и лучше, чем с моим участием :) Первая ночь прошла в попытках использовать Y комбинатор для создания рекурсивных функций. К сожалению, strict evaluation не давал этого сделать. И даже Y комбинаторы для applicative order не работали. Также не получалось и организовать рекурсию через SII. Утром пятницы я отправился на работу, но потратил большую часть рабочего времени на исследование системы. Результатом этого стала "недорекурсия" через get ячейки. А по окончанию рабочего дня пришло лучшее понимание того, как работает вычисление в предложенной системе, и это дало возможность вывести настоящую рекурсию по аналогии с выводом Y комбинатора. Это позволило писать рекурсивные функции, пробегающие по всем ячейкам. К счастью, организаторы ограничили количество аппликаций одной тысячей(к счастью - потому что увеличение количества аппликаций до 3839 позволило бы уничтожать противника где-то на 85 ходу). И из-за этого ограничения рекурсивные функции пробегались только по нескольким ячейкам и самоуничтожались после применения.
К этому моменту в Харькове был написан конвертер из лямбда выражений в SKI выражения и конвертер из SKI выражений в программы. В ночь с пятницы на субботу я пытался оптимизировать конвертер и генерировать с его помощью выражения, вызывающие рекурсивный обход ячеек. Результат: больше 89 ячеек за один запуск для односложных команд при помощи настоящей рекурсии не обойти. Ночью же вылетел в Харьков(и наконец выспался в самолете). По прилету обнаружил, что коллеги вовсю думают над однотактными и двухтактными пушками. Идея была в том, чтобы создать пушку, которая будет уничтожать вражескую ячейку и восстанавливать после этого vitality. Двухтактная пушка перенаправлялась на следующую ячейку двумя тактами, однотактная(гениальное изобретение Sas/Rst) - одним. К вечеру пришло осознание того, что нам нужно писать хитрого стратега, который будет решать, какие выражения применять. San создал инфраструктуру для написания ботов-стратегов, и к этому моменту был написан язык для описания действий(by San/Dzhulgakov). Я продолжал в душе лелеять надежду на использование рекурсивных выражений и начал создавать ботов и стравливать их в турнире. Конечным результатом этого процесса к 10 утра воскресенья стал SuicideBot(убийца-камикадзе) и, главное, ZombaBot - бот, который за ~150 ходов уничтожал ~40 ячеек противника, а еще за ~90 ходов стирал всю информацию из них. Начальная стратегия использовала настоящую рекурсию(синтаксис языка не приводится):

power@0 = 8192;
@1 = (S (attack 0 0) (attack 1 0) (get 0));
pois@2 = ^x. (help x x @power);
part@3 = ^n.^f. (f (S @pois succ n) f);
part_func@4 = ^y. (@part (y 0) ) @part;
@5 = (dec 0) (zombie 0 @part_func);
newpois@6 = ^xx. (zombie xx I);
newpart@7 = ^nn.^ff. (ff (S @newpois succ nn) ff);
newpart_func@8 = (@newpart 219) @newpart;

Также в это время формируется SanBot(by San) - консервативный бот, который умеет защищаться, уничтожая "горячие" ячейки противника. В свободное время он собирает более быстрые атакующие программы и переключается на них. San постоянно развивал своего бота, тренируясь на кошках - на SuicideBot и ZombaBot. В схватках с ZombaBot он научился закрывать порталы для зомби, а по дороге научился воскрешаться, восстанавливать команды из кеша, красть константы. ZombaBot тоже не стоял на месте. Sas подхватил идею с использованием copy для организации рекурсии и придумал, как с ее помощью сделать обход ячеек. В конечном итоге, этот способ и оказался самым эффективным способом обхода. Он дал возможность ZombaBotу полностью уничтожать противника за 4 запуска рекурсивного зомби, за 198 тактов. К этому времени submissionы SanBotа показали, что он слишком консервативен, и поэтому не столь эффективен. Воспользовавшись наработками, я добавил еще и UndeadRiseBotа - бота, который пытался уничтожить противника за 198 ходов, а после этого переключался на SanBotа. Этот бот оказался весьма эффективным - он крошил противников на неофициальном сервере и даже побеждал самого SanBotа, потому что использовал его же механизмы лечения. Мы продолжали развивать эту идею и оптимизировать код. Результат(язык получился довольно мощный и выразительный, а к концу контеста Dzhulgakov добавил в него и средства для ручной оптимизации):

power@0 = 8192;
@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);
// optional dec 0; here is done by UndeadRiseBot 
@128 += @@ 0;
address@2 = 66;
@129 ~ zombie1 = (zombie 0 (@part_func @address));
// optional dec 0; here is done by UndeadRiseBot 
!continue zombie1;
@2 += dbl @@;
@130 ~ zombie2 = (zombie 0 (@part_func @address));
// optional dec 0; here is done by UndeadRiseBot 
!continue zombie2;
!clear @2;
@2 = 198;
@131 ~ zombie3 = (zombie 0 (@part_func @address));
// optional dec 0; here is done by UndeadRiseBot 
!continue zombie3;

Этот вариант уничтожал противника за 177 ходов. В копилке наших знаний есть еще парочка оптимизаций, которые должны уменьшить код до 171-172 ходов. Хочется верить, что это минимальная программа, которая уничтожает безвольного противника.
Всё это время Sas собирал своего бота - SasBot, который использовал супероружие - зомбопушку (убить+стереть). Он добился того, что своей пушкой уничтожал и SanBotа, и UndeadRiseBotа. Но, к сожалению, он был готов слишком поздно и не очень хорошо справлялся с реальными противниками на официальном сервере, поэтому в последний момент было решено сабмитить UndeadRiseBota, который в душе - SanBot.

Выводы по окончанию контеста: по результатам битв на неофициальном сервере видно, что наш бот неплох, но далеко не лучший. Что особенно интересно - есть сильные боты, которые используют сходную с нами тактику, но при этом побеждают нас. Это значит, что мы просто не отладили бота окончательно. Еще стоит пожалеть о судьбе SasBotа. Он был готов слишком поздно, чтобы его достижения использовать в SanBot/UndeadRiseBot, и не был готов к submission самостоятельно. Основной вывод - нужно было начинать создавать ботов и описывать стратегии раньше. Тогда к концу контеста у нас бы было лучшее понимание того, какая тактика оптимальна.

Как я уже говорил выше - один из лучших ICFP contests за всё время, что я о нём знаю. Спасибо организаторам - великолепное задание и отличная организация. Спасибо каждому из команды THIRTEEN. Мне кажется, мы отлично сыгрались и можем и будем таким составом выигрывать :)

Talk: (Non) Comprehensive Guide to C/C++ Source Code Quality

I did a talk on C/C++ source code quality tools here at Quickoffice. I believe it could be helpful for the C/C++/ObjC developers(especially for those who care about quality). Here goes the list of the tools mentioned:

• CPD
• gcc
• clang
• Valgrind
• cppcheck
• EDoc++
• GCOV
• gcovr
• LCOV
• avalanche
• frama-c

(Non) Comprehensive Guide to C/C++ Source Code Quality
You can find LaTeX source and .cpp source files at github

Отчёт об ICFPC-2010

До чего дошёл прогресс -
До невиданных чудес!
Опустился на глубины
И поднялся до небес.

Позабыты хлопоты, остановлен бег -
Вкалывают роботы, а не человек.

Введение

ICFPC-2010 закончился еще в понедельник, но он оказался настолько емким, что полтора дня я только и мог, что кататься на велосипеде и проветривать мозги. Да и сейчас на подробный отчёт меня не хватит, так что ограничусь только кратким описанием того, что происходило со мной во время ICFPC-2010.
Итак, начнём с того, что в этом году меня пригласили поучаствовать вживую в харьковской команде THIRTEEN. Команда сыгранная и довольно сильная, до этого я с ними сталкивался на Sapka и ICFPC-2009.
На время прохождения контеста мы все собрались в квартире-офисе одного из членов команды. Отсюда первое и самое сильное впечатление: общение с живыми людьми, участие действительно в реальном времени(без перерывов на сон в собственной постели) - это нечто невообразимое. Представьте, что вы провалились в кроличью нору и попали в страну, где жители решают странные задачки, где сон и еда - досадные раздражители, а производительность труда взлетает до небес.
Второе впечатление - для участия в таком конкурсе нужна не команда из программистов, каждый из которых будет писать код. Нужны математики, физики, спецы по схемотехнике и прочие головастики. А программить могут 2-3 человека, не более того.

Кратко о происходившем

Задание повторять не буду, вы можете найти его краткое описание в отчете Futamura Rejection. В первую очередь, все бросились разбирать формат фабрики. Довольно быстро я написал парсер на Python, который генерил картинки в graphviz. Однако красивыми картинки сделать не получилось и в итоге все фабрики рисовались на бумаге. Как только с форматом более-менее разобрались, начали подбирать функцию гейтов. Мудрым решением здесь было предположить, что Undefined сигнала не существует и он заменяется 0. Я сделал простейший эмулятор на Python и с его помощью пытался подобрать функцию гейта(в виде матрицы). Но где-то в коде закрался баг и пока я его искал, sannysanoff на Java реализовал такой же симулятор без багов и нашел эту самую функцию.

А дальше пошло самое интересное: нужно было придумать генератор, который будет генерить фабрики в соответствии с нужной выходной последовательностью. При этом на входную последовательность завязываться было нельзя. Пока я крутил в голове всякие мысли со стейтами, переходами между ними и применением алгоритмов из теории графов для построения таблицы переходов между стейтами, Rst7 и SAS мозговым штурмом предложили довольно простой и естественный способ генерации фабрик из таких макроэлементов, как "генератор 0", "генератор 1", "генератор 2", "задержка", "задержка с вычитанием", "вычитатель". sannysanoff его быстро закодил(кстати, я впервые видел применение настоящего ООП в спортивном программировании. До этого я считал, что ООП слишком затратно, чтобы его применять при жестких временных рамках). Фабрики получались довольно большими, но работали.

Это был вечер пятницы. Начиная с этого момента начинается хмурая и безрадостная эпопея разгадывания внутреннего кода машин и топлива. Одна из причин этой хмурости (и один из основных лучей ненависти к организаторам) - в том, что попытки работать из под одного IP на нескольких машинах заканчивались провалом. Видимо, организаторы сделали привязку по IP и, соответственно, если заходить всем под разными аккаунтами, то аккаунты шарились между машинами, а при заходе по одному аккаунту высвечивался Internal Error. В итоге, я и sannysanoff зарегистрировали два фейковых аккаунта (fake001 и fake002) и использовали их через собственные туннели. Аккаунт THIRTEEN был под управлением brox и через его машину мы сабмитили официальные решения. Таким образом, несмотря на то, что участников было довольно много, разбираться с форматом данных могли только два, максимум три человека: ведь для того, чтобы понять формат, нужен был доступ к серверу.

Суббота прошла туманно. С утра я написал на Python скрипты, которые позволяли заливать тривиальные решения для тривиальных машин. Это дало ощутимый прирост к очкам. Всё остальное время было посвящено разгадыванию кода. Почему-то это шло очень медленно и к вечеру субботы полного понимания даже структуры топлива еще не было. Более-менее был ясен только способ кодирования чисел. Где-то в это же время я написал command-line интерфейс к парсеру на сервере, открыл к своей машине терминальный доступ и за разгадывание формата взялся Rst7. После нескольких часов, он предложил вариант формата, который мы успешно(!) использовали до утра понедельника. После этого Rst7 и SAS увлеклись идеей оптимального генератора фабрик. Они его разработали, хотя я до сих пор лучше понимаю, как работает первый вариант генератора.

Таким образом, к началу воскресенья у нас не было еще формата описания машин и не было никаких наработок по алгоритмам их решения. Я не помню точного времени, но где-то в этот момент, руководствуясь подсказками из чатов, до меня начал доходить формат описания машин. Однако полностью это понимание сформировалось позже. Читая отчёты других команд, я завидовал тем людям, которые выписав колонки чисел, сразу догадались, что два формата чисел отличаются сдвигом и отбрасыванием двойки. Я к этому сдвигу шел долгие часы, а 22 вообще долгое время считал признаком начала списка. Всё же, совместно с sannysanoff мы разобрали этот формат, я написал простенький енкодер машин. Еще ранее был написан интеллектуальный посылатель тривиальных машин. Он проработал совсем немного - до момента падения сервера. После поднятия сервера организаторы отключили нужные для работы ссылки на список всех машин, но оставили рабочей скрытую в недрах ссылку на список всех машин с принадлежностью к командам. Переписать скрипт, чтобы он использовал эту ссылку - дело 3-х минут. Как я понимаю, к моменту, когда мой бот снова начал работать, остальные участники еще не успели модифицировать собственные скрипты - скорость работы сервера была великолепна!

Также где-то в ночи появился переборный решатель от sannysanoff и dshoot. К нему так же был написан скрипт на Python, который запускал программу на Java для нахождения решений и отсылал результаты на сервер. Так решались небольшие нетривиальные машины. В это же время стало очевидно, что мы многое теряем, н придумывая свои машины. Этим занимались SAS и brox. В это же время действовало ограничение на 100 символов на машину. Поэтому почти все наши машинки - небольшие и поддаются перебором. К сожалению, мы пропустили момент, когда ограничение на 100 символов было снято.

Утром в понедельник вовсю работали скрипты, мы постили шаблонные машинки, а sannysanoff обнаружил, что топливо у нас кодируется неправильно. Часов за 7 до окончания контеста. Однако проблему удалось решить, хотя это нам и не сильно помогло. Последние участники разбрелись за час до окончания.

Итог

30 место, 69 машинок, около 700 топлив. Великолепное задание, отвратные кодировки. Я успел покодить на Python, C и Java. Кстати, этот ICFPC-2010 - наглядное доказательство того, что скриптовые языки вроде Python - очень нужны в таких контестах. Без Python не было бы ботов, написанных в считанные минуты, без Python не было бы быстрого прототипирования.

Заключение

В голове у меня эти дни отпечатались размыто. Действительно, как сон Алисы о Стране Чудес. Я мог перепутать время, потому что не помню, когда заканчивался один день и начинался другой. Я ничего не упомянул о том, как brox пытался на С подобрать очень короткие макроэлементы а я писал ему алгоритм пермутаций, как я оптимизировал генераторы 1 с задержкой, как вместе с Rst7 мы пытались решить машины аналитически с помощью Matlab, как я пытался реализовать рекурсивный энкодер чисел и как у меня ничего не вышло.

Немного сумбурный отчёт от sannysanoff. Если чей-то ник или какие-то события я указал неправильно - поправляйте.
ICFPC 2010 - кулаками после боя (by brox)

Некоторые трюки при использовании GDB

Небольшое собрание трюков, которые могут помочь при отладке с использованием GDB. Не претендует на сенсационность, но должно быть полезно для тех, кто только начинает знакомиться с этим замечательным инструментом. Итак, начнём:

Печать содержимого STL контейнеров

Основные способы собраны здесь, но я бы хотел остановиться на наиоболее универсальном способе - gdb-stl-views(нужно добавить в ~/.gdbinit). Он будет работать не только в самых новых версиях, а и в уже устаревших (это является важным фактором для тех, кто не может обновиться). Примеры использования:

(gdb) plist some_list
List size = list_size
List type = std::list<element_type, std::allocator<element_type> >

Соответственно, для того, чтобы распечатать весь список нужно использовать:

(gdb) plist some_list element_type
elem[0]: $i = ...
...
elem[list_size - 1]: $i = ...
List size = list_size 

А теперь интересные моменты:

• Если внутри контейнера хранится умный указатель, то часто для упрощения вывода можно в качестве element_type указать просто указатель (зависит от того, какой умный указатель вы используете. Большая часть из них при reinterpret_cast к указателю даст осмысленный результат). Например, вместо

  plist some_list smart_ptr<elem_type>

  использовать

  plist some_list elem_type*

• Если вы активно используете пространства имён, element_type скорее всего будет доступен только с полным указанием пространств имён, например NS1::NS2::element_type. Интересной особенностью GDB является то, что он не воспринимает NS1::NS2::element_type* как тип. Обойти эту проблему можно заключив имя типа в одинарные кавычки: 'NS1::NS2::element_type'*
• GDB иногда игнорирует using namespace. Поэтому лучше просто полностью указывать имя типа со всеми пространствами имён
• Чем новее у вас версия GDB, тем лучше он работает с пространствами имён. Если есть возможность - поставьте GDB 7.0 и выше

Вывод строк

Если вы активно работаете с разными типами строк, с разным размером символов, то вам пригодится следующий совет. Чтобы вывести строку, которую не желает выводить print, можно использовать:

• Команду просмотра памяти x. Например,

  (gdb) x/16s some_char_ptr

  для вывода 16 первых символов в символьном виде
• Можно добавить вот такую функцию в .gdbinit:
  

  define wchar_print
          echo "
  
          set $i = 0
          while (1 == 1)
                  set $c = (char)(($arg0)[$i++])
                  if ($c == '\0')
                          loop_break
                  end
                  printf "%c", $c
          end
  
          echo "
  
  end

  Использовать так:

  (gdb) wchar_print some_char_ptr

  Однообразно выводит std::string, std::wstring, различные двухбайтные строки. Естественно, конвертация к ASCII строке приводит к потере информации, однако в большинстве случаев это не так важно

Step Out

Самый короткий совет. Step Out делается командой fin или finish. Это почему-то один из самых распространённых вопросов.


И the last but not the least: в последнее время я довольно редко пишу в этот блог. Одна из причин тому - для небольших спонтанных записей я веду микроблог. Вторая - банальная нехватка времени. Однако не спешите отписываться: в записной книжке скопилось множество интересных статей, советов и идей. Постараюсь возобновить более-менее равномерное наполнение этого блога.

P.S. Для вывода на экран Qt строк можно использовать вот такое:

define printqstring
    printf "(QString)0x%x (length=%i): \"",&$arg0,$arg0.d->size
    set $i=0
    while $i < $arg0.d->size
        set $c=$arg0.d->data[$i++]
        if $c < 32 || $c > 127
                printf "\\u0x%04x", $c
        else
                printf "%c", (char)$c
        end
    end
    printf "\"\n"
end

Краткий отчёт о PyCamp

Не далее как в прошлую субботу, 30 января 2010, в Киеве состоялась конференция PyCamp Kyiv, основной темой которой был язык Python и сопутствующие технологии. Мне повезло там побывать, и я получил огромное удовольствие от конференции.

Доклады

В основном, доклады были довольно интересными. Ниже представлены некоторые претензии/отзывы по докладам, а также оценка качества повествования/слайдов:

• Александр Шигин "Почему Python - тормоз и как заставить его меньше тормозить" - неплохой доклад о том, какие конструкции в Python тормозят сильнее, чем другие. Для многих информация из доклада может показаться очевидной, но для меня она оказалась довольно полезной - позволила кое-как классифицировать разрознённые знания по этой теме. Качество повествования-3+, качество слайдов-5.
• Юрий Юревич "Рецепты декораторов" - очень короткий и довольно малоинформативный доклад о том, что такое декораторы в Python. Несмотря на хорошие слайды(на 5) и доклад(на 4+)
• Дмитрий Кожевин "Программирование на нервах" - отличный развлекательный доклад на тему управления проектами. Он небольшой и веселый, поэтому смотреть в видеозаписи обязательно. Качество доклада - 5, качество слайдов - 3.
• Михаил Кашкин "Работа с хранилищем данных в Google App Engine, отличия от реляционной модели" - доклад сочетает в себе общий обзор Datastore и описание некоторых особенностей. Доклад, в принципе, неплохой, но неполный. После него осталось очень много вопросов. Качество слайдов - 5, качество повествования - 4.
• Александр Соловьев "Redis: Дикий Запад баз данных" - хороший доклад про сверх-быструю key-value db. Удачно выбранная тема в данном случае на 80% определила успех доклада. Качество повествования - 5, качество слайдов - 5
• Андрей Светлов "Безопасная разработка ПО. Результат длинного пути и множества набитых шишек" - доклад о том, как важно использовать тесты, системы автоматической сборки и прочие вспомогательные тулзы. Довольно длинно, в основном по местам давно обглоданным. К тому же для многих тема "Тестировать или не тестировать" уже далеко не так остра, как была пару лет назад. Качество повествования - 4, качество слайдов - 4.
• Владимир Пузанов, Владимир Кириллов "Расширение и встраивание Python" - обзорный доклад об интерпретаторах Python, методах расширения стандартной функциональности и связывание с другими ЯП. Было весьма интересно, а продемонстрированный в конце хак нахожу очень приятным и довольно юзабельным. Качество повествования - 4+, качество слайдов - 3.
• Андрей Мишковский "Использование Python в ГИС" - неплохой обзорный доклад о средствах и библиотеках для создания ГИС на Python. Хотя я бы с большим удовольствием послушал о том, как создаются ГИС, а не с помощью чего(эту информацию можно получить и в Google). Качество повествования - 5, качество слайдов - 5.
• Сергей Кириллов "WebSockets в Twisted" - неплохой вводный доклад на тему "Что такое WebSockets?". Тема не очень сложная и была полностью раскрыта. Качество повествования - 5, качество слайдов - 5.
• Александр Бельченко "Интернационализация и локализация Python-приложений с использованием gettext" - подробный доклад об использовании gettext для локализации GUI приложений на Python. Большую часть информации из доклада можно получить при чтении документации, но докладчик также обозначил множество интересных и полезных моментов. Качество повествования - 4+, качество слайдов - 5.
• Иван Моргун "Работа с платежными системами в Django (PayPal, WebMoney)" - излишне подробный доклад, практически пересказ документации. Доклад можно было существенно порезать и он от этого стал бы более привлекательным. Качество повествования - 3+, качество слайдов - 3+.
• Дмитрий Жемеров "PyCharm – новая python IDE от JetBrains" - весьма любопытная презентация новой коммерческой IDE для Python. Выглядит весьма многообещающе, но то, что оно написано на Java, а также будет в будущем стоить $100, слегка портит впечатление. Качество повествования - 5, качество слайдов :) - 5

Организация

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

Заключение

Жду видео. Побольше бы таких конференций, хороших и разных!