Questions tagged [cellular-automata]

Puzzles involving cellular automata, such as Conway's Game of Life.

Filter by
Sorted by
Tagged with
13
votes
6answers
752 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 ...
58
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....
11
votes
2answers
333 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 ...
5
votes
1answer
349 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 ...
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 ...
15
votes
4answers
717 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 ...
11
votes
9answers
762 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 ...
10
votes
4answers
668 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 ...
8
votes
3answers
757 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 ...
12
votes
6answers
529 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 ...
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 ...
9
votes
2answers
453 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 ...
10
votes
0answers
716 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. ...
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 ...
59
votes
13answers
4k 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 ...
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 ...
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 ...
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. ...
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 ...
31
votes
4answers
684 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 ...
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 ...
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 ...
14
votes
7answers
617 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 ...
5
votes
0answers
105 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 ...
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
0answers
763 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 ...
7
votes
2answers
958 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 ...
114
votes
16answers
14k 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 ...
27
votes
17answers
5k 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 ...
983
votes
6answers
206k 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 ...
26
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 ...
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), ...
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 ...
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 ...
57
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 ...
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 ...