O Jogo da Vida simula o comportamento de “células” em um universo discreto bidimensional governado por um conjunto de regras simples para nascimento, morte e sobrevivência. O universo é representado por um reticulado sobre um toro, isto é, todas as posições no universo têm oito posições vizinhas (quatro vizinhos de lado e quatro de canto). Cada posição do universo é ocupada por uma célula viva ou morta. O universo começa com uma população inicial de células vivas. A cada passo de tempo (iteração) uma nova geração de células é gerada baseada na população da geração anterior de acordo com as seguintes regras:
  • sobrevivência: uma célula passa da geração corrente para a geração seguinte se ela tiver duas ou três células vizinhas vivas na geração corrente;
  • morte: uma célula viva morre ao fim da geração corrente se ela tem menos de duas (solidão) ou mais de três células vivas (inanicação) na sua vizinhança;
  • nascimento: uma célula morta (re)nasce na geração seguinte caso ela tiver exatamente três células vivas na sua vizinhança na geração anterior.
Desenvolva um programa que implemente o jogo da vida seguindo estas regras em um reticulado 50 \times 50. Gere a primeira geração de forma aleatória.

Passo 1

O enunciado pede que eu implemente o Jogo da Vida num reticulado toroidal de tamanho (50\times50) com a primeira geração gerada aleatoriamente. Vou deixar bem explícito o que isso significa e quais são as informações/dados que já estão dados:
  • O tabuleiro tem tamanho (50\times50).
  • Cada posição (célula) pode estar viva ( 1) ou morta ( 0).
  • “Toro” significa que as bordas são periódicas: a célula na borda tem vizinhos do outro lado — em termos práticos, os índices do tabuleiro “dão a volta” (wrap-around).
  • Cada célula possui exatamente oito vizinhos (quatro ortogonais + quatro diagonais).
  • Regras que governam a transição de uma geração para a próxima (todas baseadas no número N de vizinhos vivos da célula na geração corrente):
    • Sobrevivência: uma célula viva sobrevive se N\in\{2,3\}.
    • Morte: uma célula viva morre se N<2 (solidão) ou N>3 (superpopulação).
    • Nascimento: uma célula morta vira viva se N=3.
  • O enunciado pede que a primeira geração seja gerada aleatoriamente (ou seja, cada célula inicial viva ou morta de forma aleatória, tipicamente com uma probabilidade p de nascer viva).
Essas são as informações que usarei ao longo da resolução.

Passo 2

Decisão do método e da estrutura de dados (explicando o porquê):
  • Representação: usar uma matriz 2D de valores binários 0/1. Em Python, isso pode ser uma lista de listas \text{grid}[i][j] ou (melhor para desempenho e simplicidade) um array NumPy.
  • Atualização simultânea: a regra do Jogo da Vida exige que a geração seguinte seja obtida a partir da geração corrente inteira. Logo, NÃO podemos atualizar célula-a-célula no mesmo array sem guardar a geração anterior. Solução: calcular um novo array \text{new\_grid} a partir de \text{grid} e só então substituir.
  • Contagem de vizinhos no toro: para uma célula na posição (i,j) os vizinhos são (i+\Delta i \bmod H,\; j+\Delta j \bmod W)com \Delta i,\Delta j\in\{-1,0,1\} e excluindo (\Delta i,\Delta j)=(0,0). Usar a operação de resto ( \bmod) para implementar o wrap-around. Em código, em Python essa operação pode ser feita com (i+di) % H.
  • Estratégias para contar vizinhos:
    • Versão explícita (didática): para cada célula somar manualmente as 8 posições vizinhas usando operadores módulo.
    • Versão eficiente com NumPy: usar deslocamentos (np.roll) e somar 8 versões deslocadas do array. Ex.: vizinhos = roll(grid,1,axis=0) + roll(grid,-1,axis=0) + … (incluindo deslocamentos em ambas as direções). Essa alternativa é concisa e rápida.

Passo 3

Algoritmo passo-a-passo (alto nível) — isto é o que você precisa saber para implementar na prova:
  1. Inicializar a semente aleatória (opcional, para reprodutibilidade).
  2. Criar a matriz \text{grid} com dimensões H=50 e W=50, preenchida aleatoriamente com 0 e 1, por exemplo com probabilidade p de 1.
  3. Para cada iteração (cada geração):
    a. Contar o número de vizinhos vivos N(i,j) para cada célula (i,j) usando wrap-around.
    b. Aplicar as regras simultaneamente para obter \text{new\_grid}:
    • Se \text{grid}[i][j]==1 e (N(i,j)==2 \text{ ou } N(i,j)==3), então \text{new\_grid}[i][j]=1. Caso contrário \text{new\_grid}[i][j]=0.
    • Se \text{grid}[i][j]==0 e N(i,j)==3, então \text{new\_grid}[i][j]=1.
      c. Substituir \text{grid} \leftarrow \text{new\_grid}.
      d. Mostrar/visualizar/guardar a geração se desejar.
  4. Repetir até atingir o número de gerações desejado ou até o usuário interromper.
