Questions tagged [cellular-automata]
Puzzles involving cellular automata, such as Conway's Game of Life.
37
questions
1007
votes
6answers
212k views
Build a working game of Tetris in Conway's Game of Life
Here is a theoretical question - one that doesn't afford an easy answer in any case, not even the trivial one.
In Conway's Game of Life, there exist constructs such as the metapixel which allow the ...
114
votes
16answers
15k views
Implement the Game of Life on Anything but a Regular Grid
Conway's Game of Life is (almost) always played on a regular square grid, but it doesn't need to be.
Write a program that implements the standard cell neighboring rules from Conway's Game of Life on ...
69
votes
15answers
6k views
The Quantum Drunkard's Walk
It is well known that a person on a grid under the influence of alcohol has an equal chance of going in any available directions. However, this common-sense statement does not hold in the realm of ...
59
votes
32answers
15k views
Shortest Game of Life
Conway's Game of Life is the classic example of cellular automation. The cells form a square grid and each has two states: alive or dead. On each turn, each cell simultaneously updates according to ...
59
votes
13answers
5k views
Build a sandpile
An abelian sandpile, for our purposes, is an infinite grid with integer coordinates, initially empty of sand. After each second, a grain of sand is placed at (0,0). Whenever a grid cell has 4 or more ...
59
votes
20answers
6k views
Dig a border trench
Background: Too many illegal immigrants from Blandia are crossing the border to Astan. The emperor of Astan has tasked you with digging a trench to keep them out, and Blandia must pay for the expenses....
46
votes
15answers
2k views
Electrons bouncing in a wire
Imagine a "wire" that has n spaces. Imagine further that there are "electrons" in that wire. These electrons only live for one unit of time. Any spaces in the wire ...
32
votes
2answers
2k views
Build a digital clock in Wireworld
Inspired by this Game of Life question.
Wireworld simulates "electrons" flowing through "wires", simple arrangements of which produce typical logic gate behavior.
I challenge you to build a digital ...
31
votes
4answers
708 views
Plurality Voting with Cellular Automata
There's a really important problem in cellular automata called the Majority problem:
The majority problem, or density classification task is the problem of finding one-dimensional cellular ...
27
votes
17answers
6k views
Simulate Rule 110
Rule 110 is a cellular automaton with some interesting properties.
Your goal is to simulate a rule 110 in as few characters as possible.
For those who don't know, rule 110 is simulated line by line ...
27
votes
3answers
1k views
Simple redstone simulator
Redstone is a material in the game Minecraft, and it is used for many complex contraptions. For this program, you will only need to simulate three items: the redstone wire (noted with R), redstone ...
25
votes
20answers
2k views
Bacterial expansion
Colonies of bacteria labelled 1 through 9 live on a segment of equally-spaced cells, with empty cells indicated by ...
24
votes
8answers
2k views
Simulate the Wireworld cellular automaton
Wireworld is a cellular automaton that was designed to be resemble electrons flowing through wires. Its simple mechanics allow the construction of digital circuits. It has even permitted the ...
23
votes
10answers
2k views
The XOROR sequence
Cellular Automata are truly fascinating. The ones that are usually talked about are the binary ones, i.e., the ones representable by a number. However, those, in my opinion, have been done to death. ...
19
votes
6answers
1k views
Stable Game of Life
Challenge:
Given a matrix (or 2d array) of 0s and 1s, output the number of steps it takes for Conway's game of life to reach a stable state, or -1 if it never reaches one. A stable state is a state ...
19
votes
3answers
3k views
The strange life of a beehive
Researchers recently discovered an interesting bee colony that lives in an
infinite field of honeycomb:
Each cell can house a bee or not. In fact, the lives of those creatures
appear to be a ...
18
votes
3answers
1k views
Find the identity sandpile
This question is about abelian sandpiles. Read this previous challenge and watch this numberphile video to learn more.
An abelian sandpile of size n by n is a grid containing the number 0, 1, 2 and 3 ...
17
votes
8answers
1k views
Digital Cellular Automata
Write a program or function that takes in an odd positive integer N and a string of decimal digits (0123456789). The string represents a ten-state one-dimensional ...
17
votes
1answer
1k views
Life: Created or Evolved?
Given the state of a square Game of Life grid, determine whether it could have evolved from any previous state, or could only have been created. That is, identify whether the state is a "Garden of ...
16
votes
3answers
3k views
Longest non-repeating Game-of-Life sequence
Given a positive integer N,
determine the starting pattern on a N x N-grid that yield
the longest non-repeating sequence under Game of Life-rules, and ends
with a fixed pattern (cycle of length 1), ...
15
votes
4answers
726 views
Change the rules of Life
Life-like cellular automaton are cellular automaton that are similar to Conway's Game of Life, in that they operate on a (theoretically) infinitely large square grid, where each cell has exactly 8 ...
asked Oct 20 '17 at 15:28
caird coinheringaahing
13.5k3 gold badges34 silver badges101 bronze badges
14
votes
5answers
1k views
Simulate any 1D cellular automaton
The Challenge
You are to write a complete program that takes seven numbers from STDIN, and prints the two dimensional history of the cellular automaton (CA) to STDOUT. This is code golf.
Input ...
14
votes
7answers
622 views
Pseudorandom Cellular Automaton
Introduction
In this challenge, we will simulate a certain probabilistic cellular automaton using very bad pseudorandom numbers.
The cellular automaton is defined on binary strings by the following ...
13
votes
6answers
757 views
Binary self-rotation
Given a binary 3D array, for each layer, cyclically rotate up each of its columns as many steps as indicated by the binary encoding of the columns of the layer above it, and then cyclically rotate ...
12
votes
6answers
534 views
Topple the sandpile
(There are related questions about infinite sandpiles, and finding identity elements of sandpiles.)
Given a matrix of non-negative integers, return a matrix of the same dimensions, but toppled:
If ...
11
votes
11answers
3k views
Simulate a 1D Game-of-Life-ish Model
This question just trended over on code-review and I figured you might like it adapted as a codegolf challenge:
You are given a non-empty list of x houses represented as booleans. Each day, the ...
11
votes
9answers
764 views
Implement a strange automaton
I was playing around with cellular automaton and I found one that had some interesting behavior. Here's how it works:
It reads a binary string from left to right, if it encounters a ...
11
votes
2answers
344 views
Golf Paterson's Worms
Paterson's worms are a kind of cellular automaton that exist on an infinite triangular grid and, every step, they turn in some direction and move one unit. Their defining properties are that they can ...
11
votes
0answers
738 views
Find a Glider Synthesis (Game of Life)
Challenge Summary
In summary, the challenge is to provide the glider synthesis for a Game of Life configuration, which is your input.
What does this mean?
Well, firstly, let me explain a few terms. ...
10
votes
4answers
685 views
Game of Life and Fatigue
Stewie's Game of Life and Fatigue is quite similar to the more famous Conway's Game of Life.
The universe of the Stewie's Game of Life and Fatigue (GoLF) is an infinite two-dimensional orthogonal ...
10
votes
3answers
301 views
Identifying Sequences for Cellular Automata
Background
For the purposes of this challenge, an n-state cellular automaton is simply a binary function f that takes two ...
9
votes
2answers
456 views
The Tax Historian
Introduction
There is a tax collector that has some trouble managing the taxes of his kingdom: the historical records have burnt down in a great fire.
He wants to find out how many possible pasts ...
9
votes
0answers
779 views
Emulate Rule 110 with Conway's Game of Life (or vice versa) [closed]
Can you find initial conditions for either Rule 110 or Conway's Game of Life to emulate the other? That is, produce output (in any form, not necessarily the familiar pixel grid) which corresponds ...
8
votes
3answers
764 views
CCC 2016: Circle of Life
Before I begin, this challenge was not mine originally
Credits to The University of Waterloo. This came from the Canadian Computing Competition 2016, Senior Problem 5. Here is a clickable link to the ...
7
votes
2answers
983 views
Create a universal two-dimensional cellular automaton cell using two-way universal logic processors
In Conway's Game of Life, a cell is in a state of either on or off, depending on the on-and-off state of the eight cells surrounding it.
We can simulate this using a logic gate network with some sort ...
5
votes
1answer
380 views
Conway's game of life [duplicate]
Description :
Given an array of strings representing a grid of cells
With the key :
0 = 'dead cell'
1 = 'live cell'
write a function that returns the next ...
5
votes
0answers
106 views
Shortest Wireworld [duplicate]
Wireworld is fun for the whole family! Your goal is to create a Wireworld implementation in the shortest amount of code possible.
A Wireworld cell can be in one of four different states, usually ...
