In this lab we shall implement a somewhat similar Ulam-Warburton automaton that produces its own distinctive fractal shapes of a more crystalline and symmetric nature. (Besides, Stanislaw Ulam was a pretty important figure in applied mathematics and computing in his time including the Manhattan Project, so his life and creations should deserve at least some attention.)

The first new programming technique used in this lab shows how to explicitly encode two-dimensional arrays in just one dimension. Two-dimensional arrays in Java are actually just one-dimensional arrays whose elements are one-dimensional arrays. This "array of arrays" representations allows the individual rows to be ragged so that they don't necessarily all have the same length. However, when dealing with regular grids where each row is known to have the same length, the two-dimensional structure can also be encoded into a one-dimensional array with a total of rows*cols elements, where each element in the two-dimensional position (i,j) is stored in position i*cols+j. (This is how numpy stores and represents its arrays that are known to be grids of uniform elements.)

The Ulam-Warburton automaton is similar to Game of Life in style and spirit so that every cell in the board (which for us is a simple two-dimensional grid, but could in principle be any graph) is always in exactly one of the two possible binary states "on" and "off". The automaton advances in discrete steps starting from zero, updating each cell logically simultaneously at each tick of time. In the original Game of Life the state of each cell at time t + 1 depends on the states of the up to eight cells in its 3-by-3 Moore neighbourhood (fewer for the cells on edges and corners) only at the previous time t, the rules of Ulam-Warburton automaton have the state at t + 1 depend only on its von Neumann neighbourhood (up, right, down, left) from the previous two steps t and t - 1, instead of just the immediate predecessor state at t as in Game of Life. The rules are:

If the cell (i, j) is off at time t, it is on at time t + 1 if exactly one of its four neighbours was on at time t, and otherwise it is off.

If the cell (i,j) is on at time t, it is on at time t+1 if that same cell (i,j) was off at time t-1, and otherwise it is off.

In other words, cells turn on at the time when exactly one of their neighbours is on, and automatically turn off after having been on for two steps, regardless of the states of the neighbouring cells. Your method must be careful at the edges so that they do not try to access nonexistent cells outside the board.

In your BlueJ labs project, create a class Ulam and write the following method inside it:

public static void computeNext(int cols, boolean[] prev, boolean[] curr, boolean[] next)

The arrays prev and curr contain the two-dimensional boards at times t - 1 and t encoded into a single dimension, as explained above. (The number of rows is equal to prev.length/cols, and would thus be redundant to have as a parameter.) This method should not return anything, but compute the state of the board at t + 1 into the given parameter array next. Every time this method is called, all three arguments prev, curr and next are guaranteed to be proper array objects that contain enough elements.

To allow the states of this automaton to be displayed as a Swing component, have your Ulam class extend JPanel. Define the field

private boolean[][] states; 

that the component uses to store the computed states of the automaton, so that state at time t is stored in the one-dimensional boolean array states[t]. Then, define a constructor

public Ulam(int rows, int cols, int[][] start, int n) 

that computes the states of this automaton for times 0 to n for later lookup. At time t = 0, every state is off. At time t = 1, every state is off except those whose positions are given in the array start that is guaranteed to contain two-element int[] objects as its elements. For example, in the UlamTest method massTest, the array

int[][] start = { {100, 100}, {100, 200}, {200, 100}, {200, 200} };

would have those four states on. To allow the user code to access the state of each cell at given times, your class should have the accessor method

public boolean getCellState(int i, int j, int t) 

thatreturnsthestateofthecell(i,j) attimet.ToverifythatthelogicofyourcomputeNextmethod is correct according to the rules of this automaton, you should run the massTest method in the JUnit test class UlamTest to verify that it gives you a green checkmark.

Just so that we can try something new in this lab, instead of animating the evolution of the automaton states using some form of Java concurrency, the component should contain a JSlider instance whose values range from 0 to n. By grabbing and moving that slider, the user should be able to instantly skip to any particular time to see the board displayed in the paintComponent method in a manner that resembles the following low-resolution screenshot.

This code is to be written in Java.

Here is the tester for this question:

import static org.junit.Assert.*; import org.junit.After; import org.junit.Before; import org.junit.Test;

import java.math.BigInteger; import java.util.*; import java.util.zip.CRC32;

import java.awt.*; import javax.swing.*;

public class UlamTest {

@Test public void massTest() { int[][] start = { {100, 100}, {100, 200}, {200, 100}, {200, 200} }; Ulam ulam = new Ulam(300, 300, start, 500); CRC32 check = new CRC32(); Random rng = new Random(12345); for(int c = 0; c < 1000; c++) { int i = rng.nextInt(300); int j = rng.nextInt(300); int s = rng.nextInt(500); check.update(ulam.getCellState(i, j, s) ? c : 0); } assertEquals(1297780951L, check.getValue()); } @Test public void launchUlam() { JFrame f = new JFrame("Ulam"); // Tell the frame to obey the close button f.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE); f.setLayout(new FlowLayout()); int[][] start = { {100, 100}, {100, 200}, {200, 100}, {200, 200} }; f.add(new Ulam(300, 300, start, 500)); f.pack(); f.setVisible(true); } }