Всем, привет! Наша команда сейчас проходит важный этап становления любого разработчика игр — первый запуск игры на Steam Greenlight. Пока я готовил материал для этой статьи, наша игра вошла в ТОП-100 проектов на Greenlight, набрала почти 2000 голосов «ЗА» и через 12 дней получила зелёный свет.

В этой статье хочу поделиться информацией, которую «нарыл» в процессе подготовки к Greenlight'у, а также попробовать проанализировать, какие гипотезы по продвижению сработали, а какие пути оказались тупиковыми. Надеемся, эта информация окажется полезной и кому-то попадёт в избранное.

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

pred1(X, Y), pred2(Y, Z), pred3(Z).


в традиционных языках представляется чем-то вроде следующей вложенной конструкции

for Y in pred1(X) {
  for Z in pred2(Y) {
    pred3(Z)
  }
}


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

Однако, мы отвлеклись.

Сегодня мы будет обсуждать технические аспекты и реализацию задач на Python и C/C++, которыми нас будет закидывать инженер из Google. Начнём с самых тривиальных проблем с последующим нарастанием сложности. Параллельно обратим внимание о чём стоит упомянуть во время интервью и где не попасть в ловушку.

Доброго времени суток! Недавно узнав о таком инструменте моделирования, как язык Modelica и его свободной реализации OpenModelica, был удивлен тому, что на Хабре по этому поводу всего одна статья. Поскольку тема несколько необычна, детали пришлось постигать на собственной шкуре некотором взятом из головы примере. В этой статье пойдет речь о том, как построить простую модель сражения (для примера), попутно разобравшись с некоторыми концепциями языка (основное).

Оглавление (на данный момент)

Часть 1. Описание, операции, применения.
Часть 2. Ценная информация в дереве и множественные операции с ней.
Часть 3. Декартово дерево по неявному ключу.
To be continued...

Декартово дерево (cartesian tree, treap) — красивая и легко реализующаяся структура данных, которая с минимальными усилиями позволит вам производить многие скоростные операции над массивами ваших данных. Что характерно, на Хабрахабре единственное его упоминание я нашел в обзорном посте многоуважаемого winger, но тогда продолжение тому циклу так и не последовало. Обидно, кстати.

Я постараюсь покрыть все, что мне известно по теме — несмотря на то, что известно мне сравнительно не так уж много, материала вполне хватит поста на два, а то и на три. Все алгоритмы иллюстрируются исходниками на C# (а так как я любитель функционального программирования, то где-нибудь в послесловии речь зайдет и о F# — но это читать не обязательно :). Итак, приступим.

Введение

В качестве введения рекомендую прочесть пост про двоичные деревья поиска того же winger, поскольку без понимания того, что такое дерево, дерево поиска, а так же без знания оценок сложности алгоритма многое из материала данной статьи останется для вас китайской грамотой. Обидно, правда?

Следующий пункт нашей обязательной программы — куча (heap). Думаю, также многим известная структура данных, однако краткий обзор я все же приведу.
Представьте себе двоичное дерево с какими-то данными (ключами) в вершинах. И для каждой вершины мы в обязательном порядке требуем следующее: ее ключ строго больше, чем ключи ее непосредственных сыновей. Вот небольшой пример корректной кучи:

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

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

Долго выбирал между «Алгоритмами», «Читальным залом» и «Я пиарюсь», в итоге остановился на Data Mining.

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

И вот, терзаясь муками выбора, я забил в поиск «IMDB for books» и… не нашел ничего пристойного. Весь интернет забит рекомендательными сервисами для книг, и все они выдают полную чушь. Вот, например, топ имхонета для раздела «Самая лучшая фантастика и фэнтези»:

1. Мастер и Маргарита. Михаил Булгаков, 1940 год
2. Цветы для Элджернона (рассказ). Дэниел Киз, 1959 год
3. Цветы для Элджернона. Дэниел Киз, 1966 год
4. Битва Королей. Джордж Мартин, 1998 год
5. Рыцарь Ордена: Клинки у трона. Сергей Садов, 2000 год
6. Голубятня в Орехове. Владислав Крапивин, 1983 год

Эээ… Это совсем не то, что я ожидал увидеть на первых местах в рейтинге фантастики. «Мы пойдём другим путём», — подумал я. Отказавшись от идеи найти нормальный читательский рейтинг, я просто пошёл в Вики, нашёл список лауреатов премий Хьюго и Небьюла и выбрал пару-тройку книг — как, собственно, я всегда раньше и делал.

«А не замутить ли мне свой рейтинг книг, взяв за основу престижные премии?» — внезапно подумал я. И замутил. Знакомьтесь: top-books.info

В данной статье я подробно опишу как установить и настроить SBCL и окружение для продуктивной разработки под Windows.

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

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

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

Если поискать, то на русском языке нет ничего толкового по разработке расширений для chrome, только лишь эта статья доступно описывает самые основы.

Данный пост будет более продвинутой версией.

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

Задача

Профессор Самоделкин решил изготовить объемную модель кубиков из спичек, используя спички для рёбер кубиков. Длина ребра каждого кубика равна одной спичке.
Для построения модели трех кубиков он использовал 28 спичек.
Какое наименьшее количество спичек нужно Самоделкину для построения модели из N кубиков?
Все числа в задаче не превышают 2·10⁹.

Технические условия

Входные данные
Одно число N – количество кубиков.
Выходные данные
Одно число – количество спичек.

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

