Одним вечером я наткнулся на статью о реализации одномерного клеточного автомата с помощью комонад, однако материал неполон и немного устарел, в связи с чем решил написать русскоязычную адаптацию (заодно рассмотрев двумерные клеточные автоматы на примере Game of Life)
Метка «клеточный автомат»
Клеточные автоматы с помощью комонад
2014-06-06 в 12:21, admin, рубрики: game of life, haskell, жизнь, клеточный автомат, функциональное программирование, метки: game of life, haskell, жизнь, клеточный автомат
Клеточные автоматы на Dart
2014-01-09 в 2:53, admin, рубрики: dart, жизнь, клеточный автомат, Программирование, метки: dart, жизнь, клеточный автоматРеализация классического клеточного автомата — конуээвской «Жизни» — это такая же задачка для начинающего программиста, как для радиотехника — спаять простейший радиоприемник. Для тех кто не знает, что такое «Жизнь», прочитайте эту статью: Википедия: Жизнь (игра).
Напомню правила: действие происходит на клеточном поле. Каждая клетка имеет 8 соседей — клетки, примыкающие к ней сторонами или углами. В начале игры некоторые клетки заполнены, образуя начальный организм, остальные — пусты. Эволюция происходит так: в следующем поколении очищаются все заполненные клетки, имеющие менее 2 или более 3 соседей и заполняются пустые, имеющие ровно 3 соседа.
После того, как поиграешь с интересными конфигурациями, становится немного скучно. В самом деле, за 40 лет все, что можно описано, разжевано на сотнях страниц различных статей и книг. Найти что-то новое и интересное сложно. Тогда возникает желание поменять правила — а вдруг новые организмы будут вести себя совершенно по-иному?
Как заставить мир аплодировать стоя. Делаем стартап популярным
2013-06-21 в 8:53, admin, рубрики: Алгоритмы, клеточный автомат, математика, моделирование, теория автоматов, метки: клеточный автомат, моделирование, теория автоматовПредставьте, что мир — это концертный зал, а ваш только что запущенный стартап — это шоу, которое секунду назад завершилось, и публика вот-вот начнёт рукоплескать вам стоя, либо отделается вялыми хлопками в разных углах зала. Почему по-настоящему гениальные спектакли искушённая публика иногда встречает сдержанно и даже холодно, а некоторые посредственные — криками «Браво»? Как сделать так, чтобы ваш стартап оценили по достоинству, и даже лучше? Как заставить мир аплодировать вам стоя?
Профессор Мичиганского Университета Scott E. Page, известный по курсу Model Thinking на Coursera, в соавторстве с John H. Miller в 2004 году предложили изящную модель «Standing Ovations», которая с помощью клеточного автомата описывает, будет ли зал аплодировать стоя, в зависимости от некоторых факторов. В этой статье я сначала опишу модель максимально упрощённо, а затем, под катом, перейду к небольшим математическим и околоматематическим выкладкам, к построению клеточного автомата, а в конце — к выводам применительно к стартапу и другим сферам жизни.
На секунду представьте себя в зрительном зале в волнительный момент опускания занавеса. Что может заставить вас встать и начать аплодировать? Во-первых, разумеется, вам должен понравиться спектакль. Во-вторых, вы, скорее всего, будете чувствовать себя неловко, если окажетесь единственным человеком в зале, аплодирующим стоя (равно как и если все вокруг встанут, а вы будете сидеть). Значит, необходимо, чтобы некоторая часть аудитории уже решила встать. В-третьих, если вы пришли на спектакль с друзьями или семьёй, и кто-то из них встал, то вы, вероятно, захотите его поддержать и встанете тоже. В-четвёртых, вам виден не весь зал. В зависимости от места, которое вы занимаете, вам могут быть видны только первые ряды партера, половина зала или, если вы сидите в первом ряду, то вообще никто кроме ваших соседей. Следовательно, в первую очередь на ваше решение влияет только та часть зала, которая вам видна.
Таким образом, можно выделить четыре фактора, влияющих на то, встанете ли вы:
- Ваше впечатление от шоу;
- Доля аудитории, которая уже решила встать;
- Поведение ваших соседей по ряду;
- Поведение «звёзд», сидящих в первых рядах;
Игра «Жизнь». Опять. На этот раз в 3D
2012-10-14 в 17:03, admin, рубрики: c++, OpenGL, Алгоритмы, жизнь, клеточный автомат, параллельное программирование, метки: c++, OpenGL, жизнь, клеточный автомат, параллельное программированиеЗа последнюю неделю Хабр пополнился сразу несколькими статьями об игре «Жизнь». Что ж, тогда и я поделюсь своими наработками по этой теме.
Предисловие
Минувшим летом мне довелось побывать на летней школе по параллельному программированию, проводимой НГУ. В рамках школы каждый студент должен был подготовить какой-либо проект по одной из тематик, озвученных на лекциях. Меня заинтересовали клеточные автоматы. У меня первая ассоциация при фразе «клеточный автомат» это именно «Жизнь».
Я понимал, что никому не будет интересно наблюдать за черными клеточками, живущими на экране. Да и слишком просто это для такого проекта. Нужно было придумать что-то принципиально новое. Я решил расширить диапазон своих мыслей и выйти за пределы двухмерного пространства. В прямом смысле. Я подумал, а почему бы не сделать эту игру трехмерной? Ведь это гораздо интереснее!
Читать полностью »
Реализация игры «Life 1970» на javascript’е с использованием TTD
2012-09-21 в 9:42, admin, рубрики: BusterJS, Conway's game of Life, javascript, tdd, ttd, клеточный автомат, метки: BusterJS, Conway's game of Life, javascript, ttd, клеточный автомат Есть прекрасная игра/алгоритм «Conway's Game of Life» [wiki] — это набор правил для клеточного автомата который определяет жизнь колонии. Алгоритм был придуман английским математиком в далеком 1970 году.
Игровое поле — квадратная сетка неограниченного размера.
Каждая клетка может иметь два значения Живая или Мертвая
Игрок задает начальное положение клеток на поле и потом наблюдает как они эволюционируют.
Правил эволюции всего 4 и звучат они так:
- Живая клетка у которой меньше двух соседей умерает от одиночества.
- Живая клетка у которой 2 или 3 соседа живет до следующего хода.
- Живая клетка у которой больше 3 соседей умирает от перенаселения.
- Мертвая клетка у которой ровно 3 живых соседа становаится живой (рождается).
Соседними считаются клетки по вертикали, горизонтали и диагонали. Т.е. у одной клетки может быть восемь соседей.
Эти простые правила позволяют реализовать машину Тьюринга и даже простые колонии (наборы живых клеток) могут обладать очень интересными свойствами.
Я решил реализовать алгоритм на джаваскрипте с ипользованием TTD и рассказать об этом.
Читать полностью »
Реализация игры «Life 1970» на javascript’е с использованием TDD
2012-09-21 в 9:42, admin, рубрики: BusterJS, Conway's game of Life, javascript, tdd, клеточный автомат, метки: BusterJS, Conway's game of Life, javascript, tdd, клеточный автомат Есть прекрасная игра/алгоритм «Conway's Game of Life» [wiki] — это набор правил для клеточного автомата который определяет жизнь колонии. Алгоритм был придуман английским математиком в далеком 1970 году.
Игровое поле — квадратная сетка неограниченного размера.
Каждая клетка может иметь два значения Живая или Мертвая
Игрок задает начальное положение клеток на поле и потом наблюдает как они эволюционируют.
Правил эволюции всего 4 и звучат они так:
- Живая клетка у которой меньше двух соседей умерает от одиночества.
- Живая клетка у которой 2 или 3 соседа живет до следующего хода.
- Живая клетка у которой больше 3 соседей умирает от перенаселения.
- Мертвая клетка у которой ровно 3 живых соседа становаится живой (рождается).
Соседними считаются клетки по вертикали, горизонтали и диагонали. Т.е. у одной клетки может быть восемь соседей.
Эти простые правила позволяют реализовать машину Тьюринга и даже простые колонии (наборы живых клеток) могут обладать очень интересными свойствами.
Я решил реализовать алгоритм на джаваскрипте с ипользованием TDD и рассказать об этом.
Читать полностью »