Pull to refresh
116
0

Python developer

Send message

Удивительные клеточные автоматы: обратные и расширенные поколения

Level of difficultyEasy
Reading time7 min
Views3.6K


👾, Хабр!
Давно не виделись.

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

В первых статьях цикла мы познакомились с поколениями, одной из базовых и простейших модификаций стандартной конфигурации клеточных автоматов. До этого дополнения наши клетки могли находиться лишь в двух логических состояниях – пустая и живая (0 и 1, соответственно). После же, с новым параметром G, мы добавили третье положение – старение, что значило, что клетка, после выхода из состояния 1, начинала отмирать, доходя до состояния G-1, и только после возвращая состояние к 0. Во время старения клетки не влияют на соседей, не проходят проверки выживания, увеличивая собственный счётчик состояния с каждым шагом, но они и не позволяют новым клеткам рождаться на их месте.

Дополнение поколений является самым популярным, среди всех модификаций стандартной модели, и даже, фактически, оно стало частью правила по умолчанию, наравне с B/S, используясь практически во всех прочих расширениях, хотя использование поколений, конечно, опционально.

Со временем участники сообщества начали предлагать дополнения и к этому варианту конфигурации. На поверхности лежали многие вариации, как ещё возможно изменить или переставить состояния клеток. Одним из них были и обратные поколения, a.k.a. snoitareneG, с которых мы и начнём.
Читать дальше →
Total votes 39: ↑39 and ↓0+39
Comments10

Удивительные клеточные автоматы: дефицитные правила

Level of difficultyEasy
Reading time6 min
Views4.3K


👾, Хабр!

Возвращаемся к нашей экскурсии по модификациям клеточных автоматов. Объект сегодняшнего внимания – дефицитные правила (deficient rules). Это ещё более свежая вариация, чем рассмотренный в прошлом посте BSFKL, и была описана 5 лет назад энтузиастом 83bismuth38.

Модификация предполагает, что при рождении клетки на окружающих соседей налагается ограничение на рождение по этому переходу, согласно нотации Хенселя. Освежить в памяти, что из себя представляют переходы можно здесь.
Читать дальше →
Total votes 43: ↑43 and ↓0+43
Comments13

Удивительные клеточные автоматы: клетки-киллеры, BSFK[L]

Level of difficultyEasy
Reading time7 min
Views3.6K


?, Хабр!

После небольшого перерыва продолжим нашу экскурсию по различным вариациям классической конфигурации клеточных автоматов. Сегодня мы рассмотрим правила с «деструктивными клетками». Первоначальный вид подобной модификации, известной как BSFK, предложил энтузиаст под ником c0b0p0, всего 9 лет назад, спустя более чем 40 лет, после первого описания «Жизни» Джона Конвея.
Что здесь происходит (для новых читателей серии)
В этой серии мы разбираем клеточные автоматы – дискретную модель, основой которой является сетка из ячеек-клеток, которые изменяют (или не изменяют) своё состояние в зависимости от количества соседей.
Учёт соседей определяется правилами, которые устанавливаются нами. Вариаций правил существует бесчисленное множество, и они были систематизированы в определённые конфигурации.
Самая популярная конфигурация – «B/S», или «life-like», по названию крайне широко известного клеточного автомата «Game of Life», где B/S обозначает, что в нашем правиле мы описываем всего два параметра – количество соседей необходимых для рождения новой клетки в пустой ячейке, и количество соседей для выживания существующей клетки.
В каждой статье серии мы углубляемся в данную конфигурацию, добавляя новые параметры, либо дополняя существующие. Иногда заглядываем и в прочие конфигурации.
Начало серии здесь, если желаете ознакомиться последовательно.
Рассматриваемая модификация предполагает три состояния клеток – мёртвые, живые и деструктивные, и добавляет два числовых параметра в наше правило – F и K. Переходы говорят, что если у живой клетки есть как минимум K деструктивных соседей («киллеров»), она умирает. Если это условие не выполняется, то, как и в прошлых конфигурациях, происходит проверка на вхождение в множество S, но с тем отличием, что при отсутствии вхождения такая клетка не умирает, а сама превращается в киллера. Киллеры же умирают, если у них есть как минимум один живой сосед.

К условию зарождения жизни на пустых (мёртвых) клетках по числу живых соседей B добавляется «и количество соседей-киллеров не больше F».
Читать дальше →
Total votes 32: ↑31 and ↓1+46
Comments6

