Рад сообщить, что вышел перевод отличнейшего учебника Дасгупты, Пападимитриу, Вазирани «Алгоритмы», над которым я работал последние несколько лет. В книге многие алгоритмы объяснены гораздо короче и проще, чем в других учебниках: с одной стороны, без излишнего формализа, с другой — без потери математической строгости. Откройте книгу на каком-нибудь известном вам алгоритме и убедитесь в этом. =)

В общем, угощайтесь: печатный вариант перевода, электронный вариант перевода (PDF), печатный вариант оригинала, электронный вариант оригинала (PDF).

Доброго дня, на выходных от скуки и отсутствия работы решил себя развлечь написанием небольшого приложения, которое сгодится в качестве учебного метариала для изучения возможностей двух замечательных библиотек — ractive.js и sails.js

Постановка задачи

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

Выглядит примерно так

Про технологию WebRTC в последнее время пишут много. Она позволяет обеспечить взаимодействие двух клиентов без специализированного сервера между ними, но нужда в сервере отпадает только после установки соединения. А на этапе установки самого соединения некоторые серверные ресурсы все еще нужны. Можно ли избавиться от потребности в сервере? Небольшой эксперимент в этом направлении под катом.

Хей народ, пристегните ремни и держитесь покрепче, ибо наступил действительно волнительный момент: вам предстоит разобраться в тонкостях чрезвычайно интересных временных функций CSS!

Окей, ваша кровь, конечно, вряд ли закипела от предмета данной статьи, но шутки в сторону: временные функции — своего рода скрытая жемчужина, когда дело касается CSS, и, вполне вероятно, вы удивитесь тому, сколько всего интересного с помощью них можно сделать.

Допустим, мы хотим сделать двухколоночную раскладку с помощью свойства table-cell. Левая колонка будет занимать всю доступную ширину, правая же может иметь два варианта в нашем случае:

• мы зададим этой колонке фиксированную ширину;
• она будет равняться минимальной ширине контента → minimum content width (MCW).

Данным постом мы открываем рубрику «Переводы» в нашем блоге. Почему мы решили открыть такую рубрику? Дело в том, что сотни специалистов, работающих в Mail.Ru Group, для решения стоящих перед ними задач ежедневно прочитывают множество интересных статей и постов на форумах. Некоторые из них кажутся нам интересными, и мы считаем своим долгом перевести их на русский и поделиться этими ценными знаниями с Хабражителями.

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

В предыдущей статье я рассказывал об уникальном, на мой взгляд, проекте Zillions of Games. Как я и обещал, я начинаю небольшой цикл учебных статей по описанию возможностей декларативного языка, предназначенного для разработки новых (и описания уже существующих) игр, в рамках этого проекта.

Для того чтобы не загромождать изложение излишними (на этом этапе) подробностями, я выбрал для реализации очень простую игру. Я играл в нее в детстве. Она называется «Волки и Козленок». Правила следующие: Волки (черные фигуры) — ходят на одну клетку по диагонали, только вперед. Козленок (белая фигура) — также ходит на одну клетку по диагонали, но в любую сторону. Задача белых — пройти на любую из четырех клеток своего цвета последней горизонтали. Задача черных — лишить белых возможности хода.

Поскольку на стандартной шахматной доске 8x8 черные побеждают элементарно, используем для игры доску 9x9 клеток. Эта игра очень простая (и нравится детям). При правильной игре, белые всегда побеждают.

К шахматам я неравнодушен с детства. Хотя я так и не научился играть действительно хорошо, сам процесс игры доставляет мне огромное удовольствие. Довольно давно я узнал, что помимо известных всем традиционных шахмат, существуют и другие их разновидности. Не помню на каком компьютере, на Спектруме или Векторе 06 Ц я впервые увидел Сянцы. Игра была полностью на китайском языке и постигать её правила приходилось «методом тыка». Позже, я узнал о существовании Сёги, Чатуранга и прочих ближайших родственников Шахмат. Публикации в Кванте подстегнули интерес к Сказочным шахматам. Меня заинтересовал вопрос, сколько вообще известно разновидностей шахмат? Выяснилось, что их невероятно много. Настолько много, что список, посвященный этому вопросу на Вике очень и очень далек от того, чтобы его можно было считать полным.

Уже гораздо позже, когда я стал профессиональным программистом, у меня появилась идея, разработать универсальное приложение, для контроля правил ходов в разнообразных шахматноподобных играх на квадратных и прямоугольных досках. Разумеется, у меня и в мыслях не было, что я смогу создать универсальный AI. Даже сама задача реализации универсальной шахматной доски, с настраиваемым контролем всевозможных правил и возможностью игры по сети выглядела неподъемной. Я коллекционировал правила шахматных игр, пытался обобщить их, но, с учетом того, что я занимался этим краткими урывками, между основной работой, процесс пробуксовывал и шел очень медленно. Так продолжалось до тех пор, пока в прошлую пятницу, я не обнаружил проект под названием Zillions of Games.

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

Питон изумителен.

Удивительно, но это довольно неоднозначное заявление. Что я имею ввиду под “Питоном”? Может, абстрактный интерфейс Питона? Или CPython, распространенная реализация Питона (не путать с похожим по названию Cython)? Или я имею ввиду что-то совсем иное? Может, я косвенно ссылаюсь на Jython, или IronPython, или PyPy. Или может я отвлекся так сильно, что говорю о RPython или RubyPython (которые очень сильно отличаются).

