Due

Objectives

• to use arrays, 1-D and 2-D

Reading

Introduction

Each automaton produces a new one when a set of rules is applied to it. The rules determine which cells in the new automaton are filled. The rules are based on the state of the cell and its two neighbors in the original automaton. For example, a rule might say that if a cell and its right neighbor are filled in the original automaton but its left neighbor is not filled, then in the new automaton the cell will be filled.

The applet below allows you to select the state of the original automaton and the rules that will be applied to it. It will show you the result of applying those rules to the original automaton, to the automaton that results from that first step, to the automaton that results from that second step, and so on.

As an example, select the first, fourth, and fifth rules along the right side of the applet. Fill the second, third, fifth, seventh, and tenth cells in the original automaton by clicking the boxes in the top row. Click "Run" to see the results. The second and eighth cells in the second row should now be filled.

The first cell in the second row is not filled because we did not select the rule that would have filled it. In the original automaton the first cell was empty, its left neighbor was empty (we are treating all cells that are off the edges of the display as empty), and its right neighbor was filled. The rule that would have applied is the second rule. If you check the box for the second rule and click "Run" again, the first cell in the second row will be filled (try it and then put things back the way they were).

The second cell in the second row is filled because we did select the rule that says it should be filled. That rule is the one that says that if a cell is filled in the original automaton and its right neighbor is filled but its left neighbor is not, then the cell is filled in the resulting automaton (this rule is the fourth one in the list).

All the other cells in the second row are filled or are left unfilled according to the rules we selected in the same manner: first, we examine the cell and its two neighbors in the original automaton; if the corresponding rule was selected then the cell is filled. The process is repeated for the third row, but for that row we examine the cells in the second row. For the fourth row we examine the cells in the third row, and so on.

Assignment

Rule should have the following.

• A field that is a one-dimensional array of three elements. This array will record what is necessary for a cell to be full in the next generation. For example, the rule that says that a previously empty cell becomes full if both of its neighbors were full could be recorded in an array as {1, 0, 1}.
• A constructor that takes a String as an argument. The String would have 0's and 1's to correspond to where the true and false would go in the array field. For example, the rule described above would be specified by the String "101".
• A method getCell that returns the state of the cell specified by the argument. The argument would be -1 to indicate the left neighbor, 1 for the right neighbor, or 0 to indicate the original cell. (Note that you will have to translate the argument to an array index here: if the argument is -1 you want to look in array element 0; if the argument is 0 you need to examine array element 1, and so on.)
• A method toString that returns a String representation of the rule using 0's and 1's. For example, the rule described above would be returned as the String "101".
• A method equals that determines if the Rule the method is invoked on is the same as the Rule passed in as an argument.

The Rule class should work with the following test driver.

    public static void main(String[] args)
    {
	Rule r1 = new Rule("000");
	Rule r2 = new Rule("101");
	Rule r3 = new Rule("110");
	Rule r4 = new Rule("000");

	System.out.println(r1.getCell(-1)); // displays 0
	System.out.println(r2.getCell(-1)); // 1
	System.out.println(r3.getCell(1)); // 0

	System.out.println(r1); // 000
	System.out.println(r3); // 110

	System.out.println(r1.equals(r2)); // false
	System.out.println(r4.equals(r1)); // true
    }

RuleSet should contain the following.

• A field that is an array of Rules.
• A field that counts how many Rules are in the set.
• A constructor that creates the array so it can hold up to eight Rules and initializes the count.
• A method add that adds the Rule given as an argument to the set if it is not already in the set.
• A method contains that determines if the Rule given as an argument is in the set.
• A method size that returns the size of the set.

    public static void main(String[] args)
    {
	RuleSet s = new RuleSet();

	Rule r1 = new Rule("011");
	Rule r2 = new Rule("101");
	Rule r3 = new Rule("110");

	System.out.println(s.contains(r1)); // should display false
	
	s.add(r1);
	s.add(r2);
	s.add(r1);

	System.out.println(s.size()); // 2

	System.out.println(s.contains(r1)); // true
	System.out.println(s.contains(r2)); // true
	System.out.println(s.contains(r3)); // false
    }