Удивительные клеточные автоматы: направленные и пользовательские окрестности

Level of difficultyEasy
Reading time7 min
Views3.3K


?, Хабр!

На прошлых неделях мы познакомились с различными вариациями альтернативных окрестностей – начиная с учёта расположения нотацией Хенселя, через альтернативные шаблоны расположения, и заканчивая взвешенными окрестностями. Сегодня добавим в тему окрестностей стандартного поля небольшой финальный штрих – пользовательские расположения.
Что здесь происходит (для новых читателей серии)
В этой серии мы разбираем клеточные автоматы – дискретную модель, основой которой является сетка из ячеек-клеток, которые изменяют (или не изменяют) своё состояние в зависимости от количества соседей.
Учёт соседей определяется правилами, которые устанавливаются нами. Вариаций правил существует бесчисленное множество, и они были систематизированы в определённые конфигурации.
Самая популярная конфигурация – «B/S», или «life-like», по названию крайне широко известного клеточного автомата «Game of Life», где B/S обозначает, что в нашем правиле мы описываем всего два параметра – количество соседей необходимых для рождения новой клетки в пустой ячейке, и количество соседей для выживания существующей клетки.
В каждой статье серии мы углубляемся в данную конфигурацию, добавляя новые параметры, либо дополняя существующие. Иногда заглядываем и в прочие конфигурации.
Для понимания сегодняшней статьи достаточно знать, что:
  • поиск соседей изначально выполняется в радиусе 1 (8 окружающих клеток – ), но мы можем установить другой, добавив к правилу Rx, где x – нужный нам радиус;
  • мы можем изменять шаблон окрестности поиска соседей. Изначально подразумевается окрестность Мура – R в каждую сторону (и диагональ) от рассматриваемой клетки, – но указывая Nxx мы будем определять иной шаблон, что, конечно, изменит вид правила. Сегодня мы продолжаем расширение этой части правила. Знакомство с предыдущими расширениями не является необходимым, но вы, конечно, можете предварительно ознакомиться с ними и прочими дополнениями, для большей последовательности чтения. Ссылки в конце материала и в профиле.
Читать дальше →
Total votes 38: ↑37 and ↓1+50
Comments9

Удивительные клеточные автоматы: вариативные окрестности (взвешенные, Гаусса, «далёкие углы/стороны»)

Level of difficultyEasy
Reading time13 min
Views2.9K


?, Хабр!

Вернёмся к классической модели. Две недели назад мы рассмотрели альтернативные окрестности для КА, из числа «признанных сообществом». Сегодня дополним эту тему интересными вариативными частностями, такими как «взвешенные окрестности» и «far corners»/«far edges».

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

:h Что здесь происходит (для новых читателей серии)
В этой серии мы разбираем клеточные автоматы – дискретную модель, основой которой является сетка из ячеек-клеток, которые изменяют (или не изменяют) своё состояние в зависимости от количества соседей.

Учёт соседей выполняется по указанным нами правилам. Вариаций правил существует бесчисленное множество, и они были систематизированы в определённые конфигурации.

Самая популярная конфигурация – «B/S», или «life-like», по названию крайне широко известного клеточного автомата «Game of Life», где B/S обозначает, что в нашем правиле мы описываем всего два параметра – количество соседей необходимых для рождения новой клетки в пустой ячейке, и количество соседей для выживания существующей клетки.

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

Для понимания сегодняшней статьи достаточно знать, что (продолжение под катом):
Читать дальше →
Total votes 36: ↑36 and ↓0+36
Comments4

Удивительные клеточные автоматы: блочные КА, окрестность Марголуса

Level of difficultyEasy
Reading time6 min
Views3.4K


?, Хабр!

Сегодня мы снова немного отойдём от классической модели, и будем строить конфигурацию с самого начала, благо, никаких сложностей в этом нет. Сегодняшняя конфигурация – блочные КА – предполагает, что наша сетка разбивается на некоторые участки, собственно, блоки, для которых заранее определены инструкции перехода. Никаких вариаций – один шаблон перехода для одного шаблона расположения. Звучит так, будто мы получим набор бессвязных осцилляторов, верно? Но у конфигурации есть второе условие: каждый шаг происходит смещение сетки разбиения, за счёт чего клетки при каждой следующей итерации относятся к новому блоку. Лучше, конечно, на примере.

