Предыдущий пост вызвал множество споров в pythonua@c.j.r на тему сложности синтаксиса С++ и сложности синтаксиса лямбд в частности. Действительно, в С++ 0x лямбды - это не one-line expressions, а полноценные анонимные функции. Именно поэтому синтаксис и так сложен. Например, возьмём Python и его лямбды. Так как синтаксис Python изначально минималистичен, то и лямбды в нём выглядят аккуратно и понятно. Однако, с другой стороны такая минималистичность может сыграть и злую шутку. Вот пример - не так давно поднимался вопрос о замыканиях в Python. Речь в этой статье шла о таком небольшом сниппете:
l =[] for i inrange(2): for j inrange(2): l.append(lambda: i + j)
При такой реализации замыкания не происходит - в l мы получим абсолютно одинаковые функции. Основной вывод вышеприведенной статьи - правильная реализация замыканий в Python - это:
def lsum(n, m): returnlambda: n + m
l =[] for i inrange(2): for j inrange(2): l.append(lsum(i, j))
Но что мы видим в этом коде? Вместо удобного inline использования - отдельная функция, которая отвлекает внимание и всё портит. Теперь вернёмся к С++ и посмотрим как в игру вступает один из синтаксических наворотов - capture list:
С++ 0x - кодовое имя грядущего стандарта С++, который несет в себе огромное количество изменений. Если и до этого язык С++ был одним из самых нагруженных и сложных, то с приходом нового стандарта он может вообще быть погребен под собственной массой. Но случится ли это? Ответу на этот вопрос и посвящен данный пост.
Основная часть
На BoostCon было точно подмечено, что "С++ 0x" нужно читать как "C++ 0A","C++0B", etc, однако многое можно попробовать уже сейчас. Для этого я собрал gcc из cxx0x-lambdas-branch, который, по-моему, сейчас максимально близок к C++0x (бранч периодически мержится с основной веткой, но в этом бранче полностью отстутствуют Concepts). О том, как собирать - смотрите ссылки ниже. Итак, имеем:
$ bin/gcc --version gcc (GCC) 4.5.0 20090421 (experimental) Copyright (C) 2009 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
intmain() { std::vector<int> v ={1,2,3,4,5}; std::vector<std::pair<int,int>> v2; std::transform(v.begin(), v.end(), std::back_inserter(v2), [](int x){returnstd::pair<int,int>(x, x*x);}); for_each(v2.begin(),v2.end(),[](std::pair<int,int> x){std::cout<<"("<<x.first<<","<<x.second<<")";}); int s =0; for_each(v.begin(),v.end(),[&s](int x){s+=x;}); std::cout<<"\nResult:"<<s<<"\n"; // static_assert(false, "Dummy assertion!"); auto is_42 =[](int x){return x ==42;}; auto answer =42; if(is_42(answer)) { std::cout<<"Yes, it is!\n"; } decltype(answer +42) new_answer =43;//? std::cout<<"New Answer:"<<new_answer<<"\n"; }
Впечатляет? Присмотритесь внимательней, в этом примере: initializer lists(список инициализации для v), right angle brackets (две правые угловые скобки в определении v2), lambda(с захватом переменных и без), static_assert (закомментирован), auto (для простых случаев и для лямбда-выражений), decltype(для определения типов). Меня очень впечатлило. Несмотря на то, что в язык добавлены новые элементы, язык стал только выразительней, а никак не сложнее. Таким образом, С++ вбирает в себя всё новые и новые идеи. Несложно заметить, что С++ 0x - огромный шаг поближе к Haskell. Кто считает, что это чепуха - присмотритесь к Variadic Templates:
template<unsigned... Args>struct mysum; template<> struct mysum<>{ staticconstint value =0; };
template<unsigned x,unsigned... Args> struct mysum<x, Args...>{ staticconstint value = x + mysum<Args...>::value; };
Что такое tddspry? Это небольшой набор утилит для тестирования django-приложений с помощью nosetests. Если по какой-то причине Вы не можете воспользоваться Django Test-execution Framework или джанговские тесты просто Вас раздражают, то обязательно обратите внимание на этот небольшой проект. На данный момент в состав tddspry включены хэлперы для написания тестов, а также моки для БД и twill. В дальнейшем возможно включение поддержки Windmill, etc. Проект открыт для предложений. :) Пример использования:
class TestUI(TwillMock, DbMock): def setup(self): super(TestUI,self).setup() login_to_admin(username='admin', password='admin')
Возможно, многие из читателей уже слышали о таком сервисе, как ItQuest.ru. А если не слышали - обязательно обратите на него внимание. Ресурс идейно схож с StackOverflow - большая база вопросов и ответов на IT тематику. Так что если у Вас есть вопрос, ответ на который не знает даже Google, попробуйте задать его здесь. P.S. Сайт написан на Django. Еще один повод присмотреться.
Не так давно закончился контест 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 - отличная платформа для визуализации чего-либо
Posts
