Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit327e18f

Browse files
authored
Elementary cellular automata (TheAlgorithms#1302)
* feat: Added Elementary Cellular Automata Algorithm w/ explanation, examples, and further reading* test: Added tests for Elementary Cellular Automata Algorithm* chore: add Wikipedia link to Elementary Cellular Automata Algorithm* Used | Bitwise OR and ^= (Bitwise XOR) operators in calculating next Elementary Generation over Addition + and Subtraction -=
1 parentfc06690 commit327e18f

File tree

2 files changed

+198
-0
lines changed

2 files changed

+198
-0
lines changed

‎Cellular-Automata/Elementary.js

Lines changed: 105 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,105 @@
1+
/**
2+
* Author: Jacoby Johnson (cobyj33)
3+
*
4+
* Generates generations of Elementary 1D cellular automata
5+
*
6+
* Wikipedia: https://en.wikipedia.org/wiki/Elementary_cellular_automaton
7+
* See all 255 possible rules and find another explanation here: https://mathworld.wolfram.com/ElementaryCellularAutomaton.html
8+
*
9+
* My personal take on the explanation of Elementary Cellular Automata:
10+
*
11+
* Elementary 1D cellular automata defines the growth and decay of populations of "cells" according to a specific rule, where the population is a line (array) and each cell is in either an "alive" (1) or a "dead" (0) state.
12+
*
13+
* The next generation of for a cell in the simulation ONLY depends on the state of its neighborhood (the state of the cell itself as well as the states of the cells to the immediate right and the immediate left)
14+
* Therefore, since each neighborhood consists of 3 cells each with 2 states there are 2^3 possibilities that determine a cell's next state, where each possible neighborhood could be represented in binary as
15+
*
16+
* 111
17+
* 110
18+
* 101
19+
* 100
20+
* 011
21+
* 010
22+
* 001
23+
* 000
24+
*
25+
* Where "1" represents the cell being alive and "0" represents the cell being dead. The leftmost bit represents the left neighbor of the currently analyzed cell, the middle bit represents the currently analyzed cell, and the rightmost bit represents the right neighbor of the currently analyzed cell.
26+
*
27+
* Rules are represented between 0 and 255 (0 and 255 inclusive), or more conceptually is seen as an 8 bit binary number. Each bit represents whether a cell should survive according to one of the 8 states of a cell's neighborhood. In this way, the number can act like an array of data of length 8.
28+
* The most significant bit (ex: ->10100100 ) represents the output for the "all on" state while the least significant bit (ex: 10100100<- ) represents the output for the "all off" state
29+
* In other words, all of the 8 possible neighborhood configurations map toward the 8 bits in a rule's output values
30+
*
31+
* Therefore, to find whether the a cell is born, survives, or dies, one could convert the state of a cell and it's neighbors into a binary number, then use the numerical value of that binary number as an index to find the corresponding rule's output, which is what has been implemented below
32+
* This analysis of a cell's neighborhood is performed on each cell in a generation until a new generation is created and returned.
33+
*
34+
* Rules are usually demonstrated visually by how a single cell grows independently according to that rule
35+
*
36+
* Example: First generations of Rule 94 First Generations of Rule 126
37+
* 000000000000000000000000001000000000000000000000000 000000000000000000000000001000000000000000000000000
38+
* 000000000000000000000000011100000000000000000000000 000000000000000000000000011100000000000000000000000
39+
* 000000000000000000000000110110000000000000000000000 000000000000000000000000110110000000000000000000000
40+
* 000000000000000000000001110111000000000000000000000 000000000000000000000001111111000000000000000000000
41+
* 000000000000000000000011010101100000000000000000000 000000000000000000000011000001100000000000000000000
42+
* 000000000000000000000111010101110000000000000000000 000000000000000000000111100011110000000000000000000
43+
* 000000000000000000001101010101011000000000000000000 000000000000000000001100110110011000000000000000000
44+
* 000000000000000000011101010101011100000000000000000 000000000000000000011111111111111100000000000000000
45+
* 000000000000000000110101010101010110000000000000000 000000000000000000110000000000000110000000000000000
46+
* 000000000000000001110101010101010111000000000000000 000000000000000001111000000000001111000000000000000
47+
* 000000000000000011010101010101010101100000000000000 000000000000000011001100000000011001100000000000000
48+
* 000000000000000111010101010101010101110000000000000 000000000000000111111110000000111111110000000000000
49+
* 000000000000001101010101010101010101011000000000000 000000000000001100000011000001100000011000000000000
50+
* 000000000000011101010101010101010101011100000000000 000000000000011110000111100011110000111100000000000
51+
* 000000000000110101010101010101010101010110000000000 000000000000110011001100110110011001100110000000000
52+
* 000000000001110101010101010101010101010111000000000 000000000001111111111111111111111111111111000000000
53+
* 000000000011010101010101010101010101010101100000000 000000000011000000000000000000000000000001100000000
54+
* 000000000111010101010101010101010101010101110000000 000000000111100000000000000000000000000011110000000
55+
* 000000001101010101010101010101010101010101011000000 000000001100110000000000000000000000000110011000000
56+
* 000000011101010101010101010101010101010101011100000 000000011111111000000000000000000000001111111100000
57+
*
58+
* DEV NOTE: This implementation assumes that cells on the edge (who only have 1 neighbor) have 1 neighbor and a permanently "dead" neighbor, which is technically correct in a finite space. However, most diagrams of these elementary cellular automata rules assume a infinite line of cells. Therefore, the edges of the array may not evolve perfectly in line with pictured diagrams which assume infinite space.
59+
*/
60+
61+
/**
62+
* Find the next Elementary Cell Automata Generation given the previous generation and the rule [0-255] to follow
63+
*@param {(0 | 1)[]} generation The current generation of the Elementary Cellular Automata simulation
64+
*@param {number} rule The current rule of the Elementary Cellular Automata simulation. Must be an integer between 0 and 255 inclusive
65+
*@returns {(0 | 1)[]} The next generation according to the inputted rule
66+
*/
67+
exportfunctiongetNextElementaryGeneration(generation,rule){
68+
constNUM_ELEMENTARY_NEIGHBORHOOD_STATES=8
69+
constMIN_RULE=0
70+
constMAX_RULE=255
71+
72+
if(!Number.isInteger(rule)){
73+
thrownewError(`Rule must be an integer between the values 0 and 255 (got${rule})`)
74+
}
75+
if(rule<MIN_RULE||rule>MAX_RULE){
76+
thrownewRangeError(`Rule must be an integer between the values 0 and 255 (got${rule})`)
77+
}
78+
79+
constbinaryRule=rule.toString(2).padStart(NUM_ELEMENTARY_NEIGHBORHOOD_STATES,'0')
80+
construleData=binaryRule.split('').map(bit=>Number.parseInt(bit))// note that ruleData[0] represents "all alive" while ruleData[7] represents "all dead"
81+
constoutput=newArray(generation.length)
82+
constLEFT_DEAD=4// 100 in binary
83+
constMIDDLE_DEAD=2// 010 in binary
84+
constRIGHT_DEAD=1// 001 in binary
85+
86+
for(leti=0;i<generation.length;i++){
87+
letneighborhoodValue=LEFT_DEAD|MIDDLE_DEAD|RIGHT_DEAD
88+
89+
if(i-1>0&&generation[i-1]===1){
90+
neighborhoodValue^=LEFT_DEAD
91+
}
92+
93+
if(generation[i]===1){
94+
neighborhoodValue^=MIDDLE_DEAD
95+
}
96+
97+
if(i+1<generation.length&&generation[i+1]===1){
98+
neighborhoodValue^=RIGHT_DEAD
99+
}
100+
101+
output[i]=ruleData[neighborhoodValue]
102+
}
103+
104+
returnoutput
105+
}
Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
import{getNextElementaryGeneration}from'../Elementary'
2+
3+
describe('Elementary Cellular Automata',()=>{
4+
describe('Rule Errors',()=>{
5+
it('Correct',()=>{
6+
expect(()=>getNextElementaryGeneration([0,0,0,0,0,1,0,0,0,0,0],128)).not.toThrow()
7+
})
8+
9+
it('Less than 0',()=>{
10+
expect(()=>getNextElementaryGeneration([0,0,0,0,0,1,0,0,0,0,0],-1)).toThrow()
11+
})
12+
13+
it('Greater than 255',()=>{
14+
expect(()=>getNextElementaryGeneration([0,0,0,0,0,1,0,0,0,0,0],256)).toThrow()
15+
})
16+
17+
it('Decimal',()=>{
18+
expect(()=>getNextElementaryGeneration([0,0,0,0,0,1,0,0,0,0,0],100.4)).toThrow()
19+
})
20+
})
21+
22+
describe('Rule 54 Iterations',()=>{
23+
it('Generation 1',()=>{
24+
expect(getNextElementaryGeneration([0,0,0,0,0,1,0,0,0,0,0],54)).toEqual([0,0,0,0,1,1,1,0,0,0,0])
25+
})
26+
it('Generation 2',()=>{
27+
expect(getNextElementaryGeneration([0,0,0,0,1,1,1,0,0,0,0],54)).toEqual([0,0,0,1,0,0,0,1,0,0,0])
28+
})
29+
it('Generation 3',()=>{
30+
expect(getNextElementaryGeneration([0,0,0,1,0,0,0,1,0,0,0],54)).toEqual([0,0,1,1,1,0,1,1,1,0,0])
31+
})
32+
it('Generation 4',()=>{
33+
expect(getNextElementaryGeneration([0,0,1,1,1,0,1,1,1,0,0],54)).toEqual([0,1,0,0,0,1,0,0,0,1,0])
34+
})
35+
})
36+
37+
describe('Rule 222 Iterations',()=>{
38+
it('Generation 1',()=>{
39+
expect(getNextElementaryGeneration([0,0,0,0,0,1,0,0,0,0,0],222)).toEqual([0,0,0,0,1,1,1,0,0,0,0])
40+
})
41+
it('Generation 2',()=>{
42+
expect(getNextElementaryGeneration([0,0,0,0,1,1,1,0,0,0,0],222)).toEqual([0,0,0,1,1,1,1,1,0,0,0])
43+
})
44+
it('Generation 3',()=>{
45+
expect(getNextElementaryGeneration([0,0,0,1,1,1,1,1,0,0,0],222)).toEqual([0,0,1,1,1,1,1,1,1,0,0])
46+
})
47+
it('Generation 4',()=>{
48+
expect(getNextElementaryGeneration([0,0,1,1,1,1,1,1,1,0,0],222)).toEqual([0,1,1,1,1,1,1,1,1,1,0])
49+
})
50+
})
51+
52+
describe('Rule 60 Iterations',()=>{
53+
it('Generation 1',()=>{
54+
expect(getNextElementaryGeneration([0,0,0,0,0,1,0,0,0,0,0],60)).toEqual([0,0,0,0,0,1,1,0,0,0,0])
55+
})
56+
it('Generation 2',()=>{
57+
expect(getNextElementaryGeneration([0,0,0,0,0,1,1,0,0,0,0],60)).toEqual([0,0,0,0,0,1,0,1,0,0,0])
58+
})
59+
it('Generation 3',()=>{
60+
expect(getNextElementaryGeneration([0,0,0,0,0,1,0,1,0,0,0],60)).toEqual([0,0,0,0,0,1,1,1,1,0,0])
61+
})
62+
it('Generation 4',()=>{
63+
expect(getNextElementaryGeneration([0,0,0,0,0,1,1,1,1,0,0],60)).toEqual([0,0,0,0,0,1,0,0,0,1,0])
64+
})
65+
})
66+
67+
describe('Rule 90 Iterations',()=>{
68+
it('Generation 1',()=>{
69+
expect(getNextElementaryGeneration([0,0,0,0,0,1,0,0,0,0,0],90)).toEqual([0,0,0,0,1,0,1,0,0,0,0])
70+
})
71+
it('Generation 2',()=>{
72+
expect(getNextElementaryGeneration([0,0,0,0,1,0,1,0,0,0,0],90)).toEqual([0,0,0,1,0,0,0,1,0,0,0])
73+
})
74+
it('Generation 3',()=>{
75+
expect(getNextElementaryGeneration([0,0,0,1,0,0,0,1,0,0,0],90)).toEqual([0,0,1,0,1,0,1,0,1,0,0])
76+
})
77+
it('Generation 4',()=>{
78+
expect(getNextElementaryGeneration([0,0,1,0,1,0,1,0,1,0,0],90)).toEqual([0,1,0,0,0,0,0,0,0,1,0])
79+
})
80+
})
81+
82+
describe('Rule 30 Iterations',()=>{
83+
it('Generation 1',()=>{
84+
expect(getNextElementaryGeneration([0,0,0,0,0,1,0,0,0,0,0],30)).toEqual([0,0,0,0,1,1,1,0,0,0,0])
85+
})
86+
it('Generation 2',()=>{
87+
expect(getNextElementaryGeneration([0,0,0,0,1,1,1,0,0,0,0],30)).toEqual([0,0,0,1,1,0,0,1,0,0,0])
88+
})
89+
it('Generation 3',()=>{
90+
expect(getNextElementaryGeneration([0,0,0,1,1,0,0,1,0,0,0],30)).toEqual([0,0,1,1,0,1,1,1,1,0,0])
91+
})
92+
})
93+
})

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp