Когда-то на первом курсе я осваивал C, а чтоб было веселее, мы с товарищами факультативно разбирали принципы функционирования работ с IOCCC bit.ly/2PzRtBJ — международного соревнования на самый запутанный код на C, которое проходит с некоторыми перерывами с 1984 года. Сейчас проверил — оно живо и поныне, вот, например, работа этого года bit.ly/2QUzLOc, которая компилируется в разные штуки, если поворачивать и отражать её исходный код, оформленный в виде квадрата. Любителям хардкорного дебага рекомендую.

Существовала также попытка bit.ly/1rlsDVE сделать аналогичный ежегодный конкурс для Perl, но она продержалась недолго. По моей версии, был слишком высокий риск сингулярности, и проект пришлось закрыть, а причастных изолировать.

Ну а в этом году, в соответствии с моей концепцией JS is the new ASM bit.ly/2MbycoY, товарищ Arvid Gerstmann организует IOJCC bit.ly/2UCpi97, такое же соревнование по Javascript-поделкам. Приём работ уже открыт и продлится до первого марта 2019 года. Тем временем, вдохновение для участия в конкурсе можно черпать в Dwitter-е bit.ly/2Gh07FK -- twitter-like проекте, где каждый пост является 140-символьным javascript кодом.

Внезапно: письмо Клода Шеннона (отца теории информации) bit.ly/20DRhC6 Уоррену Мак-Каллоку (отцу математической модели нейрона) bit.ly/2eSkb1q про Рона Хаббарда (отца саентологической церки и дианетики) bit.ly/2SKKxDO. Вроде не фейк, переписка в т.ч. упоминается в bit.ly/2S28Woo

Набрёл на довольно старый уже проект по "гармонизации" картин -- добавляем на изображение инородный объект и стилизуем его под оригинал. Не сложно, но кажется, из этого можно сделать что-то интересное. Статья: bit.ly/2SPHp9E код и больше картинок: bit.ly/2GVC5fq

Подробный и очень интересный flow-chart истории мировых религий, автор -- историк John B. Sparks, редакция 1952 года от Rand McNally. Подробный зум и возможность купить большой постер тут: bit.ly/2UT2Oka

В рубрике "уголок кибернекрофилии":

Есть такой древний хтонический жанр компьютерных игр interactive fiction, иногда ещё называемый text adventures или просто adventures. Игры этого жанра представляют собой нечто среднее между интерактивной книгой, игрой в ADnD с хорошим DMом и классическим квестом, но без графики. Собственно, жанр quest от interactive fiction и произошёл, когда появились достаточно хорошие графические мониторы.

Если совсем не слышали, какую-то совсем базовую вводную о жанре можно почитать тут bit.ly/2SbNQnJ, ну или вот серия моих древних постов на эту тему bit.ly/2PQfCnJ, bit.ly/2rOqclI, bit.ly/2Cqmmp2, а ещё есть отличный документальный фильм Get Lamp bit.ly/2SZ2bDP. Пик популярности этих игр пришёлся на начало 80х bit.ly/2GvtZhV, потом были годы забвения, но небольшая тусовка жива до сих пор и периодически радует свою аудиторию интересными indie поделками. Играть в такие игры довольно сложно, особенно, если не начал в детстве -- очень высокий порог входа, но если всё-таки хотите попробовать, рекомендую использовать Frotz или Gargoyle в качестве интерпретатора, а из игр начать, например, с The Wizard Sniffer bit.ly/2ScIx7p или Hunger Daemon bit.ly/2Gv3xVK -- они небольшие, простенькие и с хорошей встроенной системой подсказок.

Я давно хотел про всё это здесь написать, а тут и повод подвернулся: в этом году исполнилось 20 лет классической игре Anchorhead в жанре лавкрафтовского хоррора bit.ly/2SbahJG, и мэтры жанра отметили это трибьютом, для которого 84 автора сделали по одной локации, а потом собрали это всё в нечто под названием Cragne Manor bit.ly/2LqmebI. Опубликовали всё это буквально неделю назад, так что я сам ещё не успел посмотреть (может, на праздниках), но некоторые фамилии в списке авторов впечатляют.

