Rule 30

Rule 30

There is a cellular automaton rule called rule 30. We leave it as an exercise to the reader to determine why this is called rule 30, and why rules 1 through 29 were not as interesting. 🙂

At first glance, the rule may be hard to interpret. Essentially the values of each group of three cells determine the single value of the cell centered immediately beneath them.

In the test below, the 2D expected value array starts off as zeros and ones and gets converted to booleans… I figured it would be easier to visually inspect the array in that format rather than in “true” “false” format.

In the spirit of test first, here is a test, followed by some working code. Enjoy!

public class Rule30Test {

    private final Rule30 rule = new Rule30();
    private boolean[] initial;

    private boolean[][] expected;

    @Before
    public void setup() throws Exception {
        initial = new boolean[15];
        Arrays.fill(initial, false);
        initial[7] = true;

        int[][] expectedAsInts = new int[][] {
                {0,0,0,0,0,0,0,1,0,0,0,0,0,0,0},
                {0,0,0,0,0,0,1,1,1,0,0,0,0,0,0},
                {0,0,0,0,0,1,1,0,0,1,0,0,0,0,0},
                {0,0,0,0,1,1,0,1,1,1,1,0,0,0,0},
                {0,0,0,1,1,0,0,1,0,0,0,1,0,0,0}
        };

        expected = new boolean[5][15];
        for(int r=0; r < expectedAsInts.length; r++) {
            for(int c=0; c < expectedAsInts[r].length; c++){
                expected[r][c] = (expectedAsInts[r][c] == 1);
            }
        }
    }

    @Test
    public void testRule() throws Exception {

        boolean[] row = initial;

        for(int i=0; i < 5; i++) {
            Assert.assertTrue(Arrays.equals(expected[i], row));
            row = rule.mapRow(row);
        }
    }
}


public class Rule30 {

    public boolean[] mapRow(boolean[] row) {
        boolean[] newRow = new boolean[row.length];
        Arrays.fill(newRow, false);
        for(int i=1; i < newRow.length - 1; i++) {
            newRow[i] = map(row, i);
        }
        return newRow;
    }

    // white == off == false
    // requires boolean of length 3
    // int p is position, the center of what we can think of as a 3-element subarray
    private boolean map(boolean[] t, int p) {
        if( ! t[p-1] && ! t[p] && ! t[p+1]) {
            return false;
        }
        if( ! t[p-1] && ! t[p] &&   t[p+1]) {
            return true;
        }
        if( ! t[p-1] &&   t[p] && ! t[p+1]) {
            return true;
        }
        if( ! t[p-1] &&   t[p] &&   t[p+1]) {
            return true;
        }
        if(   t[p-1] && ! t[p] && ! t[p+1]) {
            return true;
        }
        if(   t[p-1] && ! t[p] &&   t[p+1]) {
            return false;
        }
        if(   t[p-1] &&   t[p] && ! t[p+1]) {
            return false;
        }
        if(   t[p-1] &&   t[p] &&   t[p+1]) {
            return false;
        }
        throw new IllegalArgumentException();
    }
}

Advertisements

1 Comment

Filed under Software Engineering

One response to “Rule 30

  1. Let alone Rules 31 through 255!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s