• A 1-D array field to hold the state of each cell.
• A constructor that takes the size of the automaton as an argument and initializes the automaton to all empty.
• A method setCell that sets the cell at the position specified by the argument.
• A method getCell that returns the state of the cell at the position specified by the argument.
• A method toString that returns a String representation of the automaton. Represent empty cells as '.' and full cells as '*'.
• A method hasMatch that takes two arguments: a RuleSet and a position of a cell. It should return true if and only if there is a rule in the set that applies to the cell. For the purposes of this method, the left neighbor of the leftmost cell and the right neighbor of the rightmost cell should be considered empty. hasMatch should work by creating a String representation of the rule that applies to the cell. For example, if the cell and only its right neighbor are filled then the String would be 011. Next, hasMatch should make a Rule out of that String using the Rule constructor and should check if that Rule is in the RuleSet that was passed in as an argument.
• A method applyRules that takes a RuleSet as an argument and returns the Automaton1D that represents the next generation according to the rules. This method should work by creating a new automaton and, for every cell in it, calling hasMatch to determine if the cell should be filled. A cell in the new automaton can be filled by calling the setCell method on it.
• A method runGenerations that takes two arguments: a RuleSet and a number of generations. It should return a 2-D array of integers with the original automaton in the top row, the 1st generation in the next row, and so forth (note that the total number of rows will be one more than the number of generations since the original automaton is in the first row). Empty cells should be saved in the array as 0 and full cells as 1. This method should work by creating a 2-D array of the appropriate size. It should then copy from the array field of the original automaton into the top row of the 2-D array. Next, it should call applyRules to get the first generation and copy from the array field of the resulting automaton into the second row in the 2-D array. Then applyRules should be called on the new automaton and the resulting automaton should be copied into the third row. That process repeats as many times as are specified by the argument.

Automaton1D should work with the following test driver.

    public static void main(String[] args)
    {
	RuleSet s = new RuleSet();

	Rule r1 = new Rule("000");
	Rule r2 = new Rule("110");
	Rule r3 = new Rule("001");

	s.add(r1);
	s.add(r2);
	s.add(r3);

	Automaton1D a = new Automaton1D(10);

	System.out.println(a); // should display ..........
	System.out.println(a.getCell(3)); // 0

	a.setCell(2);
	a.setCell(4);
	a.setCell(7);
	a.setCell(8);

	System.out.println(a); // ..*.*..**.

	System.out.println(a.hasMatch(s, 0)); // true (the rule 000 matches)
	System.out.println(a.hasMatch(s, 1)); // true (001)
	System.out.println(a.hasMatch(s, 2)); // false

	System.out.println(a.applyRules(s)); // **....*.*.

	// should display
	// 
	// ..*.*..**.
	// **....*.*.
	// .*.***....
	// *....*.***

	int[][] grid = a.runGenerations(s, 3);

	for (int r = 0; r < grid.length; r++)
	    {
		for (int c = 0; c < grid[r].length; c++)
		    if (grid[r][c] == 0)
			System.out.print('.');
		    else
			System.out.print('*');
		System.out.println();
	    }
    }

Advice

If you assign the character '0' to an int variable, the variable gets the value 48 because that is the position of '0' in the ordering of characters. To convert digit characters to their proper numeric values you can use the Character.getNumericValue method.

If you are stuck on Rule, start with RuleSet. RuleSet will be very much like Dictionary from lab 7. You do, however, need a working Rule class in order to test RuleSet. If you do not have one you can use my Rule.class which is the compiled version of my Rule.java. In order to use this, first move your own Rule.java (if you have one) to a different directory. Then save Rule.class to the directory where you are saving the rest of your Project 4 source code. Then, when you try to compile RuleSet and run RuleSetTest the compiler will automatically use Rule.class.

If you can't figure out how to avoid an ArrayIndexOutOfBoundsException when hasMatch is called on the left or right end of an automaton, then modify applyRules so it skips those ends (and comment out the first test of hasMatch in RuleSetTest). If applyRules is otherwise correct, it should give the correct results except at the ends.

Grading

• 70% Execution. Partial credit will be granted depending on how much progress you made towards the correct result.
• 20% Design. The design score is based on how easy it is to follow the logic of your code, how well you avoided repetitive code, and how easy it would be to change your code if certain specifications changed.
• 10% Style. Style includes comments, indentation, and choice of variable and method names.
• Substantial progress must be made towards correct execution to earn the points for design and style.

Submissions