Google Foobar Expanding Nebula Problem

Gino Prasad

05/17/2023

This algorithm finds the Preimage Matrix for this cellular automata. Then, this uses dynamic programming to find the number of preimages for a given state.

Here is my source for counting the number of preimage states: https://en.wikibooks.org/wiki/Cellular_Automata/Counting_Preimages

import numpy as np

def to_decimal(ls):
    sum_ = 0
    for i, val in enumerate(reversed(ls)):
        sum_ += (2 ** i) * val
    return sum_

g = np.array([[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]])

num_states = len(g)
num_states

5

sequence = [to_decimal(x) for x in zip(*g)]
sequence

[31, 4, 31, 0, 0, 17, 31, 17]

k = 2

First, we convert the 2d input into a 1D sequence

The number of states per cell is $2^{width}$

k = 2 because each neighborhood has 2 cells

Want to get D matrix

# preimage states: $2^{num\_states+1}$

The rows are the left cell, the columns are the right cell

def get_next_state(state_1, state_2, num_states):
    next_state = 0
    for i in range(num_states-1,-1,-1):
        # checks if exactly bit is 1 in the 2x2 window
        next_state <<= 1
        bit_sum = (((state_1 >> i) % k) + ((state_1 >> i+1) % k) + ((state_2 >> i) % k) + ((state_2 >> i+1) % k))
        bit = bit_sum == 1
        next_state += bit
    return next_state

get_next_state(2, 0)

3

def get_preimage_matrix_unoptimized(num_states):
    preimage_states = np.arange(2 ** (num_states+1))
    D = np.array([[get_next_state(row, col, num_states) for col in preimage_states] for row in preimage_states])
    return D

def get_preimage_matrix(num_states):
    # Recursively returns the preimage matrix
    if num_states == 1:
        return get_preimage_matrix_unoptimized(num_states)
    prev_matrix = get_preimage_matrix(num_states-1)
    
    preimage_matrix = np.zeros((2 ** (num_states+1), 2 ** (num_states+1)), dtype=np.int32)
    for inner_quad in range(k**2):
        row_start = (2 ** (num_states - 1)) * (inner_quad % 2)
        col_start = (2 ** (num_states - 1)) * (inner_quad // 2)
        
        prev_matrix_quad = prev_matrix[row_start:row_start+(2**(num_states-1)),col_start:col_start+(2**(num_states-1))]
        for outer_quad in range(k**2):
            target_row_start = row_start + ((2 ** num_states) * (outer_quad % 2))
            target_col_start = col_start + ((2 ** num_states) * (outer_quad // 2))
            
            bit = ((outer_quad % 2) + (outer_quad // 2) + (inner_quad % 2) + (inner_quad // 2)) == 1
            preimage_matrix[target_row_start:target_row_start+(2**(num_states-1)),target_col_start:target_col_start+(2**(num_states-1))] += prev_matrix_quad + (bit*(2 ** (num_states-1)))
    return preimage_matrix

def solution(sequence):
    num_combinations = np.ones(2 ** (num_states+1)).astype(int)
    for state in sequence:
        num_combinations = np.matmul((D == state).astype(int), num_combinations)
    return num_combinations.sum()

solution(sequence)

254