Monday, March 23, 2009

Sapka contest

Не так давно закончился контест Sapka, который проходил с 13-го по 20-е марта 2009 года. Я принимал в этом контесте участие и не могу не поделиться впечатлениями, ведь их было очень-очень-очень много.

Введение

Sapka - контест, больше похожий на ICFPC, чем на контесты, проводимые ACM. А именно - задание здесь одно, марафонного типа, которое может решить практически любой хороший программист, но только в ситуации, когда у него в распоряжении будет неограниченное количество времени. К тому же задания как в ICFPC, так и в Sapka обычно намного интересней, подаются в игровой форме и больше требуют не знания алгоритмов, а умения напрягать мозг, концентрировать усилия и бороться. Для меня контест Sapka стал первым контестом подобного типа.

Команда

Sapka и ICFPC - командные соревнования. Естественно, участвовать можно и одному, но для одного человека объем работы очень велик, да и вместе веселее. Поэтому очень важным является выбор команды, настройка средств коммуникации, распределение ролей и т.д.
Я до самого конца не был уверен, буду ли я участвовать в Sapka, поэтому команду я нашел лишь за день до соревнований, да и за день мы никак не готовились к участию. Как ни странно, но ничего страшного из-за этого не случилось, были и покрупней просчёты :) Итак, команда под названием "a" изначально состояла из трёх человек - Вашего покорного слуги, xa4a и A2K. Но у последнего участника под конец соревнования были завалы с учебой, поэтому написанием самого решения занимались всего два человека.

Начало соревнования

Оригинальное задание можно прочитать на сайте Sapka. Фан начинается уже здесь. Если кратко - то нам даётся некий сервер некой игры, в которую надо стучаться по телнету. Нужно написать клиента для этой игры. Всё! Никакого точного ТЗ, только упоминание о том, что сначала сервер нужно сконфигурировать. И вот с таким багажом знаний все участники и вступают в игру.
Лично для себя я всё время участия могу поделить на 3 этапа:

Этап 1. Хак сервера :)

То, что сервер написан на Java, и то, что защита там игрушечная, впоследствии позволило многим командам получить все нужные для конфигурации данные в течение первых 1-2х часов соревнования. Это также вызвало бурные дискуссии и недовольство тех, кто не смог сервер хакнуть. В гугл-группе даже жаловались, что из-за того, что в команде не было ни одного джависта, у них не получилось похачить сервер и поэтому они не смогли "заняться собственно программированием"(с). Для тех, кто все еще считает, что для взлома сервера обязательно нужны знания Java - следующий абзац.
Обладая минимальными знаниями Java и обладая к Java большой нелюбовью, я пересилил себя и приступил к "взлому" сервера. Вся процедура взлома заключалась вот в чём: разархивировать jar; увидеть, что там есть какой-то loader; натравить на него jad (найден в google по словам Java Decompiler); открыть Eclipse; запихать туда расшифрованный код; пройтись по коду и найти место, где происходит дешифрация; добавить запись в файл прямо там(код записи в файл был также найден в google ;));скомпилировать и использовать получившийся код для дешифрации файлов; после этого натравливать jad на дешифрованные файлы. Чтобы долго не лазить по обфусцированному коду, я взял и банально расшифровал самые большие файлы, которые были в архиве. И тут же налетел на нужные файлы - на описания логики игр. Чуть погодя(почему погодя - смотрите ниже) был написан и генератор конфигурационных токенов(простым копированием существующего кода). Вы всё еще считаете, что для взлома сервера нужно было знание Java? ;)
На самом деле, я занимался исследованием сервера намного дольше, чем это могло показаться. Во-первых, я вначале пытался достать конфигурационные токены прямо из памяти, но успеха не добился. Во-вторых, команда активно ковыряла квестовую часть Сапки, и я также принимал в этом участие.

Этап 2. Квест

Все конфигурационные токены можно было достать, пройдя текстовый квест, общаясь по telnet с сервером. Это было очень увлекательно, поэтому даже когда я уже достаточно продвинулся в процессе взлома, мы всё равно продолжали решать задачки. Так были найдены практически все токены, кроме DNA (сгенерировать токен оказалось намного проще, чем решить эту задачу). Также были подсмотрены в коде сервера секретные пароли, так что токены, которые они дают, также были получены путём хака.
В общем, описать квестовую часть практически невозможно - это было незабываемо! :) Внутри был Брейнфак, Forth-подобный язык, "шашки"(за них отдельное спасибо, я был просто поражен, когда обыграл его) + несколько задачек на преобразование текста. Я постарался не выдавать никаких секретов в описании, поэтому если вы не видели квеста - it's worth to try it out! Даже несмотря на то, что игра завершена, удовольствие вам гарантировано.

Этап 3. Программирование бота