Самой популярной моделью построения блочных КА является разбиение на блоки 2×2, со смещением на 1 клетку по диагонали за итерацию. Данная модель носит имя своего первого и основного исследователя, пионера изучения КА – Нормана Марголуса. Хоть сам вид и называют окрестностью Марголуса, он несколько отличается логически от тех окрестностей, что мы с вами обозревали ранее. А именно: данная окрестность отображает сразу оба возможных состояния, и она не привязана ни к какой конкретной клетке.
Читать дальше →
Total votes 38: ↑38 and ↓0+38
Comments5

Удивительные клеточные автоматы: альтернативные окрестности и HROT

Level of difficultyEasy
Reading time6 min
Views3.7K


?, Хабр!

В прошлой статье о циклических КА мы мельком затронули тему альтернативных окрестностей, рассмотрев несколько примеров. Несмотря на то, что ранее мы использовали только окрестности Мура и фон Неймана, существует ещё множество прочих именованных окрестностей, а потенциал для создания новых ограничен лишь нашей фантазией.

Сегодняшний обзор мы совместим с ещё одним расширением: в статье об LtL было упомянуто, что параметры рождения и выживания клетки могут поддерживать множество значений и диапазонов в некоторых прочих конфигурациях. В первую очередь речь шла о HROT (Higher-Range Outer-Totalistic) – обобщении LtL конфигурации, на котором и будут наши сегодняшние примеры.
Читать дальше →
Total votes 52: ↑52 and ↓0+52
Comments17

Пятничные клеточные автоматы: циклические конфигурации; камень-ножницы-бумага

Level of difficultyEasy
Reading time6 min
Views3K


👾, Хабр!

На прошлой неделе мы снова расширили классическую «life-like» модель, добавив к ней параметр радиуса поиска соседей. Сегодня немного отойдём от этого вида и заглянем в область прочих конфигураций. Начнём с циклических КА.
Читать дальше →
Total votes 26: ↑25 and ↓1+33
Comments8

Пятничные клеточные автоматы: 10 правил «больших, чем жизнь»

Level of difficultyEasy
Reading time4 min
Views4.5K

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

Самое популярное подобное расширение конфигурации известно как Larger than Life, или просто LtL. Его мы и рассмотрим.

?
Total votes 42: ↑42 and ↓0+42
Comments3

Пятничные клеточные автоматы: 10 удивительных правил с нотацией Хенселя

Level of difficultyEasy
Reading time7 min
Views7K

Продолжим знакомиться с вариациями клеточных автоматов. Ранее мы рассмотрели базовую «life-like» конфигурацию и добавили к ней поколения.

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

?
Total votes 57: ↑57 and ↓0+57
Comments11

10 зрелищных клеточных автоматов с поколениями

Level of difficultyEasy
Reading time4 min
Views7.5K

На прошлой неделе мы посмотрели на 10 правил простейших клеточных автоматов, где меняли только количество соседей необходимых для рождения и выживания клетки.

Сегодня мы немного дополним характеристики «life‑like» модели и добавим ещё одну часть к правилам — поколения.

?
Total votes 66: ↑66 and ↓0+66
Comments1

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

Level of difficultyEasy
Reading time5 min
Views34K

Самое простое представление двумерного клеточного автомата основано на двух характеристиках: клетки имеют всего 2 состояния; правила изменения состояния зависят только от количества живых соседей из окрестности Мура первого порядка (8 окружающих).

Такая категория КА называется «Life-like», по названию самого известного автомата с такими характеристиками – «Conway's Game of Life». Игра «Жизнь» Конвея работает на правиле B3/S23, т.е. для рождения клетки требуется ровно 3 живых соседа, для выживания – 2 или 3. Во всех других случаях клетка умирает (или же остаётся пустой).

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

Сегодня взглянем на самых интересных представителей.

?
Total votes 158: ↑158 and ↓0+158
Comments24

История моделирования лесных пожаров

Level of difficultyEasy
Reading time14 min
Views2.6K

На прошлой неделе мы моделировали идеализированный лесной пожар клеточным автоматом на Python, в общих чертах ознакомившись с основными подходами в этой области.

Но каковы истоки моделирования пожаров? Кто сегодня занимается моделированием пожаров? Почему модели пожаров не имеют такого же развития, как модели погоды, и смогут ли они когда-нибудь достичь этого?

?
Total votes 7: ↑7 and ↓0+7
Comments1

Моделирование лесных пожаров: теория, клеточный автомат на Python