Не смотря на схожесть в названиях указанных выше технологий, некоторые из них имеют совсем другие задачи (или, как минимум, работают совершенно иными способами)

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

В этом посте я начну с нуля и пройдусь по разным реализациям Питона, а закончу подробным введением в PyPy, за которым, по моему мнению, будущее языка.

Все начинается с понимания того, чем на самом деле является “Питон”.

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

Быстрое изменение состояния посреди анимации

Обычно анимации используются для того, чтобы плавно менять свойства элементов со временем. Однако изменения могут также быть практически мгновенными. Для этого надо задать два ключевых кадра с очень маленьким интервалом, например в 0.001%:

@keyframes toggleOpacity {
  50% { opacity: 1; } /* Turn off */
  50.001% { opacity: 0.4; }

  /* Keep off state for a short period */

  52.999% { opacity: 0.4; } /* Turn back on */
  53% { opacity: 1; }
}

Вот как я использовал этот приём для имитации мигающей неоновой вывески с помощью прозрачности и свойства text-shadow:

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

Всем нам иногда хочется попробовать новую идею, запилить какой-нибудь сайтик про манулов, но чтоб обязательно на node.js, хайлоад реди, с мемкешем, монго, фейловером и с претензией на мировое господство. У меня для Вас хорошие новости: благодаря щедрости проклятых западных капиталистов всё это можно получить совершенно бесплатно.

[FF D8]

Вам когда-нибудь хотелось узнать как устроен jpg-файл? Сейчас разберемся! Прогревайте ваш любимый компилятор и hex-редактор, будем декодировать это:

Специально взял рисунок поменьше. Это знакомый, но сильно пережатый favicon Гугла:

Последующее описание упрощено, и приведенная информация не полная, но зато потом будет легко понять спецификацию.

Даже не зная, как происходит кодирование, мы уже можем кое-что извлечь из файла.

[FF D8] — маркер начала. Он всегда находится в начале всех jpg-файлов.

Следом идут байты [FF FE]. Это маркер, означающий начало секции с комментарием. Следующие 2 байта [00 04] — длина секции (включая эти 2 байта). Значит в следующих двух [3A 29] — сам комментарий. Это коды символов ":" и ")", т.е. обычного смайлика. Вы можете увидеть его в первой строке правой части hex-редактора.

Данная статья предназначена для разъяснения сути фундаментальных методов построения и оптимизации «искусственного интеллекта» для компьютерных игр (в основном антагонистических). На примере игры в зайца и волков будет рассмотрен алгоритм «Минимакс» и алгоритм его оптимизации «Альфа-бета отсечение». Помимо текстового описания, статья содержит иллюстрации, таблицы, исходники, и готовую кроссплатформенную игру с открытым кодом, в которой вы сможете посоревноваться с интеллектуальным агентом.

Все отлично знают, что из класса обменных сортировок самый быстрый метод – это так называемая быстрая сортировка. О ней пишут диссертации, её посвящено немало статей на Хабре, на её основе придумывают сложные гибридные алгоритмы. Но сегодня речь пойдёт не про quick sort, а про другой обменный способ – старую добрую пузырьковую сортировку и её улучшения, модификации, мутации и разновидности.

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

image: пузырьки

Вступление

Вообще, речь пойдёт не о классической гомоку, а о русской вариации «пять в ряд». У вас есть листок бумаги в клеточку. Правила игры такие же, как в крестиках-ноликах. Отличие лишь в том, что необходимо выстроить линию из 5 элементов.



За такой нехитрой игрой мы прослушали не одну лекцию. Меня всегда раздражало, что моя блестящая стратегия разбивается о собственную невнимательность. Ну ничего, думал я, вот напишу программу, которая не будет делать ошибок, я тогда всем им покажу! Раз плюнуть! Пару циклов, правда, надо повозиться с пользовательским интерфейсом, но за пару вечеров управлюсь. С момента окончания института прошло 10 лет, а программу я всё ещё не написал.

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

Часть вторая

Приветствую в серии статей о WebGL рендринге ландшафта, используемом в игре Trigger Rally!

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

В этой статье я расскажу об структуре данных вершин, а так же о морфинге.


От переводчика: в статье много косноязычия и технических неточностей. Помогите их исправить!

Эта статья является переводом цикла из четырёх статей «Linear algebra for game developers», написанных David Rosen и посвящённых линейной алгебре и её применению в разработке игр. С оригинальными статьями можно ознакомиться тут: часть 1, часть 2, часть 3 и часть 4. Я не стал публиковать переводы отдельными топиками, а объединил все статьи в одну. Думаю, что так будет удобнее воспринимать материал и работать с ним. Итак приступим.

От переводчика:
Я собрался изучить новый для меня паттерн Стратегия, но не нашёл толкового русского описания его реализации на javascript. Статья на wiki пугает своей сложностью, а наглядность примера оставляет желать лучшего. По этому и взялся за перевод этой статьи, одновременно разбираясь, что же из себя представляет данный паттерн.
Спойлеры и текст, выделенный серым, являются моими комментариями.

Далее мы разберём примеры того, как я использую СТРАТЕГИЮ в Javascript, и как он используется реальной библиотекой, для разбиения её на небольшие части.