• Russian AI Cup 2017 — всем поклонникам StarCraft и C&C посвящается


      Уже несколько лет подряд мы проводим Russian AI Cup — нехилый такой конкурс для всех неравнодушных к программированию в целом, к построению ИИ, просто к написанию ботов для игр или автоматизации чего бы то ни было. Естественно, и этот год не будет исключением. Итак, Mail.Ru Group в сотрудничестве с Саратовским государственным университетом официально объявляют о дате старта Russian AI Cup 2017 и счастливы предложить задачу этого года. Жёсткие битвы, макбуки за первые места и минус полтора месяца из жизни разработчика — всё на месте, всё как вы любите. Добро пожаловать под кат за подробностями!

      Читать дальше →
    • Что за чёрт, Python

      • Перевод


      Недавно мы писали о забавных, хитрых и странных примерах на JavaScript. Теперь пришла очередь Python. У Python, высокоуровневого и интерпретируемого языка, много удобных свойств. Но иногда результат работы некоторых кусков кода на первый взгляд выглядит неочевидным.


      Ниже — забавный проект, в котором собраны примеры неожиданного поведения в Python с обсуждением того, что происходит под капотом. Часть примеров не относятся к категории настоящих WTF?!, но зато они демонстрируют интересные особенности языка, которых вы можете захотеть избегать. Я думаю, это хороший способ изучить внутреннюю работу Python, и надеюсь, вам будет интересно.


      Если вы уже опытный программист на Python, то многие примеры могут быть вам знакомы и даже вызовут ностальгию по тем случаям, когда вы ломали над ними голову :)

      Читать дальше →
    • Игра в Бога, или как я «Волчий остров» писал

        Давным-давно, когда я еще учился в университете, я услышал что на математическом факультете в нашем вузе программистам задают интересную задачу: смоделировать так называемый «волчий остров». Суть ее примерно в следующем.



        Что на картинке
        Stop/Start — Запустить мир
        Turn — Остановить мир
        Restart — Пересоздать мир
        Зеленые клетки — Клетки с травой. Чем зеленее, тем больше травы.
        Маленькие зайцы и волки — щенки
        Большие зайцы и волки — взрослые особи
        Красные и синие полоски на пиктограммой зверей — текущая сытость. Красные — самцы, синие — самки.
        Число в левом нижнем углу каждой клетки — количество существ на данной клетке
        Внизу общее количество зайцев и волков, а также время, занявшее обработку последнего ход
        Читать дальше →
      • «Магическая константа» 0x5f3759df

        • Перевод
        В этой статье мы поговорим о «магической» константе 0x5f3759df, лежащей в основе элегантного алгоритмического трюка для быстрого вычисления обратного квадратного корня.

        Вот полная реализация этого алгоритма:

        float FastInvSqrt(float x) {
          float xhalf = 0.5f * x;
          int i = *(int*)&x;  // представим биты float в виде целого числа
          i = 0x5f3759df - (i >> 1);  // какого черта здесь происходит ?
          x = *(float*)&i;
          x = x*(1.5f-(xhalf*x*x));
          return x;
        }

        Этот код вычисляет некоторое (достаточно неплохое) приближение для формулы

        image

        Сегодня данная реализация уже хорошо известна, и стала она такой после появления в коде игры Quake III Arena в 2005 году. Её создание когда-то приписывали Джону Кармаку, но выяснилось, что корни уходят намного дальше – к Ardent Computer, где в середине 80-ых её написал Грег Уолш. Конкретно та версия кода, которая показана выше (с забавными комментариями), действительно из кода Quake.
        В этой статье мы попробуем разобраться с данным хаком, математически вывести эту самую константу и попробовать обобщить данный метод для вычисления произвольных степеней от -1 до 1.

        Да, понадобится немного математики, но школьного курса будет более, чем достаточно.
        Читать дальше →
      • Математический детектив: поиск положительных целых решений уравнения

        • Перевод
        «Я экспериментировал с задачами кубического представления в стиле предыдущей работы Эндрю и Ричарда Гая. Численные результаты были потрясающими…» (комментарий на MathOverflow)
        Вот так ушедший на покой математик Аллан Маклауд наткнулся на это уравнение несколько лет назад. И оно действительно очень интересно. Честно говоря, это одно из лучших диофантовых уравнений, которое я когда-либо видел, но видел я их не очень много.

        Я нашёл его, когда оно начало распространяться как выцепляющая в сети нердов картинка-псевдомем, придуманная чьим-то безжалостным умом (Сридхар, это был ты?). Я не понял сразу, что это такое. Картинка выглядела так:


        «95% людей не решат эту загадку. Сможете найти положительные целочисленные значения?»

        Вы наверно уже видели похожие картинки-мемы. Это всегда чистейший мусор, кликбэйты: «95% выпускников МТИ не решат её!». «Она» — это какая-нибудь глупая или плохо сформулированная задачка, или же тривиальная разминка для мозга.

        Но эта картинка совсем другая. Этот мем — умная или злобная шутка. Примерно у 99,999995% людей нет ни малейших шансов её решить, в том числе и у доброй части математиков из ведущих университетов, не занимающихся теорией чисел. Да, она решаема, но при этом по-настоящему сложна. (Кстати, её не придумал Сридхар, точнее, не он полностью. См. историю в этом комментарии).

        Вы можете подумать, что если ничего другое не помогает, то можно просто заставить компьютер решать её. Очень просто написать компьютерную программу для поиска решений этого кажущегося простым уравнения. Разумеется, компьютер рано или поздно найдёт их, если они существуют. Большая ошибка. Здесь метод простого перебора компьютером будет бесполезен.
        Читать дальше →
      • Реверс-инжиниринг одной строчки JavaScript

        • Перевод
        Несколько месяцев назад я получил от друга такое письмо:



        Тема: Можешь объяснить мне эту одну строчку кода?

        Текст: Считай меня тупым, но… я не понимаю её и буду благодарен, если растолкуешь подробно. Это трассировщик лучей в 128 символах. Мне кажется, он восхитительный.

        <pre id=p><script>n=setInterval("for(n+=7,i=k,P='p.\\n';i-=1/k;P+=P[i%2?(i%2*j-j+n/k^j)&1:2])j=k/i;p.innerHTML=P",k=64)</script>



        Эта строчка JavaScript отрисует анимацию, которая показана на изображении под катом. В браузере она запускается здесь. Скрипт написан автором www.p01.org, где вы можете найти эту и много других классных демок.
        Читать дальше →
      • Реклама помогает поддерживать и развивать наши сервисы

        Подробнее
        Реклама
      • Виртуальные твари и места их обитания: прошлое и настоящее TTY в Linux

          Ubuntu интегрирована в Windows 10 Redstone, Visual Studio 2017 обзавелась поддержкой разработки под Linux – даже Microsoft сдает позиции в пользу растущего числа сторонников Торвальдса, а ты всё еще не знаешь тайны виртуального терминала в современных дистрибутивах?

          Хочешь исправить этот пробел и открываешь исходный код? TTY, MASTER, SLAVE, N_TTY, VT, PTS, PTMX… Нагромождение понятий, виртуальных устройств и беспорядочная магия? Всё это складывается в довольно логичную картину, если вспомнить, с чего всё началось…
          Читать дальше →
        • Угадай фильтр по импульсной характеристике



            На некотором сайте, в некотором форуме, добрый молодец по прозвищу SciFi озадачил коллектив свой историей.
            Нашел он в руководящих технических материалах иноземной фирмы Texas Instruments [FSK Modulation and Demodulation With the MSP430 Microcontroller] требуемый ему цифровой фильтр. Но иноземцы шибко хитры оказались, и в исходном коде привели следующее:
            Читать дальше →
          • Аналог std::vector из C++11 на чистом C89 и как я его писал

            image
            Жилой массив людей. Нет, серьёзно.


            Холивары между ценителями Си и приверженцами его ублюдка сына в лице C++ начались ещё до моего рождения и прекратятся разве что после смерти обоих этих языков и меня заодно.


            Адепты великого творения Кернигана-Ритчи до последней секунды рабочего дня готовы доказывать приспешникам Страуструпа аксиомы про вечность Си и его невероятную гибкость.
            Те в ответ по-свойски советуют им лучше порадоваться рабочему дню, ведь он вот-вот окажется последним – двадцать первому веку кроссплатформенный ассемблер не нужен.
            Распаляясь, сторонники Си приводят миллионы давно прошедших через голову навылет тезисов "почему Си лучше C++", при этом каждый раз подчёркивая, что второй все достоинства первого растерял ещё будучи в отцовской утробе, попутно утратив лик человеческий.
            Обвиняемая сторона в обиде не остаётся и...


            а хотя постойте, о чём это я.


            Я люблю Си, уважаю C++ и не переношу холивары (честно). При этом я осознаю, что в Си действительно не хватает многого, и яркий тому пример – отсутствие удобной работы с данными. В C++ эту проблему во многом решает STL и свойства самого языка. На мой студенческий взгляд, здесь особо отличается всем знакомый std::vector. Если стало интересно, как я реализовал его аналог средствами C89 – прошу под кат.

            Читать дальше →
          • Считаем до трёх

              Троичные вычисления


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



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

              На любые вопросы из разряда «зачем?!» я отвечаю заранее: «Because I can».


              Читать дальше →
            Самое читаемое