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

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

Осторожно, 4 мегабайта!

  Данный пост будет полезен разработчикам, которые только встали на радужный путь геймдева. В нашем недавнем посте уже было рассказано о первоначальных шагах нашей dream team в сфере игройстроя. Как и обещали, работаем в этом направлении дальше и решили попробовать себя в другом жанре игр. Далее будут кратко освещены некоторые моменты создания и публикации игры на двух платформах iOS и android.

На этот раз нововведений гораздо меньше, чем в первой части. Все-таки С++14 считается незначительным релизом, нацеленным скорее на устранение недочетов С++11, чем привнесение новых возможностей.

Краткий перечень:

• Освобождение памяти определенного размера
• Одинарная кавычка, как цифровой разделитель
• Аттрибут [[deprecated]]
• Пользовательские литералы для std::complex
• Filesystem API
• Преобразование сетевого порядка байт

Обзор новых возможностей С++14: Часть 1
Текущий черновик стандарта

Всем доброго пятничного вечера!

Сегодня я хочу рассказать о некоторых коварных особенностях статических переменных при неправильной линковке исполняемых модулей. Я покажу проблему из моей реальной практики, которая может возникнуть у каждого.
Разжевываю все довольно детально, поэтому у «бывалых» и красноглазиков может возникнуть ощущение, что я «колупаюсь в песочнице», но это статья не только для них.

Понадобилось мне прикрутить Lua к проекту на C++. Писать обертки в ручную — лень (слишком много писать), готовые не подходили по тем или иным причинам. Решил написать свою. А потому задался вопросом, как максимально упростить интерфейс? От одной только мысли об этом в голову лезли жутчайшие конструкции из шаблонов. Так оно в последствии и оказалось, но гораздо проще, чем представлялось.

В C++11 появились шаблоны с переменным числом аргументов, это позволяет писать шаблонные функции/классы так, как в C++03 было невозможно вовсе. Такие шаблоны сильно упрощают задачу.