_{«Однако среди переборных и некоторых других задач можно выделить класс задач, обладающих одним хорошим свойством: имея решения некоторых подзадач (например, для меньшего числа n), можно практически без перебора найти решение исходной задачи.» — Класс задач которые решаются динамическим программированием.}
И наша цель добиться решения, согласно описанию задач на динамическое программирование, в котором решение для текущих параметров строится на решении предыдущих.

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

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

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

Такие задачи решают методом динамического программирования, а под самим динамическим программированием понимают сведение задачи к подзадачам.

Сегодня я расскажу на абстрактном примере как правильно создать *.deb пакет для Ubuntu/Debian. Пакет мы будем делать бинарный. Пакеты, компилирующие бинарники из исходников здесь не рассматриваются: осилив изложенные ниже знания, в дальнейшем по готовым примерам можно понять суть и действовать по аналогии :)

В статье не будет никакой лишней возни «вручную»: формат пакета эволюционировал в достаточно простую, а главное — логичную структуру, и всё делается буквально на коленке, с применением пары специализированных утилит.

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

Для тех, кто не хочет вдаваться в мощную систему установки софта в Linux, рекомендую посетить сайт проги CheckInstall: она автоматически создаёт deb-пакет из команды «make install» ;) А мы вместе с любопытными —

Когда я прочитал эту и эту статьи, мне захотелось рассказать, как человек может внести свой маленький вклад в распространение своей любимой программы среди пользователей всеми любимой операционной системы. Полистав Убунтариум, я увидел, что статей на эту тему вроде бы не было, поэтому я решил смело приняться за дело.
(Части 2, 3 и 4)

Эта головоломка уже знакома Хабрахабру по этой публикации.

Суть головоломки в следующем (цитируя bor1s):

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

Пройти головоломку online можно по ссылке: http://freeweb.siol.net/danej/riverIQGame.swf.

Пролог обычно хорошо справляется с решением таких задач, в чем я и решил убедиться…

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

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

Вот тут наткнулся на, в общем-то, простую задачку состоящую в парсинге текстового файла, содержащего 5 миллионов float'ов (и подсчете их суммы). Файл генерируется следующим C#-кодом:

static void Main(string[] args)
{
  using (Stream stm = new FileStream(@"d:\numbers_large.txt", FileMode.Create))
  {
    TextWriter wr = new StreamWriter(stm);
    System.Random r = new System.Random();
    for (int i = 0; i < 5000000; i++)
    {
      double d=10000*r.NextDouble() * (r.NextDouble() > 0.7 ? -1.0 : 1.0);
      wr.Write("{0} ", d);
    }
    wr.Flush();
  }


Задача ставилась в контексте обсуждения производительности haskell'я в применении его к задачам парсинга. Я знал, что на прологе подобные задачи решаются красиво и непринужденно используя технику DCG (Definite clause grammar: 1, 2, 3, 4). Фактически, это описание грамматик на языке Пролог, и парсинг по ним, основанный на переборно-откатном принципе работы пролога.

Ну то есть обычно получается очень кратко и красиво (например, вот решение задачки о сбалансированности скобок этим методом: программа из 7 строк), но, я подозревал, что не всегда быстро. Собственно, это мне захотелось проверить.

Доброго всем понедельника. Если понедельник для вас не самый приятный день, то предлагаю вам немного расслабиться и проникнуться моим хобби. Моё хобби — решение олимпиадных задач по программированию: встряхивает мозг, будоражит воображение и заряжает энергией (правда не всегда положительной). Не верите? Попробуйте сами, только честно попытайтесь решить поставленную задачу, получите долгожданный Accepted, и наслаждайтесь полученными эмоциями.

Сегодня случай подкинул нам задачу №10474. Это задача на умение применять вовремя простые алгоритмы, поэтому не ждите от нее чего-то сложного и хитроумного. Если вам не интересно решать задачи за счет пары стандартных алгоритмов, то пропускайте топик, а всем остальным добро пожаловать под кат. Нас ждет пара алгоритмов, выбор наиболее удобного решения, ну и, конечно же, Accepted!

Привет. Сегодня понедельник, поэтому я решил, что стоит начать свой рабочий день с разогрева пальцев и мозга. Для тех кто не в курсе: мое олимпиадное хобби состоит в решении олимпиадных задач по программированию, которые я беру с сайта http://uva.onlinejudge.org/. Сегодня нам предстоит решить задачу о размене монет из области динамического программирования. Задача не очень сложная, но есть над чем поразмыслить, поэтому заинтересовавшихся прошу под кат. К слову, это третья наша задача, но, безусловно, из всех самая интересная.

При разработке CMF я столкнулся с необходимостью грамотно реализовать i18n (мультиязычность), и стал рассматривать различные варианты…

Node.js — вещь, вокруг которой сейчас много шума, восторженных отзывов и гневливых выкриков. При этом, по моим наблюдениям, в умах людей закрепилось следующее представление о том что же такое Node.js: «это штука, позволяющая писать на JavaScript на серверной стороне и использующая JavaScript-движок от Google Chrome». Поклонники языка восторженно вздохнули: «Ах! Сбылось!», противники же процедили сквозь зубы: «Ну вот только еще этой ерунды с прототипами и динамической типизацией нам на серверах не хватало!». И дружно побежали ломать копья в блоги и форумы.

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

Возникла задача написание простенького расширения под все (по возможности) популярные браузеры. Деятельность расширения заключается во внедрении javascript`а в тело документа.