Ctrl+K

Level 1 - Elementary Cellular Automaton

32. Level 1 - Elementary Cellular Automaton#

32.1. Introduction#

In mathematics and computability theory, an elementary cellular automaton is a one-dimensional cellular automaton, i.e., a vector of evolving cells where each cell has two possible states (labeled False and True). The rule to determine the state of a cell in the next generation depends only on the current state of the cell and its two immediate neighbors.

There are \(8 = 2^3\) possible configurations for a cell and its two immediate neighbors. The rule defining the cellular automaton must specify the resulting state for each of these possibilities so there are \(256 = 2^{2^3}\) possible elementary cellular automata.

Here an example of evolution.

Evolving Automaton source

In this subject, you will develop a one-dimensional automaton. It will show us the ability you have to developp a programm using: functions, for loop, while loop, if statement, list and dictionary.

If you want more information on elementary cellular automaton:

32.2. Automata#

32.2.1. Creation#

Implement a function create_automaton(width) which initialize an automaton with a given width. The automaton is a list of cells. Each cell has a value of False except for the center cell which has a value of True.

def create_automaton(width):
    # TO COMPLETE

print(create_automaton(5)) # Expected [False, False, True, False, False]

32.2.2. Print#

Implement a function print_automaton(automaton) which prints a given automaton. The automaton is printed as a string where each cell is represented by a "▓" if the cell is True and a " " if the cell is False. For example : "[  ▓  ]" for the automaton [False, False, True, False, False].

def print_automata(automaton):
    # TO COMPLETE

print_automaton([False, False, True, False, False]) # Expected "[  ▓  ]"

32.3. Evolution#

32.3.1. Get Pattern#

Implement a function get_pattern(automaton, i) which takes as parameter an automaton and an index i. It returns a tuple of three cells. The three cells at index i and the cells around i. We consider a circular automata. If the cell i is at the beginning of the automaton, the first cell of the pattern is the last cell of the automaton. If the cell i is at the end of the automaton, the last cell of the pattern is the first cell of the automaton.

def get_pattern(automaton, i):
    # TO COMPLETE

print(get_pattern([False, True, False, False, True], 2)) # Expected (True, False, False)
print(get_pattern([False, True, False, False, True], 4)) # Expected (False, True, False)
print(get_pattern([False, True, False, False, True], 0)) # Expected (True, False, True)

32.3.2. Evolution#

Implement a function evolve(pattern, rule) taking two parameters. The first one, pattern is a tuple representing a cell and its neighbors. The second one, rule is a dictionnary associating a pattern with a boolean. The function returns the new state of a cell given a pattern. If pattern is not in the rule dictionnary, the default new state is False.

def evolve(pattern, rule):
    # TO COMPLETE

print(evolve((True, True, False), {(True, True, False): True})) # Expected True
print(evolve((True, True, True), {(True, True, False): True})) # Expected False

32.3.3. Next Gen#

Implement a function next_generation(automaton, rule) which takes to paramters. The first one is an automaton. The second one is a dictionnary, the rule of evolution. This function return a new automaton containing the state after the evolution of each cells.

def next_generation(automaton, rules):
    # TO COMPLETE

print(next_generation([False, False, True, False, False], {(False, False, True): True}))
# Expected [False, True, False, False, False]
print(next_generation([True, False, False, False, False], {(False, False, True): True})) 
# Expected [False, False, False, False, True]

32.4. Main#

Implement a main function which create an automaton of width 30 and iterate over an infinite loop. In the loop the automata is printed, then the next generation automata is created and the programm is paused for a few moment.

Try your main function using the Rule 90.

rule90 = {
    (True, True, False): True,
    (True, False, False): True,
    (False, True, True): True,
    (False, False, True): True,
    }

The expected result is a fractal.

[               ▓              ]
[              ▓ ▓             ]
[             ▓   ▓            ]
[            ▓ ▓ ▓ ▓           ]
[           ▓       ▓          ]
[          ▓ ▓     ▓ ▓         ]
[         ▓   ▓   ▓   ▓        ]
[        ▓ ▓ ▓ ▓ ▓ ▓ ▓ ▓       ]
[       ▓               ▓      ]
[      ▓ ▓             ▓ ▓     ]
[     ▓   ▓           ▓   ▓    ]
[    ▓ ▓ ▓ ▓         ▓ ▓ ▓ ▓   ]
[   ▓       ▓       ▓       ▓  ]
[  ▓ ▓     ▓ ▓     ▓ ▓     ▓ ▓ ]
[ ▓   ▓   ▓   ▓   ▓   ▓   ▓   ▓]

32.5. Advanced Features#

You are now free to complete the project with any extension that you may imagine. This is an opportunity to show that you are now confident and can propose and develop new leads independently.

Here, an example of extension: how to detect a loop? The automaton is deterministic, thus if the automaton reach a state that he already reached, then we can stop the programm, we are in a loop, we can stop the automaton.

Contents