После прохождения квеста стало ясно, что нам нужно написать клиент к bomberman-like игре. В качестве основного инструмента был выбран язык Python. Краткое описание процесса:
xa4a - написание парсера для сообщений от сервера
xa4a - создание визуализатора (на pygame)
tilarids(/me) - улучшение визуализатора
xa4a - создание keyboard controller
xa4a - рефакторинг, фикс багов, random AI
tilarids(/me) - добавлено избегание опасных мест
tilarids(/me) - добавление уничтожителя стен

Здесь небольшая врезка - кончился lightning раунд. На lightning раунд был отправлен бот, который не ставил бомб, а только убегал от опасностей. Причина - за убийство себя давали -1000 очков, а бот был страшен в своей наглости и часто себя убивал.
Дальнейшая разработка заключалась практически в улучшении, рефакторингом и пофиксах существующих алгоритмов.
xa4a - большой рефакторинг, добавлен нормальный механизм переключения состояний
tilarids(/me) - добавлен учёт времени взрыва бомб, простейшее начисление очков(в соответствии с идеей A2K), пофикс багов
xa4a - добавление охоты за бонусами, пофикс багов, рефакторинг бомб
tilarids(/me) - добавление охоты за противником
xa4a - завершение рефакторинга бомб, добавление учета подрыва бомбами друг друга, пофикс багов
tilarids(/me) - пофикс багов, пофикс учета коллапса мира, сабмит

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

Репозиторий с исходниками находится в публичном доступе. Также есть просмотрщик риплеев.

Благодарности

Хотелось бы выразить огромнейшую благодарность организаторам. Sapka - это было потрясающе! Такого количества фана я не получал уже очень давно. Спасибо вам за то, что вы сделали!
Также хотелось поблагодарить команду - мне показалось, что работали мы достаточно слаженно, и я очень рад, что мне довелось участвовать в Sapka в команде именно с таким составом.

Организаторам

  • Всё же сервер надо защищать лучше. Чтобы взлом сервера был отдельной трудной задачей, а не заменял прохождение квеста. Например, можно было бы некоторые задания составить так, чтобы понадобилось их решать программно в момент запуска клиента
  • Побольше бы заданий наподобие fifth. Задачки на преобразование текста были занятные, но по количеству фана намного менее содержательные
  • Я буду очень рад поучаствовать в Sapka 2010 ;)

Себе на заметку

  • Если желаешь выиграть, нужно пользоваться даже относительно нечестными методами. Если бы мы не тратили время на квест, когда уже были почти все токены, на лайтнинг можно было бы успеть отправить уже активного бота
  • Количество участников в подобных соревнованиях - не главное. Но хорошо, если есть участники, которые могут потратить время на поиск и исправление багов
  • Возможно, стоило попробовать переписать всё вообще без состояний, чтобы получить простого, как пробка, но зато бессмертного/безбажного бота. Но после драки кулаками не машут :)
  • Pygame - отличная платформа для визуализации чего-либо

Sunday, March 22, 2009

Настройка удобного переключения раскладки клавиатуры для трёх и более языков

Многие пользователи ПК пользуются всего двумя раскладками клавиатуры - для родного и для английского языка. Если Вы привыкли к использованию двух раскладок, то переход на использование трёх или более раскладок может быть очень болезненным: Вы будете случайно попадать не на ту раскладку, писать белиберду и страшно ругаться. Для того, чтобы облегчить себе жизнь с тремя и более раскладками(у меня английская, русская и украинская), я настроил такую схему переключения раскладок: левый Shift + левый Ctrl переключает между первой и второй раскладкой, а правый Shift + правый Ctrl переключает циклически все раскладки. Так как обычно я переключал раскладку левой рукой, то привычная комбинация введением новых раскладок нарушена не была, при этом сохранилась возможность перейти на любую добавленную раскладку.
Основным источником информации для меня стал вот этот сайт. Ниже руководство для нетерпеливых :)
Итак, первым делом скажу, что я не захотел полностью следовать советам с указанного выше сайта, так как предложенный там способ задания конфигурационных файлов предполагал редактирование xorg.conf, а также добавление собственных конфигурационных файлов в папки настроек Xorg. Таким образом, я пошел по пути наименьшего сопротивления и моё решение - "fast and dirty".
В данном руководстве я предполагаю, что переключение раскладок по Shift + Ctrl уже настроено, все раскладки уже добавлены. Начнём с того, что получим текущую настройки XKB:

xkbcomp :0
, где :0 - id вашего X Display (скорее всего он у вас :0). Эта команда создаст файлик server-N.xkb , где N - указанный Вами id. Откройте этот файлик и найдите там описание символов ISO_Next_Group, ISO_Prev_Group, ISO_First_Group и ISO_Last_Group. У меня описания выглядят примерно так:
    interpret ISO_Next_Group+AnyOfOrNone(all) {
virtualModifier= AltGr;
useModMapMods=level1;
action= LockGroup(group=+1);
};
interpret ISO_Prev_Group+AnyOfOrNone(all) {
virtualModifier= AltGr;
useModMapMods=level1;
action= LockGroup(group=-1);
};
interpret ISO_First_Group+AnyOfOrNone(all) {
action= LockGroup(group=1);
};
interpret ISO_Last_Group+AnyOfOrNone(all) {
action= LockGroup(group=2);
};
ISO_Next_Group, ISO_Prev_Group, ISO_First_Group и ISO_Last_Group - это специальные символы, которые как раз и отвечают за переключение раскладок. В варианте указанном выше ISO_Next_Group переключает на следующую раскладку, ISO_Prev_Group - на предыдущую, ISO_First_Group - на первую, а ISO_Last_Group - на вторую. Осталось переназначить клавиши, чтобы они указывали на другие символы. Дифф для трёх раскладок (для четырёх и более - добавятся новые группы):
     key  {         [          Return ] };
- key { [ Control_L, ISO_Prev_Group ] };
+ key {
+ symbols[Group1]= [ Control_L, ISO_Last_Group ],
+ symbols[Group2]= [ Control_L, ISO_First_Group ],
+ symbols[Group3]= [ Control_L, ISO_First_Group ] };
key {
type= "ALPHABETIC",
symbols[Group1]= [ a, A ],
@@ -1262,7 +1265,9 @@ xkb_symbols "pc+us+ru(winkeys):2+ua(wink
};
key {
type= "PC_CONTROL_LEVEL2",
- symbols[Group1]= [ Shift_L, ISO_Prev_Group ]
+ symbols[Group1]= [ Shift_L, ISO_Last_Group ],
+ symbols[Group2]= [ Shift_L, ISO_First_Group ],
+ symbols[Group3]= [ Shift_L, ISO_First_Group ]
};
Т.е, заменим для комбинации клавиши LFSH + LCTL символ ISO_Prev_Group на ISO_First_Group и ISO_Last_Group в зависимости от раскладки.
После того, как Вы отредактировали файл, осталось залить настройки. Делается это так:
xkbcomp file.xkb :0
, где file.xkb - ваш сохранённый файл, а :0 - display id.
Хочу отметить, что при перезагрузке иксов все ваши настройки сбросятся. Т.е., для того, чтобы настройки загружались при старте, их надо добавить в автозагрузку. Минус такого подхода в том, что если обновить X Server, то настройки могут стать несовместимыми и иксы могут зависать. Поэтому я просто добавил шорткат для применения настроек и запускаю его тогда, когда мне нужно.
Еще один важный момент: xkbcomp перезаписывает все настройки. Т.о., если Вы переназначите какие-нибудь клавиши через xmodmap, то Вам нужно будет заново создавать файл настроек, иначе при применении настроек сделанные через xmodmap переназначения пропадут. Удачи с настройкой!

Monday, March 2, 2009

Reia - скриптовый язык для виртуальной машины Erlang`а

Лично я считаю Erlang одним из самых простых яызков программирования, а среди знакомых мне функциональных языков - самым простым. К тому же на Erlang благодаря его направленности на создание конкурентных приложений написано уже множество проектов, таких как Yaws, CouchDB, ejabberd, которые являются для него наилучшей рекламой.
Таким образом, Erlang - функциональный язык с простым и понятным синтаксисом, который нашёл свою нишу, и если вы интересуетесь созданием масштабируемых конкурентных систем - вам стоит выучить его. Однако из-за того, что Erlang - функциональный, его синтаксис и стиль понятен не всем - он слишком отличается от императивных языков(таких как С и подобные) и даже от Ruby/Python, которые включают в себя частицы функционального подхода.
Если Вы столкнулись с такой проблемой - обратите внимание на Reia - скриптовый Ruby/Python like язык для виртуальной машины BEAM(эта виртуальная машина используется также и в Erlang). Язык Reia совместим с Erlang и может использоваться для создания конкурентых приложений, однако используя при этом скриптовый синтаксис. Вот простейший пример:

module Foo
def bar
receive
when msg
["Received ",msg].join().puts()
bar()
pid = Process.spawn(fun {Foo.bar()})
pid ! "Hello"
pid ! "World"
Результат:
Received Hello
Received World
В язык заложено очень много возможностей(как по мне - слишком много :) ): отсылка сообщений процессам и объектам, встроенные регулярные выражения, pattern matching, асинхронные вызовы функции, лямбда функции, а также многое-многое другое. Многое из этого не реализовано(например, циклы), но часть функциональности уже существует и работает, как можно увидеть из примера.

Выводы

  1. Reia - многообещающий ЯП, которому, однако, не хватает разработчиков. Возможно, если реализации будет уделяться больше времени, то этот ЯП станет мостиком, по которому толпы приверженцев императивного подхода ринутся в страну Erlang
  2. Как по мне, синтаксис Reia перегружен. Этот вывод только подкрепляет моё убеждение, что Erlang - отлично спроектирован и очень элегантен