Section 6 - Implementing M. Mitchell Rules

3A.6.1 The Plan

You have to always think in terms of objects when you start a project like this.  What will the objects be?  In CA, a natural answer is that there should be two classes:

  1. A Rule class, which encapsulates all the information of a rule.
  2. An Automaton class, which accepts a rule in its constructor, and has methods that compute and display new generations as a result of repeatedly applying the rule.
We could also pass a seed to the Automaton constructor, but to keep things manageable for this lecture and assignment, we'll always assume the seed is always a single 1, swimming in an infinite sea of 0s, i.e., ...0000000000001000000000000... .

There is a lot of leeway here.  For example, should our Automaton class print out only one generation and allow the client to decide how to display the results of many generations, or should the class display all the generations (up to some value) by itself with no client intervention?  Also, the Rule class might not be necessary if rules are really simple.  For example, using M. Mitchell's encoding scheme from the last section, a rule is nothing more than a number.  There is hardly a need for a separate class in that case.

With this in mind, I will create an Automaton class that only provides a propagateNextGeneration() method (to compute the next gen based on the rule and current gen) and a toStringCurrentGen() (which returns a string, like "*   * ** * *"). We will let the client do the modest work of looping to produce multiple generations and displaying each generation, one-beneath-the-previous. We will always assume the seed is a single asterisk surrounded by infinite blanks, like, "...         *        ... ". Also, we can dispense with the "Rule class" (which would no doubt please Herr Marx).

I often like to start with a proposed main() that shows how we will use the class.  From there, it makes the class design a little easier.

int main()
{
  int rule, k;

  // get rule from user
  do
  {
    cout << "Enter Rule (0 - 255): ";
    cin >> rule;
  } while (rule < 0 || rule > 255);

  // create automaton with this rule and single central dot
  Automaton
  aut(rule);

  // now show it
  cout << "   start"  << endl;
  for (k = 0; k < 100; k++)
  {
    cout << aut.toStringCurrentGen() << endl;
    aut.propagateNewGeneration();
  }
  cout << "   end"  << endl;

  return 0;
}

We immediately see that the constructor takes the rule (as an int). That implies that it is stored internally. While an int is, indeed, a compact way to represent a rule, it is not necessarily the most useful.  We should probably devise a slightly more intuitive internal representation of a rule.  Remembering that a rule needs to give an output, on or off, which results from one of eight possible input combinations, we can store this cleanly as an array of eight bools.  So rule[0] will give the output (true=ON or false=OFF) from the input combination "000".  rule[1] would give the output for "001".  rule[2], the output for "010", rule[3] the output for "011", and so on, up to rule[7] which tells the output for the input combo "111".

We should also store a string that represents the current generation or, as I call it, thisGen. 

3A.6.2 Class Automaton

With this introduction, we can now give a reasonable prototype for class Automaton:

class Automaton
{
private:
  bool rules[8];
  string thisGen;
  string extremeBit; // bit, "*" or " ", implied everywhere "outside"
  int displayWidth;  // an odd number so it can be perfectly centered

public:
  static const int MAX_DISPLAY_WIDTH = 121;

  Automaton(int rule);
  string toStringCurrentGen();
  bool setRule(int rule);      // change rule set
  void resetFirstGen();
  bool setDisplayWidth(int width);
  void propagateNewGeneration();
};

displayWidth tells us how much of the thisGen string to send to the console. This enables thisGen to get extremely long (thousands of characters) without causing a mess on the console. If thisGen is, in fact, longer than displayWidth, we have to decide which sub-portion of thisGen to display. The answer is the exact center section, cropping off excess characters equally from the left and right. Typically displayWidth will be 79, but we allow it to grow to 121 (we want to be an odd number for technical reasons.) MAX_DISPLAY_WIDTH determines the maximum displayWidth allowed.

extremeBit

What is this strange sounding member? It is a single character (in a string form) which is either blank, " ", or an asterisk, "*". It represents the value we imagine stored in every string position to the far left and far right (out to infinity), beyond the actual, interesting, middle portion of the string.

To do this automaton correctly, we have to imagine that every generation is infinite in both directions. We begin by assuming that everything to the left and right, which is not the central, single "*" asterisk, is a blank, " ". However, after we start applying the rule to that initial generation, it might change those blanks to asterisks. How? In one of two ways:

Either way, besides the growing central signal, or interesting part, there will be a boring sea of either all 0s or all 1s. The extremeBit string is a single character string that tells us which it is. If it is " ", it means our generation is swimming in a sea of 0s. If it is a "*", it means we are swimming in a sea of 1s. This is needed to compute the next generation.

The Member Methods

Let's describe the methods.

3A.6.3 The Implementation

You will be implementing this as part of your lab assignment this week.