Challenge - Linear Cellular Automata

Challenge – Linear Cellular Automata

Do you like solving puzzles as much as myself and my Demcon colleagues?
Then I got a challenge for you: can you solve Linear Cellular Automata? Read the full challenge below.
Did we scare you because of the long text? No worries, it should not take much more than one hour to solve.

I wish you good luck.
Pieter Bijleveld
#decodedemcon

< ALL CHALLENGES

THE CHALLENGE

For this exercise, you are tasked with creating a linear cellular automaton*. A cellular automaton consists of a grid of cells, with each row being called a generation. Each cell is in a certain state, which is ‘occupied’ or ‘empty’ in this case. The content of each subsequent generation is changed from the previous generation according to a few simple rules.

The rules for computing a new generation satisfy four requirements:

The rules use only the current generation to compute the next one.
The rules define one state value per cell.
The rules are the same for each cell.
The rules define the new state value based on the state values in a set of cells in fixed positions with respect to the cell the value is computed for; such a set is often referred to as the neighborhood of the cell.

This exercise concerns linear cellular automata, i.e., automata with a one-dimensional array of cells as grid. The neighborhood of a cell consists of the immediate neighbors in the array and the cell itself. Again, there are only two different states, referred to as ‘occupied’ and ‘empty’ (i.e., not occupied). In the book “A new kind of science” by Stephen Wolfram, the creator of the Mathematica tool, shows that such simple automata can display very interesting behavior. This exercise will show the effect of some rules.

The following three types of automaton are considered:
– An automaton of type A has the following fixed rule set
1. If a cell is currently occupied, it remains occupied only if exactly one neighbor is occupied.
2. If a cell is currently empty, it remains empty only if both neighbors are empty.

– An automaton of type B has the following fixed rule set
1. If a cell is currently occupied, it remains occupied only if the right neighbor is empty.
2. If a cell is currently empty, it becomes occupied if exactly one neighbor is occupied.

– For an automaton of type U (called a universal automaton) the rule set is defined by a table of the following form
(where boolean values true and false are used to indicate the occupied and empty state, respectively):
where b0, b1, …, b7 are boolean values. (NB Obviously the rule sets for automata of type A and B can also be defined in this way).

exercise definition

You are asked to develop a program that reads the description of an automaton (including initial configuration) from standard input, and then computes and displays a specified number of generations. The input is specified as follows (all items mentioned are separated by white space):

1. The letter A, B, or U indicating the type of automaton to be executed.
2. A positive integer L being the number of cells of the automaton.
3. A positive integer G being the number of generations to be computed and displayed (including the initial configuration).
4. The word init_start, followed by one or more positive integers, followed by the word init_end. The integers are the positions of the occupied cells in the initial configuration (the first cell in the grid has position 1). All other cells are empty in the initial configuration. When an integer is higher than the number of cells L it should be ignored.
5. In case of automaton type U (universal automaton) 8 0’s and 1’s representing the Boolean values b0, b1, …, b7 mentioned in the description of the rule set for a universal automaton above (0 representing false, 1 representing true).

The output should be a sequence of G rows representing the successive generations. The first row is the initial generation. Each row consists of L characters each representing the state of one cell. An empty cell is displayed as a space, an occupied cell as the character *. Each row is terminated with an end-of-line.
Input and corresponding output are illustrated in the following two examples: see image.

SPECIFICS & RULES

Please write your solution in one of the following programming languages: Python, Matlab, C++. We will evaluate your solutions based on inventiveness, efficiency and good coding practices. We will only accept submissions in the form of a link to a Github project. We’ve added some instructions if you’re unfamiliar with Github. In order to help you along a bit, and to help us with evaluating everyone uniformly, we’ve written a print function for you to use. You can find it here: Decode Demcon GitHub

This challenge has ended, but you can still send in your answer to communication@demcon.com.

HOW TO USE GITHUB

In your internet browser, navigate to github.com
Enter your email address, and press ‘sign up for GitHub’
Press continue, create a password and enter a username
Solve the puzzle to show that you are a human
Verify your email address and customize your Github experience
Create a new project by pressing ‘start a project’
Give your repository a name, and make sure it is set to public. Press ‘create repository’
In quick startup, press ‘create new file’ or ‘upload existing file’
Enter the code for this challenge here.
When you are ready to submit, go to the <>code section of your repository and press ‘code’ and copy the HTTPS link. Enter this link into your submission.

* Challenge created by Pieter Bijleveld, Stefan Heijmans and Jeroen Verberne.

< All challenges