Level of difficultyMedium
Reading time10 min
Views7.7K

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

Очень идеализированный лесной пожар может быть представлен с помощью простого клеточного автомата.

?
Total votes 23: ↑23 and ↓0+23
Comments15

Сегрегация общества: модель Шеллинга и распределение этнических групп в городах Израиля

Level of difficultyHard
Reading time27 min
Views3.9K

Модель сегрегации Шеллинга является одной из самых ранних агент-ориентированных моделей в социальной науке. Модель была представлена Томасом Шеллингом для иллюстрации того, как индивидуальные стимулы и индивидуальное восприятие различий могут привести к сегрегации. Хотя модель показательна для целого ряда явлений, когда люди склонны переселяться в зависимости от доли похожих соседей, она была признана особенно полезной для изучения сегрегации по месту жительства.

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

?
Total votes 6: ↑6 and ↓0+6
Comments7

REcollapse: фаззинг с использованием unicode-нормализации

Level of difficultyHard
Reading time6 min
Views4.1K

В этом посте я расскажу о технике REcollapse. Я изучал её последние пару лет, чтобы обнаружить до странности простые, но эффективные уязвимости в защищённых объектах. Эта техника может быть использована для захвата учётных записей с нулевым взаимодействием, обнаружения новых обходных путей для брандмауэров веб-приложений и многого другого.

Этот пост преимущественно основан на моём выступлении на BSidesLisbon 2022 и посвящён запуску инструмента REcollapse, который теперь доступен на GitHub. Это также то, что мы начали исследовать внутри Ethiack.

Всё начинается с непредвиденного ввода.

?
Total votes 17: ↑16 and ↓1+20
Comments0

Хватит использовать [a-zа-яё]: правильная работа с символами и категориями Unicode в регулярных выражениях

Level of difficultyMedium
Reading time14 min
Views8.8K

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

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

?
Total votes 20: ↑20 and ↓0+20
Comments8

Краткая история календаря и фантазии о шестидневной неделе

Level of difficultyEasy
Reading time14 min
Views20K

Привет, Хабр.

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

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

?
Total votes 46: ↑44 and ↓2+53
Comments99

Пройти LeetCode за год: экскурсия по сайту и roadmap [обновлено 30.11.2023]

Level of difficultyEasy
Reading time23 min
Views109K

С наступающим наступившим вновь наступающим, Хабр.

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

Конечно, про литкод все слышали и, казалось бы, о чём тут рассказывать? Ну задачник, перед техсобесами можно открыть на день-два. Но для того рассказать и стоит, дабы чуть разбавить это мнение.

С сайтом несколько больно знакомиться, он отпугивает вездесущими приписками "premium", пользуясь славой ресурса для техсобесов продвигает функционал вроде списков компаний, где встречался вопрос n и симуляции интервью в компанию m, да и сам не особо стремится рассказать о себе, потому в нём зачастую и видно голый задачник с одной страницей "problems".

За всем этим теряется важный пункт – а можно ли использовать сайт не для механического зазубривания популярных вопрос-ответов, а для изучения/закрепления алгоритмов и структур данных? Можно. Но подход к этому нужно формировать самостоятельно.

🏆
Total votes 37: ↑36 and ↓1+44
Comments30

Абсолютная мультиязычность и типографика на любой раскладке

Level of difficultyEasy
Reading time15 min
Views4.8K

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

Основная идея – использование одной раскладки для всей письменности и символьного набора, без каких-либо ограничений.

Возможно вы также слышали (а может даже и используете) о типографской раскладке Ильи Бирмана. Она добавляет многим клавишам два дополнительных слоя, с модификаторами AltGr и Alt-Shift, под которыми расположен расширенный набор символов, в числе которых символы "корректного ввода", кавычки всех видов, некоторые специфичные языковые символы, а также прочие потенциально востребованные символы и немного диакритики. Общее количество уникальных символов – около 75. За 15 лет данная раскладка приобрела немалую известность, в основном среди медиакомпаний, что служит определённым показателем востребованности.

В самом базовом представлении, данный проект следует тем же положениям – дополнительные символы на дополнительных слоях под модификаторами, для упрощения набора.

Но самое интересное в деталях, ведь так? О них и поговорим ниже, благо, есть о чём.

Total votes 4: ↑4 and ↓0+4
Comments10
1

Information

Rating
Does not participate
Registered
Activity

Specialization

Backend Developer
Python