Complexidade: para a versão explícita (duas loops for) cada iteração é O(H\cdot W) * 8 vizinhos — ou seja, custo linear no tamanho da grelha. Método com NumPy e roll também é efetivamente linear com coeficiente pequeno.

Passo 4

Como gerar a primeira geração aleatória e decisões práticas:
  • Para gerar aleatoriamente uma matriz de (50\times50) use:
    • em NumPy: grid = (np.random.rand(H, W) < p).astype(int) com p a probabilidade de célula viva (por exemplo p=0,3).
    • em Python puro: grid[i][j] = 1 if random.random() < p else 0.
  • Escolha de p: valores intermediários produzem padrões interessantes. p muito baixo gera poucas células vivas (morre por solidão); p muito alto tende a superpopulação. Um bom valor padrão é p=0{,}3.
  • Semente: random.seed(s) ou np.random.seed(s) tornam a geração reprodutível.

Passo 5

Detalhe matemático/computacional de contagem de vizinhos (a parte que costuma confundir):
  • Definição formal: para cada célula (i,j), N(i,j) = \sum_{\substack{\Delta i=-1\\Delta j=-1}}^{1} \! \text{grid}[(i+\Delta i)\bmod H,\;(j+\Delta j)\bmod W]\;-\;\text{grid}[i,j]em que subtrai-se \text{grid}[i,j] porque o somatório sobre \Delta i,\Delta j inclui o próprio centro.
  • Implementação prática (com NumPy): usar oito deslocamentos com np.roll. Por exemplo, os deslocamentos (\Delta i,\Delta j) são os pares: (-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1).Em código NumPy cada np.roll(grid, shift=(di,dj), axis=(0,1)) desloca a matriz com wrap-around; somando as 8 deslocadas tem-se neighbors.

Passo 6

Exemplo pequeno e manual (para fixar a intuição):
Considere uma grelha 3\times3 (só para exemplificar) com a seguinte disposição inicial (1=viva, 0=morta):
\begin{matrix} 0 & 1 & 0\\[4pt] 0 & 1 & 0\\[4pt] 0 & 1 & 0 \end{matrix}
Aqui a coluna do meio é uma “blinker” vertical. Conte de forma manual o N do centro (1,1): seus vizinhos vivos são os dois na mesma coluna acima e abaixo, total N(1,1)=2. Pela regra, a célula central viva com N=2 sobrevive. A célula em (0,1) tem N=1 (só o de baixo), morre por solidão. Ao aplicar as regras a toda a matriz simultaneamente, a blinker vertical passa a uma forma horizontal:
\begin{matrix} 0 & 0 & 0\\[4pt] 1 & 1 & 1\\[4pt] 0 & 0 & 0 \end{matrix}
Depois de mais uma geração volta ao vertical — é um oscilador de período 2. Esse exemplo mostra a necessidade da atualização simultânea (se atualizasse célula-a-célula sem copiar, o padrão seria destruído).]

Passo 7

Boas práticas e dicas rápidas para a prova (o que lembrar na pressa):
  • Não atualize no mesmo array; sempre calcule um novo array.
  • Use índice modular `% H`, `% W` para o toro.
  • Para contar vizinhos, prefira somar explicitamente as 8 posições vizinhas — é clara, segura e fácil de escrever em prova. Se estiver com tempo e familiaridade, cite que np.roll é uma alternativa elegante.
  • Inicialize com probabilidade p e mencione o valor de p usado.
  • Indique condição de parada (número fixo de gerações ou até estabilidade/oscilação).

Passo 8

Pronto — agora o código completo. O programa abaixo implementa:
  • tabuleiro (50\times50);
  • geração inicial aleatória (parâmetro p_alive);
  • atualização com wrap-around (toro);
  • se puder, usa NumPy + matplotlib para animação; caso contrário, um modo de terminal simples é usado como fallback.
O código está preparado para ser copiado e executado em Python. Leia os comentários do código (no próprio script) para entender cada peça. Boa sorte e força — você vai conseguir entender isso rapidinho!

Resposta

#!/usr/bin/env python3
"""
Jogo da Vida (Conway) em um reticulado toroidal 50x50.
Gera a primeira geração aleatoriamente e anima a evolução.

Versão: tenta usar numpy + matplotlib para visualização. Se matplotlib
não estiver disponível, cai para um modo de terminal simples.

Como usar:
    python jogo_da_vida.py

Parâmetros ajustáveis:
    H, W: dimensões do grid (por padrão 50x50)
    p_alive: probabilidade inicial de célula viva (por padrão 0.3)
    interval_ms: intervalo entre frames em ms (quando usando matplotlib)
"""

import sys
import time
import random

# Parâmetros principais
H = 50
W = 50
p_alive = 0.3  # probabilidade inicial de célula viva
seed = None    # defina um inteiro para reprodutibilidade, ou None
interval_ms = 150  # intervalo entre frames na animação (ms)
max_steps = None    # colocar um inteiro para número fixo de passos, ou None para rodar até fechar

