• Считаем кур, пока их не заклевали

    • Перевод
    Эта история началась с короткой статьи в New York Times о Люке Робитейле, 13-летнем школьнике из Юлесса, штат Техас, который выиграл Raytheon Mathcounts National Competition, правильно ответив на следующий вопрос:
    В амбаре кружком сидят 100 кур. Каждая из кур случайным образом клюёт свою ближайшую соседку слева или справа. Каково ожидаемое количество кур, которых никто не клюнул?
    Судя по статье Times, Робитейлу потребовалось на ответ меньше секунды.

    На следующий день Джордан Элленберг твитнул такую задачу:

    Text of Ellenberg's tweet: 100 chicks in a circle. Each pecks R or L at random. Pecked chicks don't peck. Iterate until no two unpecked chicks adjacent. How many left?

    «100 кур сидят в круге. Каждая клюёт случайным образом R или L. Клюнутые куры никого не клюют. Итерации проводятся до тех пор, пока не останется двух соседних неклюнутых кур. Сколько кур осталось?»

    Мне не нужно умещать эту историю в 140 символов, поэтому я дополню вопрос Элленберга подробностями так, как я его понял. Исходная задача относилась к одной итерации синхронизированного случайного клевания, а теперь у нас есть несколько итераций. Во время одной итерации каждая курица случайным образом поворачивается влево или вправо и клюёт одну из своих соседок. Однако если курицу уже клюнули, она больше никогда не клюёт, даже её продолжают клевать. Если две соседние курицы клюют друг друга в одной итерации, обе они вылетают из игры на все последующие раунды. Если неклюнутая курица оказывается между двумя клюнутыми, её уже никогда не клюнут и поэтому она может клевать бесконечно. Вопрос заключается в том, какая часть кур выживет и станет «неуязвимыми»?

    Ниже представлены спойлеры, так что сейчас вы можете попробовать ответить на вопрос сами. Пока вы этим занимаетесь, я немного поговорю о курах и о риторике и семиотике математических «текстовых задач».
    Читать дальше →
  • Пандус для сайта

      Привет, Хабр. Я Иван Бакаидов. Сегодня я хочу поделиться с вами своим докладом “Почему я не могу пользоваться твоим сайтом?”. В этом докладе я рассказываю о проблемах доступности современного Веба для людей с особенностями здоровья. Уверен, что вы не задумывались над этой проблемой, хотя для некоторых пользователей это может быть решающим фактором в использовании вашего ресурса. Даже обычные статьи на хабре плохо читаются скринридерами, так как никто не указывает описание изображения в alt.

      Под катом будет представлено небольшое описание содержания Видео, а еще полезные ссылки по теме, а также выдержки из моих постов про баттлы с Yota и Сбербанком.


      Читать дальше →
    • Разбираемся, что же там нового открыли в задаче о ферзях

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


        image
        Сможете поставить ещё шесть? А найти все решения?
        (картинка из статьи)


        Далее, к сожалению, произошла какая-то совершенно невразумительная история из цепочки вот таких вот превращений:



        Стоит отметить, что пять наугад открытых ссылок на русском ещё меньше проясняли картину происходящего.


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


        О чём пойдёт речь:


        Читать дальше →
      • 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 — Пересоздать мир
            Зеленые клетки — Клетки с травой. Чем зеленее, тем больше травы.
            Маленькие зайцы и волки — щенки
            Большие зайцы и волки — взрослые особи
            Красные и синие полоски на пиктограммой зверей — текущая сытость. Красные — самцы, синие — самки.
            Число в левом нижнем углу каждой клетки — количество существ на данной клетке
            Внизу общее количество зайцев и волков, а также время, занявшее обработку последнего ход
            Читать дальше →
          • AdBlock похитил этот баннер, но баннеры не зубы — отрастут

            Подробнее
            Реклама
          • «Магическая константа» 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… Нагромождение понятий, виртуальных устройств и беспорядочная магия? Всё это складывается в довольно логичную картину, если вспомнить, с чего всё началось…
              Читать дальше →
            Самое читаемое