C/C++ Implementation of a One-Dimensional Cellular Automaton

This assignment requires the development of a one-dimensional cellular automaton using C, C++, or C#. The task involves researching the purpose and structure of cellular automata and then programming a 1-D CA that develops downwards on the screen. The solution should handle user input for rule numbers and automaton width, convert binary strings to arrays, wrap the ends of the array, and display generations in the terminal. The assignment emphasizes practical C programming skills in a Unix-like environment, focusing on array manipulation, rule set implementation (including binary conversion), and user interaction. Students are encouraged to start with rule set 30 and consider memory efficiency in their implementation. The final solution should include the conversion of binary strings into an array of variables, accept a rule number from the user and display the automaton for that rule, take the automaton's width and the number of generations to display from the user, wrap the ends of the array, and write the output to the terminal.

Your task is to:
• researching the purpose and structure of cellular automata
then to use the C or C++ or C# (VS 2013 only) programming language (under Linux or Windows)
to build:
• a one-dimensional cellular automaton i.e. one which develops in one direction on the screen,
(usually downwards)
You should undertake this assignment individually i.e. no collusion or
plagiarism is acceptable.
The pass mark for this resit coursework is 60%.
Introduction
Generally a cellular automaton is a regular grid of cells. Each cell can exist in one of a finite
number of states. The grid can be in any finite number of dimensions but we are only really
concerned with 1- (and possibly 2-) dimensional cellular automata. Time is considered to be
discrete rather than continuous. This means that the whole automaton exists in a single state at a
given time, e.g. at time t=1, and then according to the rules, the automaton changes to another state
at time t=2, and so on. The state of any given cell at time t is a function of the states of a finite
number of cells (called its neighbourhood) at time t-1. This means that the state of a given cell is
determined based upon the states of its neighbours in the immediate previous time step. These
neighbours are a selection of cells relative to the specified cell, and do not change (though the cell
itself may be in its neighbourhood, it is not usually considered a neighbour). Every cell has the
same rule for updating, based on the values in this neighbourhood. Each time the rules are applied
to the whole grid a new generation is created.
Background Reading
Wikipedia has a good introduction to CAs at:
http://en.wikipedia.org/wiki/Cellular_automata
Most popular science books on chaos theory will include a chapter or two on CAs. However a good
book is ”A New Kind of Science” by Stephen Wolfram (2000) which may be worth dipping into for
some added background - it is available online at:
http://www.wolframscience.com/
You can find out more about CAs at:
http://mathworld.wolfram.com/CellularAutomaton.html

Searching YouTube for cellular automata yields lots of movies and animations of cellular automata
in action, as well as some documentaries of scientists talking about their implications.
Finally, you should also consider getting a book on C programming from the University Library.
There are many to choose from and most introductory texts will be sufficient at this stage to provide
you with extra support whilst doing your development projects.
Requirements
Your task is to create a simple 1-dimensional (1-D) cellular automaton (CA) which will display
each generation of your automaton in the shell (as this exercise is to give you practice C
programming in a Unix-like environment, it should be performed using these tools in the lab, or
equivalent).
In a 1-D CA, each generation is just a single line. The values of the cells in each generation are
determined by applying the rules to the values of the cells in the previous generation. For example,
if we use rule set 30 (remembering that 30 = 00011110 in binary), gives:
Current pattern 111 110 101 100 011 010 001 000
New state for centre cell 0 0 0 1 1 1 1 0 ( =3010 )
then we should get output similar to the following (although yours does not actually have to look
exactly like this):
Getting Started
You should probably start with storage for two generations of cells: a parent generation and a child
(or current) generation. One way of implementing this storage is using arrays. Initially you will
seed the parent generation at time t=0, i.e. put the value 1 or 0 into each cell of the parent array.
You now need to work out what the child generation should contain given the contents of the
parent. You do this by applying the rules as discussed above, for example, if the parent cell and its
neighbours to either side contain the values 0, 1, 1, then the child cell should contain the value 1.
Once you have completed the child generation you can discard the parent, although you might want
to consider writing it to a file so that you can compare the output between different runs. At this
point the child generation becomes the new parent generation, and you should work out what the
next child generation should be. You might want to start with rule set 30, as shown above, for
specifying how the child generation is derived from the parent. Alternatively, you might want to put
together your own rule set (there are 256 possible different rule sets that you can generate from
various combinations of the 3 ancestor cells, and this is only for the most simple type of automata).

Before you do this you should decide how big you want the storage for each of your generations to
be, e.g. how many cells make up a generation? 10? 50? 100? Too few and you might have
insufficient space for interesting patterns to emerge, too large and you will not be able to fit much
of any given generation into your terminal window.
Rather than spending your time learning to do graphics in C/C++ (although this might be a good
extension once you have the basics working, because graphics give you more resolution for the
output) you should consider how you could indicate the different cells in the terminal, for example,
using a 1 to indicate black and a 0 (or even possibly a space) to indicate white. One other thing that
you will have to consider is how to store your automata data whilst you are working on it (e.g. the
previous generation and current generation). You might want to use an array of INTs to begin with,
so that each integer in the array is a cell in the automata, but there are much more efficient ways to
store the cells if you consider that each cell has only two states and is therefore very similar to a bit
(binary integer). You could store your data very efficiently as bit arrays but that would limit you to
only two states for your cells and thus your code would be limited to the very simplest automata.
Perhaps a happy medium might be to store each cell as a CHAR because a CHAR generally uses
about half as much memory as an INT? Perhaps however there is more data that you would like to
store with each cell and therefore some sort of simple STRUCT would be better?
Required Features
Your solution should include some or all of the following features:
• conversion of binary strings e.g. “101001010101” into an array of variables (binary or
integers) and back again
• be able to ask the user for any rule number (given in decimal) and convert this into binary
rules for that number, and hence display the automata for that rule
• be able to ask the user how wide the automaton is to be on the screen, and how many
generations are to be displayed
• wrap the ends of your automata array around so that the right-hand end continues onto the
left-hand end and vice-versa.
• write your automa