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
# 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