Design Activity: Cellular Automata Simulation

A Simple Design Method #

Most interesting problems reward careful thought before we start coding.

A few questions to consider:

1. What data (entities, state, input parameters) do we need to represent?
2. What operations do we need to perform on those data?
3. How might we represent those data to support those operations?
4. How do we arrange those operations to find a solution?
5. What output or interface do we need to support?
6. What are the objectives, constraints, and environment under which we are working?
7. How might we need/want to generalize or modify the problem and how do our answers to these questions change when we do?

Aphorism of the day: Make it run, make it right, make it fast – in that order

Cellular Automata #

A cellular automaton is a discrete model of computation that can exhibit complex structure from simple rules. The consist of a regular lattice of cells each in one of a finite number of states. The states of the cells evolve according to simple rules.

A famous example is Conway’s Game of Life.

1. The automaton evolves on a rectangular grid.
2. Each cell has two states, on or off.
3. The next state of a cell is determined by how many living neighbors it has, where the neighborhood contains the eight cells surrounding the cell.
4. A live cell with
   • Fewer than 2 live neighbors, dies (underpopulation)
   • More than 3 live neighbors, dies (overpopulation)
   • 2-3 live neighbors, survives.
5. A dead cell with exactly three live neighbors is born (reproduction)

This rule set is sometimes denoted B3/S23. This is called an outer totalistic rule set because the next generation at a cell depends only on (a) the state at that cell, and (b) the total value of the cell’s neighbors.

Some online simulations:

• conwaylife.com
• GollyOnline

Our Task #

Simulate the game of life. We will focus on computing the state at a given time and outputing that state, rather than simulating the system dynamically and graphically.

Design Discussion #

Let’s try to answer the seven questions.

What data (entities, state, input parameters) do we need to represent? #

What operations do we need to perform on those data? #

How might we represent those data to support those operations? #

How do we arrange those operations to find a solution? #

What output or interface do we need to support? #

What are the objectives, constraints, and environment under which we are working? #

How might we need/want to generalize or modify the problem and how do our answers to these questions change when we do? #

Pair Programming Task #

Ultimate goal is to write a script automaton that simulates the Game of Life (and perhaps other automata) for a fixed amount of time. The script should:

1. Accept an initial state as input
2. Produce an output format to show the requested state
3. Support our standard --help and --version options
4. Have an option for producing output in the same format as the program’s input
5. Options for variations?

Today we will on the core computations. Split into common language pairs (generally).

1. Devise a representation of the state
2. Write a function that updates the state by one (or more if desired) steps
3. Write (critical) or stub (generic) support functions

Layout some tests that your main function should satisfy.

Debrief #