Expanding Nebula: Problem in Cellular Automata or Coding Theory

Question

First post to Math Stackexchange. Recently I was posed with a mathematically intensive computer programming challenge that I am completely at a loss for solving. To give you some info on my math background, I'm a senior physics major and computer science minor at university and have recently completed a course in linear algebra in addition to having taken calc 1, 2, multivariate calc, and diff eq. I have some small experience with discrete mathematics and number theory from an intro computer science course. I have applied linear algebra, discrete mathematics, and algebraic coding courses scheduled in the next 6 months but am not sure if I will cover the material to answer my problem. I would wait until after taking the courses to see if I can apply anything new to it but this problem has been driving me nuts.

I'm not necessarily looking for a solution but rather some areas to look into that may help me to solve it. If more info or explanation is needed, please let me know. The problem is as follows:

From the scans of the nebula, you have found that it is very flat and distributed in distinct patches, so you can model it as a 2D grid. You find that the current existence of gas in a cell of the grid is determined exactly by its 4 nearby cells, specifically, (1) that cell, (2) the cell below it, (3) the cell to the right of it, and (4) the cell below and to the right of it. If, in the current state, exactly 1 of those 4 cells in the 2x2 block has gas, then it will also have gas in the next state. Otherwise, the cell will be empty in the next state.

For example, let's say the previous state of the grid (p) was:

.O..
..O.
...O
O...

To see how this grid will change to become the current grid (c) over the next time step, consider the 2x2 blocks of cells around each cell. Of the 2x2 block of [p[0][0], p[0][1], p[1][0], p[1][1]], only p[0][1] has gas in it, which means this 2x2 block would become cell c[0][0] with gas in the next time step:

.O -> O
..

Likewise, in the next 2x2 block to the right consisting of [p[0][1], p[0][2], p[1][1], p[1][2]], two of the containing cells have gas, so in the next state of the grid, c[0][1] will NOT have gas:

O. -> .
.O

Following this pattern to its conclusion, from the previous state p, the current state of the grid c will be:

O.O
.O.
O.O

Note that the resulting output will have 1 fewer row and column, since the bottom and rightmost cells do not have a cell below and to the right of them, respectively.

Write a function answer(g) where g is an array of array of bools saying whether there is gas in each cell (the current scan of the nebula), and return an int with the number of possible previous states that could have resulted in that grid after 1 time step. For instance, if the function were given the current state c above, it would deduce that the possible previous states were p (given above) as well as its horizontal and vertical reflections, and would return 4. The width of the grid will be between 3 and 50 inclusive, and the height of the grid will be between 3 and 9 inclusive. The answer will always be less than one billion (10^9).

Inputs:
(boolean) g = [
                [true, false, true],
                [false, true, false],
                [true, false, true]
              ]
Output:
(int) 4

Inputs:
(boolean) g = [
                [true, false, true, false, false, true, true, true],
                [true, false, true, false, false, false, true, false],
                [true, true, true, false, false, false, true, false],
                [true, false, true, false, false, false, true, false],
                [true, false, true, false, false, true, true, true]
              ]
Output:
(int) 254

Inputs:
(boolean) g = [
                [true, true, false, true, false, true, false, true, true, false],
                [true, true, false, false, false, false, true, true, true, false],
                [true, true, false, false, false, false, false, false, false, true],
                [false, true, false, false, false, false, true, true, false, false]
              ]
Output:
(int) 11567

I have looked into coding theory but don't think this falls into any of those categories. I have explored options in bit masking image processing, and cellular automata. The closest I have come to a solution is in researching Margolus neighborhood 2D cellular automata. As this isn't reversible by definition, I haven't found a solution or even general method to find a solution. I'm just curious where I should look. I know this has to have an answer stemming from a field in mathematics but it doesn't resemble anything I currently know.

Answer 1

this is clearly a cellular automaton (CA) question. It has to do with computing the number of preimages of a certain CA rule of size 2x2 within a finite rectangular array. Think of how you would try to construct such preimages. The input (current configuration) is an array of size NxM with values 0 and 1 (true and false if you prefer). So the preimages (i.e. configurations one time-step in the past) have size (N+1)x(M+1) also with values 0 and 1. Now what is the local rule of evolution from one configuration to the next? It has to do with the values of four adjacent cells determining the new value of one cell. Try to do a small example by hand, e.g. given the 3x3 input g from your post. Can you find all four preimage-configurations step by step? Think of what it means to specify some of the cells in the preimage (e.g. along a column or a row) to see what cells in the preimage become determined by those values and by knowing their state (0 or 1, gas or no gas) in the next step of the evolution (i.e. in the input g).

In general finding preimages of CAs (or even determining their number) is a hard problem, but in the case of finite configurations and this specific evolution rule a computer can manage. There is a brute force algorithm which should work fine for the specified input sizes, but there is also a more clever/elaborate algorithm to save a lot of time, especially if your input is a rather long but narrow rectangle.

Hope these comments give you some ideas how to attack the problem. If you need more details, let me know.