1
\$\begingroup\$

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.

(Full text of the challenge here.)

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][0][0],x[i][0][1],x[i][1][0],x[i][1][1]) == g[0][0]:
                        if tran(x[i][-1][0],x[i][-1][1],x[i][-2][0],x[i][-2][1]) == g[-1][0]:
                                if tran(x[i][0][-2],x[i][1][-2],x[i][1][-1],x[i][0][-1]) == g[0][-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][1][1],x[i][1][2],x[i][2][1],x[i][2][2]) == g[1][1]:
                                                        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[0])
    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

def answer(g):
        start = time.time()
        width = len(g[0]) + 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[0])):
        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[0]:
                    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


def answer(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
\$\endgroup\$
  • 1
    \$\begingroup\$ Is this one of the Google Foobar challenges? \$\endgroup\$ – Gareth Rees Jul 20 '17 at 12:58
  • 1
    \$\begingroup\$ x[i][0][0],x[i][0][1],x[i][1][0],x[i][1][1]) == g[0][0] holy cow! \$\endgroup\$ – t3chb0t Jul 20 '17 at 13:13
  • \$\begingroup\$ Gareth.. Yes this one's the last level of that foobar \$\endgroup\$ – nk_mason Jul 20 '17 at 13:58
  • \$\begingroup\$ t3chhb0t.. Hmm... yup I also said that after seeing tf i've done. \$\endgroup\$ – nk_mason Jul 20 '17 at 13:59
  • \$\begingroup\$ Why the call to list in line 10? \$\endgroup\$ – Peter Taylor Jul 20 '17 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.