Кстати, если кто уже играет в IF и хочет присоединиться к совместному прохождению чего-то сложного, пишите в личку (последние года полтора мы вяло штурмуем The Mulldoon Legacy). Но новичкам лучше сначала поиграть во что-то вводное, например, пройти первого Zork.

Календарь фаз Луны на 2019 bit.ly/2BAtKMV от Майкла Бостока, автора D3js.org, много лет работавшего дата-журналистом в NYT. Кстати, рекомендую поизучать его работы: bit.ly/28Y3uwb, сам Тафти его очень хвалит on.ft.com/2rPEaDW :)

Третьего дня вышел новый выпуск bit.ly/2QKYQf1 ежегодного альманаха SEEDS, посвящённого процедурной генерации контента -- музыки, графики, игр, текстов и прочего. Выпускает его команда ProcJam.com — британского хакатона той же направленности.

Как автора проекта Нейронная оборона и яндексового Автопоэта меня не может не радовать эта карикатура на один из первых генераторов поэзии AUTO-BEATNIK, 1962 года bit.ly/2BFWxPR. Помню как-то читал лекцию про свои поделки на школе Хороший текст, так "настоящие поэты" слушали меня с такими же лицами :)

Случайно узнал, что Дональд Кнут (один из главных учёных-информатиков ХХ века) до сих пор читает раз в год рождественскую лекцию по алгоритмам в Стэнфорде, в этом году на днях прошла 24 ежегодная лекция bit.ly/2GCjObu, в этот раз она посвящена алгоритму Dancing Links bit.ly/2V9vVzR. Для меня это субъективно перекликается с ежегодными лекциями Зализняка по расшифровке берестяных грамот bit.ly/2EJVotT, которые Андрей Анатольевич читал до своей смерти в прошлом году, а с этого года продолжил читать Алексей Алексеевич Гиппиус.

Пост, повышающий связность данного бложика: По ссылке из SEEDS t.me/pathetic_low_freq/152 я нашёл проект bit.ly/2bvwIEx рейтрейсера t.me/pathetic_low_freq/133 на визитке, выигравшего IOCCC 2011 t.me/pathetic_low_freq/145.

Давайте, я немного расскажу вам про probabilistic data structures bit.ly/2BMtgmI. Это такое семейство алгоритмов, чья работа выглядит слегка похожей на магию, если не знать, что под капотом. Применяются они, в основном, для подсчёта всяких стриминговых статистик, и поэтому последние лет 10-15, по мере роста объемов данных, стали очень востребованы.

Вот простой пример: пусть у вас есть поток посещений вашего сайта, каждое -- с идентификаторами пользователя, вы читаете этот поток и хотите по итогу (ну, и в каждый момент времени) понимать, сколько было уникальных пользователей. Если решать задачу в лоб и хранить множество уже известных пользователей, это будет что-то в духе O(n log n) по сложности и O(n) по памяти, что для современных объёмов просто не влезет в память. А вот, например, алгоритм HyperLogLog bit.ly/2VgfuSd позволяет считать и уточнять по мере поступления новых данных мощность множества с использованием константной памяти и линейной сложностью. Но есть ньюансы -- оценка будет вероятностной. Грубо говоря, допуская в оценке ошибку порядка 2%, можно "хранить" множество порядка миллиардов элементов всего в паре килобайтов памяти, и память при этом не зависит от объема множества. В большинстве случаев в таких алгоритмах есть явный компромисс между объёмом памяти и ожидаемой ошибкой, так что можно управлять точностью. Но в данном случае такое хранение оптимизировано под конкретную задачу -- оценка мощности множества, а другие операции с ним не доступны. Аналогично, есть алгоритмы для других задач: дёшево вероятностно проверять наличие элемента в множестве можно с помощью BloomFilter или Quotient filters, оценивать объём пересечения двух множеств -- с помощью MinHash, и так далее. Работа перечисленных алгоритмов и аналогичных основана на статистических свойствах больших выборок случайных величин, а случайность их обеспечивается использованием хэш-функций с хорошими перемешивающими свойствами. Больше почитать про такие штуки и посмотреть простые примеры кода можно тут bit.ly/2VhjP82, а вот тут есть более солидный подбор ссылок на тему bit.ly/2rWTCOi

До кучи упомяну, что всякие выборочные статистики в духе среднего и дисперсии можно считать по потоку сразу точно, без погрешностей, например, с помощью алгоритма Велфорда и его аналогов. А для подсчёта медианы по потоку есть эвристический FAME algorithm и его более сложный аналог Chlamtac-Jain P-squared algorithm -- для оценки произвольных персентилей.

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

Первый блок -- интересные датасеты, чтоб вам было с чем поиграться на праздниках:
 * Большой архив текстовых отчётов об ощущениях при приёме психоактивных средств: bit.ly/2Q7IhEN. К нему визуализация bit.ly/2n63AeQ и прекрасный твиттер покойной марковской цепи, обученной на трипах и письмах рекрутеров bit.ly/2EUk0A7
 * Пара больших архивов с описанием сновидений: bit.ly/2SxcT4V и bit.ly/2VikOoj
 * Огромная база свидетельств о наблюдении НЛО bit.ly/2EWunnk с описаниями
 * Online API к датасету сериалов bit.ly/1WYgxn4

Второй блок -- прочая белиберда:
 * BATAS bit.ly/2TkJhaT -- чумовой проект ассемблера x8086 на .bat-файлах (один опкод -- один .bat-файл);
 * Наглядная иллюстрация на тему "как горящее вещество влияет на цвет пламени" bit.ly/2TlvDEt;
 * 10 минут зума во фрактал Мандельброта в хорошем качестве, без смс bit.ly/2PIIkuL;
 * Краткая история самого трешового репозитория на гитхабе bit.ly/2rZQSjp;
 * Фотоинструкция, как скрутить заузленный тор из обычного бублика (бейгеля) bit.ly/2GLzmd1;
 * bit.ly/2tMUnea -- 10 часов видео вращения фрактала Эшера в пространстве Лобачевского под звук Шепарда (субъективно воспринимающийся, как постоянно понижающийся);
 * Подборка красивых подписей каллиграфов в куфическом письме bit.ly/2GN4Sr7;
 * Видео из рубрики "забавы скучающих физиков" bit.ly/1fR7X5J -- запуск левитирующей на эффекте сверхпроводимости тележки вдоль по ленте Мёбиуса.

Хороших праздников!

Всех с прошедшими, время продолжать низкочастотные шалости!

У Чарльза нашего Доджсона в его "Алисе в Зазеркалье" есть чудесный стишок Jabberwocky bit.ly/2sOJbhI. На русском языке он всем известен в переводе Дины Орловской ("Варкалось. Хливкие шорьки...") под названием Бармаглот. Интересен этот стих тем, что первое его четверостишье сплошь состоит из несуществующих слов (не считая служебных), и в этом смысле он похож на глокую куздру bit.ly/1F9qDu1 — знаменитый синтетический пример, придуманный академиком Щербой для лекций по языкознанию.

Так вот, когда-то давно я придумал идею написать генератор таких стишков, записал её и забыл на несколько лет. А тут на праздниках дошли руки откопать это из моего бесконечного 2do-списка и сделать "бармаглотор". Я взял за основу своего Нейропоэта, соорудил поверх несколько хитрых эвристик, сохраняющих благозвучие слов, добавил фонетку и рифмовку, размер взял такой же, как у Орловской (чередующийся четырёх/трёхстопный ямб). Получилось примерно так:

    в проле кореной сож калей
    прось пранени ролей
    под прастом столи тсех сказей
    и вдруг пренет веплей

тогда мой пралеск что нероб
их страли пен не гоб
и лерный воный лерный стоб
пренораленый соп

    и проны сьет и нений спод
    мой пеный поралод
    и кто-то лоет постерод
    до кали до стухсот

здесь там в расях реровших тней
на повах у сказей
в своей постале от норей
в повене сталом рей

Внезапно, монопедальный прыгающий робот Salto-1P из Беркли.
Статья про него: bit.ly/2H8Uius
Лаборатория BiomimeticMillisys: bit.ly/2FqMOk6
Их официальный ютуб канал: bit.ly/2RoQaLC

Сегодня напишу про комбинаторику британского колокольного звона.

В 17 веке англичане придумали крепить колокол внутрь колеса bit.ly/2RDU9TY, что дало возможность легко поддерживать равномерный ритм звона колокола, но затрудняло существенное отклонение от этого ритма. Поэтому был придуман специальный стиль звона Change ringing bit.ly/2Fowssj, при котором колокола постоянно звонят строго по очереди, но от одного проигрыша (change) к следующему любые два соседних в порядке следования колокола могут поменяться местами. Каждый колокол имеет отдельного оператора, а рядом с ними сидит специальный кондуктор, который подсказывает, кому с кем меняться перед следующим проигрышем.

Дальше начинается математика перестановок: например, на 6 колоколах возможны 720 различных проигрышей (change), но граф переходов разрежен (из каждого узла выходит 12 ребёр, включая 1 петлю). Естественным образом возникает задача оптимального обхода этого графа. У звонарей такое исполнение, где присутствуют все возможные changes называется extent, а такое, где ни одна ещё и не повторяется дважды -- true extent. Не-тру extents, естественно, никого не интересуют.

Конструкция колокола ограничивает скорость исполнения, так что считается что на 1 change уходит около 2 секунд, поэтому на extent на 6 колоколах уходит примерно полчаса непрерывной игры без повторов. На семи колоколах extent можно сыграть часа за 3. Исполнение extent для восьми колоколов официально зарегистрировано лишь однажды, в 1963 году, и заняло 17 часов 58 минут bit.ly/2H7skiI. Т.к. на двенадцати колоколах честный extent придётся исполнять около 30 лет кряду, много споров вызывал вопрос, можно ли сыграть в таком случае что-то немного покороче. И наоборот, на пяти колоколах можно отыграть extent буквально за пару минут, что выглядит совсем уж не спортивно. По этому поводу в конце 19 века британцы собрали Central Council of Church Bell Ringers (CCCBR), на первом заседании которого долго обсуждали семантику понятия peal -- а именно, сколько надо играть, чтобы хватило вдоволь. Решили, что 5000 changes в целом достаточно, чтобы как следует задолбаться, поэтому peal на 6 колоколах равен 7 extents подряд. На пяти колоколах -- 42 extents, а на семи достаточно одного.

Запомнить последовательность из 5000 неповторяющихся changes тяжеловато. С современной точки зрения вся эта комбинаторика неплохо описывается теорией кос bit.ly/2M1Kt0k, а тогда, в 17 веке, англичане придумали понятие method ringing -- чтобы не мучать кондуктора, каждый из звонарей запоминает простую эвристику (method), по которой сам понимает, когда ему следует меняться с соседями, чтобы сыграть. Этот вот метод, задающий эвристику обхода, и является конкретным музыкальным произведением для исполнения на колокольне. Вариантов обхода графа много, методы с тех пор постоянно придумывают и официально публикуют -- чтобы желающие могли проверить, насколько они true extent. Кроме того, регулярно публикуется информация о том, кто и где какой метод впервые сыграл на практике. Под это дело в 1911 году CCCBR основали специальный еженедельник Ringing World bit.ly/2ChaVyG, который регулярно выходит до сих пор, а на сайте доступны несколько бесплатных номеров и платные архивы за весь период.

Больше ссылок:
Видео запись фрагмента Cambridge Maximus peal, исполняемого в кафедральном соборе Вустера: bit.ly/2Cf9IaT
Большой портал по теме: bit.ly/2CgMrFp
А вот тут можно побаловаться с онлайн эмулятором: bit.ly/2Fp8SeM

В теории игр есть раздел бесконечных игр, для которых цена игры может быть трансфинитным числом. Набрёл на бложик, автор которого ищет примеры позиций бесконечных шахмат с заданной бесконечной ценой игры bit.ly/2D8CX0J. На картинке — позиция с ценой ω^4.

В школе баловался генерацией фракталов с помощью моделей диффузорно-ограниченной аггрегации bit.ly/2HlWoaK, и получались очень похожие картинки, а тут народ украшает ими дерево bit.ly/2FBuW6m. Эффект называется фигурами Лихтенберга bit.ly/2eIqnXc.