Cellular automata are an interesting application of computer science, simulating out processes by creating local rules on a grid with individual cells. Each unit of time, or generation, the cells change based on a set of rules, and the process is repeated on the new cells.

The simplest kind of cellular automata are one-dimensional or elementary cellular automata. The idea is that you start with a certain number of cells, each of which can be dead or alive arranged on a Mbius strip (i.e., it wraps from the end back to the beginning), and during each generation, consider cell and the states of its left neighbor, itself, and its right neighbor to decide the cell's state for the next step. Being the savvy mathematician, you know that means that for any given cell, there can be 23, or 8, combinations as shown in graphical form below. see image.

For each of those 8 combinations, the result can be either on or off as a result, depending on the rules of the automata. This means that there are 2^8 or 256, different elementary cellular automata, one for each possible result of each possible state.

For example, here is one possible rule set, with each triplet of squares representing a state (the middle cell is the one being considered), and the square below it representing a result, with a white square being dead or 0, and a black square being alive or 1. see image.

For example, here is two generations of an automata using the above rules, starting with a single cell. see image.

Showing the original generation and fifteen generations at the same time yields an interesting triangular pattern: see image.

The Problem:

Given the initial state of a cellular automata and a rules set, print a two dimensional text image representing the progression of the states over a number of generations.

The Input:

The first line of the input will contain a positive integer, t (t <= 1000), of automata to follow. Each automata will consist of a pair of integers, g (0 <= g <= 100) and w(3 <= w <= 100), followed by two strings on separate lines consisting of only zeroes and ones. g is the number of generations that should be simulated and w is the number of cells in the simulated space.

The first string will be exactly w characters long and will represent the initial state of the space. A 0 denotes a dead cell, while a 1 denotes a living cell. The second string will be exactly 8 characters long and represents the rule set for an automata, given in the order shown in the picture on the previous page. A '1 will result in a live cell, and 0 means that the state will result in a dead cell.

For example, 00011110 will result in a live cell if the current cell and the cell to the right is alive, or only a single of the three cells (left, current, and right) are alive. All other configurations will result in a dead cell.

The Output:

For each automata, output a header Automata #a: where a is the number of the automata, starting from 1, on its own line. Starting from the next line, output the initial state of the grid, followed by g states, each on their own line, of the board as a series of characters. A living cell should be denoted by an octothorpe (#) and a dead cell by a period (.). Each automata should be followed by a blank line.

Sample Input:

3

0 5

01010

11111111

3 9

000010000

00011110

3 6

010010

00010000

Sample Output:

Automata #1:

.#.#.

Automata #2:

....#....

...###...

..##..#..

.##.####.

Automata #3:

.#..#.

..#..#

#..#..

.#..#.

Academic Honesty!

It is not our intention to break the school's academic policy. Projects posted are only used as a reference
and should not be submitted as is. We are not held liable for any misuse of the solutions.
Please see the frequently asked questions page
for further questions and inquiries.

Kindly fill out the form.
Please provide a valid email address and we'll get back to you in less than 24 hours.
We will be sending an invoice through PayPal upon confirmation.
We are a non profit organization however we need an amount to keep this organization running,
and to be able to complete our research and development.