Expanding Nebula: Problem in Cellular Automata or Coding Theory

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.

This was my answer... I completed it today :

box = {
    ((0, 0), (0, 0)) : 0,
    ((0, 0), (0, 1)) : 1,
    ((0, 0), (1, 0)) : 1,
    ((0, 0), (1, 1)) : 0,
    ((0, 1), (0, 0)) : 1,
    ((0, 1), (0, 1)) : 0,
    ((0, 1), (1, 0)) : 0,
    ((0, 1), (1, 1)) : 0,
    ((1, 0), (0, 0)) : 1,
    ((1, 0), (0, 1)) : 0,
    ((1, 0), (1, 0)) : 0,
    ((1, 0), (1, 1)) : 0,
    ((1, 1), (0, 0)) : 0,
    ((1, 1), (0, 1)) : 0,
    ((1, 1), (1, 0)) : 0,
    ((1, 1), (1, 1)) : 0,
}



true = True
false = False


def get_col_comb(first,column):
    x = ((0,0),(0,1),(1,0),(1,1))
    count_possibility = []

    for key in first:
        nextCol = []

        for val in x:
            if box[((key[0],key[1]),val)] == column[0]:
                nextCol.append(val)

        for n in xrange(1,len(column)):
            newCol = []
            if len(nextCol) == 0:
                break
            for col in nextCol:
                for m in xrange(2):
                    tempCol = list(col)
                    if box[((key[n],key[n+1]),(col[n],m))] == column[n]:
                        tempCol.append(m)
                        newCol.append(tempCol)
            nextCol = newCol
        [count_possibility.append((key,tuple(c))) for c in nextCol]
    return tuple(count_possibility)

def swap_row_col(g):
    return tuple(zip(*g))

def nk(firstColumn):
    def first_col_int(f_c_col):
        def initialize(col):
            g0 = col[0]
            l = []
            for key,val in box.iteritems():
                if g0 == val:
                    l.append(key)
            return tuple(l)

        x = ((0,0),(0,1),(1,0),(1,1))
        present = initialize(f_c_col)
        for n in xrange(1,len(f_c_col)):
            new = []
            for z in present:
                for comb in x:
                    possibility = (z[n],comb)

                    if box[possibility] == f_c_col[n]:
                        temp = list(z)
                        temp.append(comb)
                        new.append(temp)

            present = tuple(new)
        return tuple([swap_row_col(x) for x in present])

    if firstColumn in no_col:
        return no_col[firstColumn]
    else:
        right_grids = first_col_int(firstColumn)
        no_col[firstColumn] = right_grids
        return right_grids

def counter(g):
    rotation = swap_row_col(g)
    first = {}
    right_grids = nk(rotation[0])
    for z in right_grids:
        if z[1] not in first:
            first[z[1]] = 1
        else:
            first[z[1]] = first[z[1]] + 1
    for n in xrange(1,len(rotation)):
        second = {}
        newGrids = get_col_comb(first,rotation[n])
        total = len(newGrids)
        for z in newGrids:
            isValid_counter = 0
            if z[0] in first:
                isValid_counter += 1
                if z[1] in second:
                    second[z[1]] = first[z[0]] + second[z[1]]
                else:
                    second[z[1]] = first[z[0]]
        first = second
    meter = 0
    for row, count in first.iteritems():
        meter += count
    return meter

no_col = {}

def answer(g):
    return counter(g)