# Cellular Automata: Counting preimages

One of the Google Foobar challenges requires you to write a program to count the the number of preimages of a position in a 2D cellular automaton, under the following rules:

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.

I don't know any mathematical way to count all preimages of a given 2-D grid. So I approached using a brute-force way. But there's a memory error if the dimension of grid is higher than 4x5. Can anyone suggest a better way?

import itertools
import time

true = True
false= False

def bf(width,height,g):
row = [(0,1)] * width
col = (itertools.product(*row) for _ in range(height))
a = machine(list(itertools.product(*col)),g)
return a

def machine(x,g):
j=0
for i,k in enumerate(x):
if tran(x[i],x[i],x[i],x[i]) == g:
if tran(x[i][-1],x[i][-1],x[i][-2],x[i][-2]) == g[-1]:
if tran(x[i][-2],x[i][-2],x[i][-1],x[i][-1]) == g[-1]:
if tran(x[i][-2][-1],x[i][-2][-2],x[i][-1][-2],x[i][-1][-1]) == g[-1][-1]:
if tran(x[i],x[i],x[i],x[i]) == g:
if nk(k) == g:
j += 1
return j

def tran(a,b,c,d):
if a+b+c+d == 1:
return 1
else:
return 0

def nk(arr):
width = len(arr)
height = len(arr)
arr_new = [[0 for x in range(0)] for y in range(height-1)]
for x in xrange(0,height-1):
for y in xrange(0,width-1):
if arr[x][y] + arr[x][y+1] + arr[x+1][y] + arr[x+1][y+1] == 1:
arr_new[x].append(1)

else:
arr_new[x].append(0)
return arr_new

start = time.time()
width = len(g) + 1
height = len(g) + 1
print bf(width,height,g)
print "Time : ", (time.time()-start)


EDIT : So I started working mathematically now. I'm working on de burijn idea. MemoryError is solved now. This new code is not taking too much time to solve problem iff the grid given is less than 9x10. So can anyone now tweak my code?

true = True
false =False
import time

def transpose(arry):
return map(list, zip(*arry))

def state(grid):
state_ary = {}
for i, row in enumerate(grid):
for j, col in enumerate(row):
if col == 1:
state_ary[(i, j)] = {((1, 0),): ((0, 0),),
((0, 1),): ((0, 0),),
((0, 0),): ((1, 0), (0, 1))}
else:
state_ary[(i, j)] = {((1, 1),): ((1, 1), (1, 0), (0, 1), (0, 0)),
((0, 1),): ((1, 1), (0, 1), (1, 0)),
((1, 0),): ((1, 1), (1, 0), (0, 1)),
((0, 0),): ((1, 1), (0, 0))}
return state_ary

def column_state(grid):
state_ary = state(grid)
valid_col_states = {}
temp_col_states = {}
for j in xrange(len(grid)):
valid_col_states[j] = state_ary[(0, j)]
for i in xrange(len(grid) - 1):
for stn, value in valid_col_states[j].items():
for elem in value:
if (elem,) in state_ary[(i + 1, j)]:
temp_col_states[(stn[:] + (elem,))] = state_ary[(i + 1, j)][(elem,)]
valid_col_states[j] = temp_col_states
temp_col_states = {}
return valid_col_states

def splitter(col):
l_r_dict = {}
for key_1, value_1 in col.items():
for val_row in value_1:
temp_r = ()
temp_l = ()
for key_row in key_1:
temp_r += (key_row[-1],)
temp_l += key_row[:-1]
temp_r += (val_row[-1],)
temp_l += val_row[:-1]
if (temp_l,) in l_r_dict:
l_r_dict[(temp_l,)] += (temp_r,)
else:
l_r_dict[(temp_l,)] = (temp_r,)
return l_r_dict

def compare(col_1, col_2):
valid_col_states = {}
for stn, value in col_1.items():
for elem in value:
for stn_2 in col_2.keys():
if elem == stn_2:
valid_col_states[(stn[:] + (elem,) + stn_2[1:])] = col_2[stn_2]
return valid_col_states

def valid_state(grid):
state_col = column_state(grid)
state_valid_g = {}
for stn, value in state_col.items():
state_valid_g[stn] = splitter(value)

for j in xrange(len(state_valid_g)-1):
state_valid_g[j+1] = compare(state_valid_g[j], state_valid_g[j+1])
return state_valid_g

now = time.time()
valid = valid_state(g)
meter = 0
for item in valid[max(valid.keys())].values():
meter += len(item)
now_new = time.time()-now
print now_new
return meter

• Is this one of the Google Foobar challenges? – Gareth Rees Jul 20 '17 at 12:58
• x[i],x[i],x[i],x[i]) == g holy cow! – t3chb0t Jul 20 '17 at 13:13
• Gareth.. Yes this one's the last level of that foobar – nk_mason Jul 20 '17 at 13:58
• t3chhb0t.. Hmm... yup I also said that after seeing tf i've done. – nk_mason Jul 20 '17 at 13:59
• Why the call to list in line 10? – Peter Taylor Jul 20 '17 at 14:10