Due. In lecture on Thursday, October 12, 2000. You may turn it in to a
consultant before that date in the consulting room in Carpenter. Do not turn it
in at Carpenter on the due date. Programs will not be accepted late.
Note. Always
write your name, Cornell ID#, and the day/time/instructor for your section in
the first comment of any program you hand in for credit; otherwise it will not
be graded. This cannot be written in
by hand. If you wrote the program with a partner, turn in only one printout with your partner's name
and ID# in the comment, as well as your own. The comment must also include the
section day/time/instructor for partner; the program will be returned to the
first person listed. Sign your name(s) by the comment. Please staple the pages
of your assignment together.
Grading. This assignment will be given two grades: the
first based on correctness, the second on program organization and style. Each
grade will be a 0, 4, or 5. Not only should your program work, but it should
contain adequate comments to guide the reader who is interested in
understanding it. The declaration of every significant variable should include
a comment describing that variable. There should be appropriate comments in the
code so the reader can see the structure of the program, but not so many that
the program text is hard to read.
Goals. To give you experience using one-dimensional
arrays and the passing of arrays to methods and objects. This assignment also
provides a further exercise in using classes and methods to structure your
program and data. And, again, we will demonstrate the ease with which one can
create interesting graphics output in Java.
Write a program that simulates the operation of a so-called one-dimensional
cellular automaton. A 1D cellular automaton (CA) consists of a series of
cells. Each cell can be in two or more different states. Based on the
current state and the neighboring states of a cell, a cell changes state over
time in according to a pre-defined set of rules. Your program will simulate the evolution over time of a 1D
cellular automaton.
The notion of a cellular automaton is best illustrated with a concrete example. We consider a 9 cell one-dimensional cellular automaton. We assume each cell can have two values (0 or 1). So, the complete state of this CA is given by a sequence of 9 0’s and 1’s. For example,
cell value [0 0 1 0 1
1 0 0 1]
cell
# 0 1
2 3 4 5 6
7 8
We have written the number of each cell below each cell value. Given the state of a cellular automaton at time T the state at time T + 1 is given by updating the cell values using a fixed set of rules. These rules take into account the current value of a cell and its immediate neighbors. For example, a rule of the form
0
0 1 è 1
(rule I)
can be used to update the value of a cell. To
apply the rule, the left hand side of the rule has to be satisfied. The left
hand side of rule I is satisfied for a given cell k iff the left
neighbor of k has value 0, the
cell k itself has value 0, and the right neighbor of the cell has value
1. After application of the rule, the value of cell k will change to 1.
So, in the example CA state above, rule I applies at cell 1 and at cell 7. We
can graphically illustrate the update of these cells by giving their new cell
values on a new row, i.e.,
[0 0 1 0 1 1
0 0 1] (Time = T)
[0 1 1 0
1 1 0 1 1] (Time = T + 1)
In general, we have a complete set of rules that define a potential state change for all possible combinations of values for a cell and its neighbors. When we look only at the direct neighbors of a cell, we need a total of eight rules. An example set of rules is:
0) 0 0 0
è 0
1) 0 0 1
è 1
2) 0 1 0
è 0
3) 0 1 1
è 1 (Rule set A.)
4) 1 0 0
è 1
5) 1 0 1
è 0
6) 1 1 0
è 1
7) 1 1 1
è 0
For ease of reference, we have numbered these eight rules from 0 to 7.
Note that the left hand sides of the rules correspond to the binary
representation of the numerals 0 to 7. To convert a three bit binary number x
y z use the formula x * 2^2 + y * 2 + z. For example,
the binary number 1 1 0 evaluates to 1 * 2^2 + 1 * 2 + 0 = 6, i.e., the #6 rule
above. We will make use of this fact later on in our program. Also note that
rule I from above is part of this rule set (see rule #1). However, this is
accidental. We could just as easily have included 0 0 1
è 0 as rule # 1.
If we now apply rule set A to the CA state above
we get:
[0 0 1 0
1 1 0 0 1]
(Time = T)
[1 1 0 0
1 1 1 1 0]
(Time = T + 1)
cell
# 0 1 2 3
4 5 6 7 8
For example, at time T, cell 2 has value 1 and
its left neighbor has value 0 and its right neighbor has value 0. So, we should
look for a rule with left-hand-side 0 1 0. This is rule #2, and cell 2 gets
value 0 after the update. You should verify for yourself that the other cells
indeed get the values as given above. To update the cell 0 and 8, we assume
that the array of cells “wraps around”, so that cell 8 neighbors cell 0. More
concretely, to update cell 0, we look for the left neighbor to cell 8, and to
update cell 8 we look for its right neighbor at cell 0.
A good way to think of the problem of computing
the next state is by imagining a sliding window of 3 cells that moves from left
to right, updating the middle cell in this window according to a matching rule
and writing its new value on the line below.
It should be clear that different rule sets will
result in different updates to the current state. The properties of a rule set
become particularly interesting when one considers a long sequence of state
updates. In effect, we will watch the “evolution” of the state of the automaton
over a long series of time steps. Rule sets that have more 1’s than 0’s on the
right hand side will lead over time to CA states with a majority of 1’s. While
rule sets with a majority of the rules leading to 0, will tend to lead over
time to lots of 0 values in the cells. The behavior of rule sets with an equal
number of 0’s and 1’s on the right hand side is more difficult to predict. In
fact, certain such rule sets are conjectured to lead to a kind of “chaotic”
behavior. We now return to the program.
Your program should contain a class called “CA”, for cellular automaton. This class should contain the representatation of the state of the automaton. The natural way to represent the automaton is by a one dimensional array. You will need one array for the current state and one array to store (temporarily) the next state. The CA class should contain a method (“updateState”) that operates on the current state to obtain the next state using a given rule set. After computing the next state in the next state array, you should update the current state array so that it contains the values of the next state array. This way the current state array always contains the last computed update. (Think of a way of getting the current state array reference to point to the array with values of the next state array, without doing a cell by cell copy of the arrays. Remember that an array variable contains a reference to an array object.)
The CA class should also contain a method for printing out the current state of the automaton. A natural way to print out the state is as a sequence of 0’s and 1’s.
The main method of your program should be in a separate class, called “CAProgram”. This class takes various inputs from the user. The inputs are best illustrated with a trace of an example run. We give the user input in bold.
Enter length: 9
Enter number of output lines: 10
Enter eight 0/1 values for rules or -1 for random rules:
0 1 0 1 1
0 1 0
Rules are: 0 1 0 1 1 0 1 0
Initial state? (0 --- fixed middle; 1 --- random): 0
0 0 0 0 1 0 0 0 0
0 0 0 1 0 1 0 0 0
0 0 1 0 0 0 1 0 0
0 1 0 1 0 1 0 1 0
1 0 0 0 0 0 0 0 1
1 1 0 0 0 0 0 1 1
0 1 1 0 0 0 1 1 0
1 1 1 1 0 1 1 1 1
0 0 0 1 0 1 0 0 0
0 0 1 0 0 0 1 0 0
Do you want to simulate another CA? (yes / no): no
So, the program first asks for the length of the cellular automaton (i.e., number of cells). Then it asks for the number of output lines (i.e., the number of complete states of the CA) that should be computed and printed out. The program subsequently asks for the rule set to be used for the state update. The rule set can be specified by eight 0/1 values, which correspond to the right hand sides of the rules (see e.g., rule set A). The user can specify these values by hand or by entering “-1”, in which case the program will generate a random sequence of eight 0’s and 1’s (for each choice, 50% chance of a 0 and 50% chance of a 1). The user then needs to specify the initial state of the cellular automaton. There are two options. An input of “0” should give an initial state with the middle cell set to “1” and all other cells to “0”. (It’s fine to round up or down to pick a “middle” cell, if needed.) The “1” options should give a random 0/1 initial assignment for each cell. How to use a random number generator in Java is discussed on pages 81 through 83 of the Lewis and Loftus book. Use "% 2" to get 0/1 values. Don't forget to import java.util.Random.
The program will then output the evolution of the cellular automaton for 9 time steps (including the initial state, this gives us 10 lines of output total), after which the user is asked whether he/she wants to try a new automaton.
To represent the rule set, you should again use a one dimensional array, call it rules. This array should have eight entries, each entry gives the right hand side of one of the eight possible rules. As we discussed with rule set A), there is a natural numbering of the rules, where the number of the rule is given by the binary number on the right hand side of the rule. So, for example, the rule
1 0 1 è x ( x is 0 or 1)
can be represented in the rules array at location 5, i.e., rules[5] = x. In your CA class, you should create a method that can take three 0/1 values and convert it to an integer value, to be used for accessing the rules array. Also, when calling the updateState method, you should pass the rules array reference as an argument.
This concludes the basic setup of the program. You should first make sure that this text-based version of your program works correctly. Check this by carefully checking some of the CA evolutions your program produces. If everything works correctly, it’s time for the fun part: fancy graphics output.
Note, as with your other programming assignments, you should use the CUCS Java Application Stationery.
Much of the interest in one dimensional cellular
automata comes from the intriguing patterns such automata can produce. You will
now adapt our program to allow for graphics output. The process is very similar
to what you did for the graphics part in programming assignment #2. Again, Java
provides an excellent platform for quickly adding graphics output.
We now outline the basic steps. See the writeup
of assignment #2, if you need further detail. We use again a class to draw the
graphics frame, we will call it CAFrame:
This class defines the method CAFrame that your program should use to draw the basic graphics window:
import
java.awt.*;
// Class CAFrame creates a graphic frame for drawing
class CAFrame extends
Frame
{
CAFrame ( )
{
super("Frame");
setSize(300, 600);
show();
}
}
To use this class, you need to again instantiate
the graphics frame:
//
Initialize graphics context
CAFrame gui
= new CAFrame();
Graphics easel = gui.getGraphics();
int stretch;
Note that you need to import java.awt.*. We again use a “stretch”. You
should read in its value for each CA simulation. With stretch = 1, we will
paint one pixel per cell, but, in general, with stretch set to s, we
will paint each cell using an s by s filled square. Many
simulations look best when using stretch = 1. However, sometimes larger cells
display the overall behavior better. Note that with stretch = 1, you can
simulate a 300 cell CA for 600 lines on the canvas. With stretch = 5, you can
simulate a 60 cell CA for 100 lines.
To draw the cells, we use again the GraphicsUtil class
you downloaded for assignment #2. To draw
the cell i in the row j, you can use:
GraphicsUtil.fillRect(easel,
i * stretch
, j * stretch, stretch, stretch,
Color.blue);
This will draw a blue cell. Use blue to represent a 0 value, and red to represent
a 1 value.
A correct program does what the problem statement
requires for any input data permitted, not just the input data given as an
example in the handout. So you should experiment with different data sets to
debug your program.
If your program does not produce the expected
output when you first run it, you may find it helpful to temporarily insert
extra output statements in key locations of the program to help you understand
what is happening.
Note that when running your program, you should make sure that your text
input window does not overlap with your graphics window.
A) Run program with rule set A on an automaton of length
21 for 25 lines. As an initial state, have a single cell with a “1” in the
middle. Hand in a printout of the java code and the textual output.
B) Run the program with rule set A on an
automaton of length 300 for 600 lines with stretch set to 1. Do this for two
different initial states: one random one, and one with a single “1” in the
middle. Hand in screen snapshots of
the graphics output.
Instructions for taking screen snapshots are
given in section 1.4.5 of the Guide to
CodeWarrior Java for CS100 and CS211.
C) Experiment with several other possible rule sets and hand in a snapshot of two interesting patterns you encountered. Write down (by hand) on each snapshot the rule set that led to that pattern.
Please remember to
staple all material together.
In this assignment, we have limited ourselves to
so-called binary valued automata. Of course, we can easily generalize our
approach to produce CA’s where the cells have a range of possible values. The
rule set would become larger, e.g., a 3-valued CA with nearest neighbor rules
would need 27 = 3^3 different rules to capture all possible patterns that can
occur in three cells. In our graphics output, we then use a third color and can
get some very interesting graphics. Also, instead of just looking at the
immediate neighbors of a cell, one can look at the nearest two neighbors on
each side. Again, this gives more complex rule sets and more complex patterns.
Finally, one can move from one dimensional automata to two or higher
dimensional automata. In a two dimensional CA, the cells are placed in a 2D
grid. Again, the updates are based on looking at a cell and its neighbors. In
2D, we cannot easily print the next state below the current state, instead one
simply overrides the current state on the screen. This leads to the fascinating
and well-known “game of life”. It can be shown that such 2D automata can
simulate any possible computational process. Your code handles the basic 1D
case, but adding in these various possible extensions should be quite doable.