# Tentar importar numpy e matplotlib; se falhar, usar fallback no terminal
try:
    import numpy as np
    import matplotlib.pyplot as plt
    import matplotlib.animation as animation
    HAS_VIS = True
except Exception:
    HAS_VIS = False

if seed is not None:
    random.seed(seed)
    if HAS_VIS:
        np.random.seed(seed)

def init_grid_python(h, w, p):
    """Cria grid h x w em Python puro com probabilidade p de célula viva (0/1 ints)."""
    return [[1 if random.random() < p else 0 for _ in range(w)] for _ in range(h)]

def step_grid_python(grid):
    """Atualiza grid (lista de listas) retornando new_grid, com wrap-around."""
    h = len(grid)
    w = len(grid[0])
    new = [[0]*w for _ in range(h)]
    for i in range(h):
        for j in range(w):
            # conta vizinhos com wrap-around
            n = 0
            for di in (-1, 0, 1):
                for dj in (-1, 0, 1):
                    if di == 0 and dj == 0:
                        continue
                    ni = (i + di) % h
                    nj = (j + dj) % w
                    n += grid[ni][nj]
            if grid[i][j] == 1:
                # sobrevivência se n == 2 ou n == 3
                new[i][j] = 1 if (n == 2 or n == 3) else 0
            else:
                # nascimento se n == 3
                new[i][j] = 1 if n == 3 else 0
    return new

def run_terminal_mode(h, w, p, interval, max_steps=None):
    """Modo simples no terminal; imprime geracoes com caracteres."""
    try:
        grid = init_grid_python(h, w, p)
        step = 0
        while True:
            # limpar tela (cross-platform)
            if sys.platform.startswith('win'):
                _ = os.system('cls')
            else:
                _ = os.system('clear')
            print(f"Jogo da Vida — passo {step}")
            for row in grid:
                print(''.join('█' if x else ' ' for x in row))
            time.sleep(interval / 1000.0)
            grid = step_grid_python(grid)
            step += 1
            if max_steps is not None and step >= max_steps:
                break
    except KeyboardInterrupt:
        print("\nInterrompido pelo usuário.")

# ---- Versão com numpy + matplotlib (recomendada se disponível) ----
if HAS_VIS:
    def init_grid_numpy(h, w, p):
        """Cria um array numpy h x w com 0/1 inteiros."""
        return (np.random.rand(h, w) < p).astype(np.int8)

    def step_grid_numpy(grid):
        """Calcula a próxima geração usando np.roll para wrap-around."""
        # soma das 8 vizinhas via deslocamentos (roll)
        neighbors = (
            np.roll(np.roll(grid, 1, axis=0), 1, axis=1) +  # (-1,-1)
            np.roll(np.roll(grid, 1, axis=0), 0, axis=1) +  # (-1,0)
            np.roll(np.roll(grid, 1, axis=0), -1, axis=1) + # (-1,1)
            np.roll(np.roll(grid, 0, axis=0), 1, axis=1) +  # (0,-1)
            np.roll(np.roll(grid, 0, axis=0), -1, axis=1) + # (0,1)
            np.roll(np.roll(grid, -1, axis=0), 1, axis=1) + # (1,-1)
            np.roll(np.roll(grid, -1, axis=0), 0, axis=1) + # (1,0)
            np.roll(np.roll(grid, -1, axis=0), -1, axis=1)  # (1,1)
        )
        # regras:
        # célula viva sobrevive se neighbors == 2 or 3
        survive = (grid == 1) & ((neighbors == 2) | (neighbors == 3))
        # célula morta nasce se neighbors == 3
        born = (grid == 0) & (neighbors == 3)
        new = (survive | born).astype(np.int8)
        return new

    def run_visual_mode(h, w, p, interval, max_steps=None):
        grid = init_grid_numpy(h, w, p)

        fig, ax = plt.subplots()
        img = ax.imshow(grid, interpolation='nearest', cmap='Greys', vmin=0, vmax=1)
        ax.set_title("Jogo da Vida — pressione fechar para encerrar")
        ax.axis('off')

        step_counter = {'k': 0}

        def update(frame):
            grid[:] = step_grid_numpy(grid)
            img.set_data(grid)
            step_counter['k'] += 1
            if max_steps is not None and step_counter['k'] >= max_steps:
                anim.event_source.stop()
            return (img,)

        anim = animation.FuncAnimation(fig, update, interval=interval, blit=True)
        plt.show()

    # Executar a versão visível
    try:
        run_visual_mode(H, W, p_alive, interval_ms, max_steps)
    except Exception as e:
        print("Erro na visualização com matplotlib:", e)
        print("Caindo para modo terminal.")
        import os
        run_terminal_mode(H, W, p_alive, interval_ms, max_steps)
else:
    # fallback: modo terminal se numpy/matplotlib não disponíveis
    import os
    print("Numpy/matplotlib não detectados — executando modo terminal simples.")
    run_terminal_mode(H, W, p_alive, interval_ms, max_steps)

Exercícios relacionados