Первым делом понадобилось написать обертку над простейшими действиями с интерпретатором (можно было бы обойтись простыми вызовами к C API Lua, но держать в памяти кучу индексов различных значений в стеке мне не хочется. Поэтому я обернул их в несколько функций, которые помимо того, что избавляют от необходимости передавать в каждую функцию указатель на состояние интерпретатора, практически не требуют индексов, так как они имеют значения по умолчанию.

В итоге хотелось увидеть интерфейс близкий к следующему:

lua.export_function(some_function);

Все началось с того, что на глаза случайно попался конкурс от NextCastle Party, где предлагалось в строго ограниченные сроки (тема была объявлена за неделю) создать игру.

Условием была обязательная возможность играть с живыми игроками за одним компьютером (не важно, pvp или кооператив, синхрон или асинхрон). А так же были ограничения по платформам — необходимо, чтобы игра шла в браузере.

Собственно, узнав про конкурс — решились поучаствовать. Смущало, правда, что в конкурсе можно использовать любые наработки… Ведь вдруг кто-то в этот момент делает именно такую игру и притащит на конкурс почти готовый проект? А у нас подходящих наработок — ну вообще нет. Ну да ладно, волков бояться — в лес не ходить. В конце концов, интересный опыт.

Графическое движение: тесселяции своими руками.

Иногда, когда я рисую, мне кажется, будто я медиум, находящийся во власти существ, порождённых моим же воображением. Рыбы становятся птицами. День ночью. Из хаоса рождается жизнь, она замирает в мёртвых городах, трансформируется в шахматную партию и рассыпается в пыль. Мозаика оживает и превращается в ящериц, они движутся, живут и вновь уходят в орнамент.
Мауриц Корнелис Эшер

Автор эпиграфа — нидерландский художник-график, известный концептуальными литографиями, гравюрами на дереве и металле, в которых мастерски исследует пластические аспекты понятий бесконечности и симметрии.
Как ни абсурдно, несколько проведённых от руки линий могут выглядеть, как объёмная фигура. Такова особенность психологического восприятия человеком сложных трёхмерных объектов. Эшер добивался простыми средствами поразительного эффекта. А если бы в его распоряжении были все средства современной компьютерной графики? Как говорил он сам: «Если бы вы только знали, какие видения посещают меня в ночной тьме… Иногда моя неспособность сделать их зримыми буквально сводит меня с ума».
Имея последние версии «Корела», «Пэйнта» или «Фотошопа», можно пойти другим путём. И предстанут перед нами иные метаморфозы…

Добрый день, Хабражитель!

Уверен с форматом nine-patch уже все давным-давно знакомы, вероятно даже не раз пользовались им в своих Android-проектах (а может даже и где-то ещё). Также о нём чуть менее года назад skkap писал небольшую статью о том, что это за формат, и «с чем его едят». Также он описал инструмент, предлагаемый для быстрого редактирования этих самых файлов.

Собственно, прошёл уже почти год с того момента и я, опять наткнувшись на ту статью и вспомнив жалобы знакомых на неудобство этого самого «инструмента», решил посмотреть нет ли каких других вариантов и, к моему большому удивлению, я таковых не нашёл. Вероятно потому, что формат сам из себя ничего сложного и специфичного не представляет (при желании nine-patch файлы можно редактировать почти в любом графическом редакторе поддерживающем png) и тем более уже есть готовый инструмент (пусть и не самый удобный).

Тут я и решил лично взяться за дело…

Демо по мотивам одного видео:
Пример 1 — Вы большой гриб, а повсюду таблетки (как на кислотной вечеринке)
Пример 2 — Человек, управляет грузовиком
Пример 3 — Кидание бракованных кирпичей в колодец
Пример 4 — Битва роботов (PvP)

Дублирующий сервер: 1, 2, 3, 4

Привет.

Недавно я создал мобильную игру для Android, в которой потенциально мог бы быть мультиплеер, чего и затребовали пользователи.
Мультиплеер не предусматривался, так как не соблюдал разделения модели и представления.
В этой статье я рассмотрю простую реализацию сетевого режима игры и расскажу об ошибках, допущенных на этапе продумывания архитектуры игры.
Воодушевившись статьей goblin wars II структура игры была разделена на независимые блоки, что в конечном итоге позволило пользователям играть по сети.

В предыдущей статье мы заглянули внутрь процессора, пусть и гипотетического. Мы выяснили, что для корректного выполнения параллельного кода процессору необходимо подсказывать, до каких пределов ему разрешено проводить свои внутренние оптимизации чтения/записи. Эти подсказки – барьеры памяти. Барьеры памяти позволяют в той или иной мере упорядочить обращения к памяти (точнее, кэшу, — процессор взаимодействует с внешним миром только через кэш). “Тяжесть” такого упорядочения может быть разной, — каждая архитектура может предоставлять целый набор барьеров “на выбор”. Используя те или иные барьеры памяти, мы можем построить разные модели памяти — набор гарантий, которые будут выполняться для наших программ.

В этой статье мы рассмотрим модель памяти C++11.

Здравствуйте! Сегодня мы будем писать платформер, используя C++, Box2D и SFML, а также редактор 2D карт для игр Tiled Map Editor.



Вот результат (карта создавалась 5 минут + во время сьемки игра тормозила + экран не так растянут — дефект Bandicam):



Исходники и exe — внизу статьи.

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

Хабр, я понимаю, что сегодня еще далеко не пятница — но увиденное при себе держать нет сил.

Танцующий Бендер Родригес на чистом CSS3

Создан или вручную, или при помощи Sencha Animator.

Для всех, кому понравится: вот более сложные примеры того, что может быть сделано при помощи CSS3 (и рассказ о них с концеренции CSSConf.eu).

В этой статье я даю краткий обзор того, как применять библиотеку lock-free структур данных libcds. В реализацию я углубляться здесь не буду, — это просто взгляд извне, взгляд со стороны пользователя библиотеки.

Библиотека libcds имеет свою точку зрения на многие известные структуры данных. Отчасти это объясняется целевой областью – lock-free структуры данных довольно минималистичны по набору предоставляемых методов, — отчасти желанием выйти за ограничения и решения стандартной библиотеки STL. Что из этого получилось – решать пользователям libcds.

Кому интересно – добро пожаловать под кат

Если не знаешь, надо не бояться, а узнавать.
Айн Рэнд “Атлант расправил плечи”



Добрый день, меня зовут Игорь Томич и я лектор курсов iOS-разработки и сооснователь онлайн курсов Master Up. Это мой первый пост в наш корпоративный блог, в котором я решил поделиться советами для начинающих iOS-разработчиков. Свое первое приложение для iOS я начал писать в начале 2009 года, а в мае 2012 году провел первый курс обучения по рарзработке под эту же платформу и к этому времени у меня скопилось достаточно “часто повторяемых ошибок” и путей их решения.

Задание

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

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

И ладно, атата с ней, с этой ататой. Но отличного контента в виде картинок там осталось немало, один тред с обоями чего стоит! Поэтому неудивительно, что следующее задание из штаба выглядело следующим образом:
«Срочно сохранить для потомков все изображения из потока #949 #291. ps. Извращенно.»

Ну, что же, есть задание — нужно работать. Вообще-то по извращенным структурам у нас уже есть некий кофейный чемпион, но и на Go тоже можно что-нибудь сообразить! После 9 часов работы в Paint у меня родился следующий план атаки:



Степень изврата поражает, начальство будет довольно! Рассмотрим что тут и как:

«Генератор» будет загружать с ататы хтмл код страниц, выдергивать урлы картинок и передавать их «Балансировщику», который раскидывает эти урлы некоторому количеству «Рабочих» (каждый из которых имеет свою небольшую очередь заданий) следя за тем, чтобы все рабочие были равномерно нагружены. Ну а «рабочие» загружают картинки и радуют глаз умиленного балансировщика. Выглядит избыточно, но зато про войну! Поехали:

Про язык Go от команды Google слышали, наверное, все. А вот пробовали далеко не все, и очень зря — общение с сусликами Go это море удовольствия, в чем я недавно убедился на собственном опыте.
Начинать знакомство с новым языком забавнее всего на жизненном примере, поэтому я, не долго думая, взял первую попавшуюся задачу “из жизни, самой первостепенной важности”:

Есть в интернете сайт http://vpustotu.ru на котором любой желающий может анонимно высказаться о наболевшем. Все высказывания (в дальнейшем буду называть их “цитатами”) сначала попадают в модерацию (аналог “бездны” башорга), где посетители могут оценить полет мысли и проголосовать за цитату в стиле “Ого!” или “Ерунда!”. На странице модерации (http://vpustotu.ru/moderation/) нам показывают случайную цитату, ссылки голосования и ссылку “Еще”, которая ведет на эту же страницу. Пощелкайте, это все очень просто.

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

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

Таким образом нужна программа, которая:

• Должна последовательно обновлять и парсить (разбирать) страницу, записывая цитату.
• Должна уметь отбрасывать дубликаты.

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

• Должна останавливаться не только по команде, но и по достижению определенного числа “повторов”, например 500!
• Так как это, скорее всего, займет некоторое время: необходимо уметь продолжить “с места на котором остановились” после закрытия.
• Ну и раз уж все-таки это надолго – пусть делает свое грязное дело в несколько потоков. Хорошо-бы в целых 4 потока (или даже 5!).
• И отчитывается об успехах в консоль каждые, скажем, 10 секунд.
• А все эти параметры пускай принимает из аргументов командной строки!

Ну, вроде все понятно. Пусть программа ведет два файла – с цитатами и с некими хешами этих цитат, чтобы не повторяться, и перечитывает файл в начале каждого запуска. Ну а дальше в цикле разбирает страницу, выдергивая все новые и новые откровения, пока не получит ctrl-c по лбу или же не встретит определенное количество повторов. Задача ясна, план есть – поехали!

Библиотека Qt позволяет делать действительно кроссплатформенные приложения. Единожды написанный код можно откомпилировать под многие операционные системы. Но проблема именно в слове «компилировать», т.к. подразумевается, что необходимо перезагрузиться под целевую систему, иметь в ней настроенную среду разработки, установленный и настроенный зоопарк библиотек. Спасает кросс-компиляция — компиляция, производящая исполняемый код для платформы, отличной от той, на которой исполняется.

На Хабре неоднократно появлялись статьи с описанием приложения из известного фильма «The Matrix». Как известно, все они принадлежат так называемому классу View Matrix, позволяют визуализировать состояние мира в котором проживают главные герои фильма. Но в отличие от предыдущих версий данных программ для ЭВМ, я хочу рассказать о визуализаторе матрицы первой версии (о которой в фильме упоминал герой с именем Морфеус в первой части трилогии).



Дорогие друзья, эта статья посвящена всем кто помнит что такое Dos, видео режим 80x25 и прочие «замечательные мелочи» олд скульного разработчика приложений. А так же кому интересно с этим познакомиться.