Estou trabalhando em um desafio envolvendo um autômato celular infinito 3D (cúbico) definido como:
Estado inicial : Começamos com 8 células posicionadas nos vértices de um cubo e cada célula está em um dos 4 estados {0: rosa, 1: vermelho, 2: verde, 3: azul}.
Crescimento : A cada passo, o cubo se expande inserindo novas células entre cada par de células existentes. O estado da nova célula é determinado pela soma dos estados de seus vizinhos mais próximos módulo 4. Note que, dependendo de sua posição, uma nova célula tem 2, 4 ou 8 vizinhos mais próximos (é a vizinhança de Moore 3D).
Para ilustrar isso, aqui estão algumas ilustrações dos primeiros passos:
Estado inicial
Passo 1
O nó central por exemplo será Verde porque tem 8 vizinhos, a soma dos tipos deles é 2 (Verde) + 1 (Vermelho) + 1 (Vermelho) + 0 (Rosa) + 2 (Verde) + 0 (Rosa) + 3 (Azul) + 1 (Vermelho) = 10% 4 = 2 (Verde)
Passo 2
Estamos interessados em rastrear a evolução do número de células de cada estado [0, 1, 2, 3]. Aqui estão as contagens para os primeiros passos:
- Inicial: 2, 3, 2, 1
- Passo 1: 6, 10, 7, 4
- Passo 2: 30, 36, 31, 28
- Etapa 3: 196, 192, 155, 186
- Etapa 4: 1'162, 1'276, 1'207, 1'268
Nosso objetivo é determinar a contagem de cada estado de célula na etapa 19. Dado o crescimento exponencial, a força bruta não é viável. Disseram-me que é possível resolver isso em menos de um segundo. Alguém tem alguma ideia de como resolver esse problema?
Agradecemos desde já a sua ajuda!