Jogo da Vida

Nesta tarefa, exercitaremos o uso estruturas multidimencionais em Python. O tema será o autômato celular proposto por John Horton Conway em 1970, conhecido como Jogo da Vida.

O jogo, que na verdade não tem jogadores, opera sobre um tabuleiro com células vivas e células mortas. Utilizaremos um padrão ASCII-ART em que células vivas são representadas por caracteres @ e células mortas por espaços em branco. Uma moldura com caratecteres + e - será utilizada para facilitar a visualização da delimitação dos diagramas.

+-----+
|     |
|  @  |
| @ @ |
|     |
+-----+

Na definição original, o diagrama é infinito e toda célula tem 8 vizinhos como esquematizado abaixo:

 V8  V1 V2
   \ | /
V7 - @ - V3
   / | \
 V6  V5 V4 

No nosso caso, para simplificar, consideraremos que as células adjacentes à moldura estão sempre mortas. Os estados das outras células poderão ser modificadas a partir da seguintes regras:

• Sobrevivência: toda célula viva com dois ou três vizinhos sobrevive para a próxima geração.
• Morte: toda célula com quatro ou mais vizinhos irá morrer por superpopulação; toda célula com menos de dois vizinhos irá morrer por isolamento.
• Nascimento: uma célula morta com exatamente três vizinhos irá (re)nascer.

Todas as mortes e todos os nascimentos são calculadas simultaneamente, dando origem a uma sequência de quadros.

+-----------------+ +-----------------+ +-----------------+ +-----------------+ 
|                 | |                 | |                 | |                 |
|     @     @     | |                 | |                 | |     @     @     |
|     @     @     | |    @@     @@    | |    @@@   @@@    | |     @     @     |
|     @@   @@     | |     @@   @@     | |                 | |     @@   @@     |
|                 | |  @  @ @ @ @  @  | |  @    @ @    @  | |                 |
| @@@  @@ @@  @@@ | |  @@@ @@ @@ @@@  | |  @    @ @    @  | | @@@  @@ @@  @@@ |
|   @ @ @ @ @ @   | |   @ @ @ @ @ @   | |  @    @ @    @  | |   @ @ @ @ @ @   |
|     @@   @@     | |    @@@   @@@    | |    @@@   @@@    | |     @@   @@     |
|                 | |                 | |                 | |                 |
|     @@   @@     | |    @@@   @@@    | |    @@@   @@@    | |     @@   @@     |
|   @ @ @ @ @ @   | |   @ @ @ @ @ @   | |  @    @ @    @  | |   @ @ @ @ @ @   |
| @@@  @@ @@  @@@ | |  @@@ @@ @@ @@@  | |  @    @ @    @  | | @@@  @@ @@  @@@ |
|                 | |  @  @ @ @ @  @  | |  @    @ @    @  | |                 |
|     @@   @@     | |     @@   @@     | |                 | |     @@   @@     |
|     @     @     | |    @@     @@    | |    @@@   @@@    | |     @     @     |
|     @     @     | |                 | |                 | |     @     @     |
|                 | |                 | |                 | |                 |
+-----------------+ +-----------------+ +-----------------+ +-----------------+

Entrada

As primeiras linhas da entrada conterão um diagrama inicial para o jogo da vida no formato utilizado nos exemplos anteriores. A última linha conterá o número de passos a serem processados na sequência, ou seja, o número de quadros além do quadro original que você deverá apresentar na saída.

+------+
|      |
|      |
|  @@@ |
| @@@  |
|      |
|      |
+------+
1

Saída

A saída conterá uma repetição do diagrama inicial seguida do(s) quadro(s) solicitado(s).

+------+ +------+ 
|      | |      | 
|      | |   @  | 
|  @@@ | | @  @ | 
| @@@  | | @  @ | 
|      | |  @   | 
|      | |      | 
+------+ +------+ 

Testes para o SuSy

Esta tarefa terá 10 testes abertos com padrões conhecidos do Jogo da Vida. Note que alguns padrões estabilizam, outros desaparecem, outros oscilam e outros se deslocam no diagrama. Veja, como exemplos, os testes 2, 3, 6 e 9.

+-----+
|     |
|  @  |
| @ @ |
|  @  |
|     |
+-----+
2

+-----+ +-----+ +-----+
|     | |     | |     |
|  @  | |  @  | |  @  |
| @ @ | | @ @ | | @ @ |
|  @  | |  @  | |  @  |
|     | |     | |     |
+-----+ +-----+ +-----+

+----+
|    |
| @  |
| @  |
|  @ |
|    |
+----+
2

+----+ +----+ +----+
|    | |    | |    |
| @  | |    | |    |
| @  | | @@ | |    |
|  @ | |    | |    |
|    | |    | |    |
+----+ +----+ +----+

+-----+
|     |
|  @  |
|  @  |
|  @  |
|     |
+-----+
5

+-----+ +-----+ +-----+ +-----+ +-----+ +-----+
|     | |     | |     | |     | |     | |     |
|  @  | |     | |  @  | |     | |  @  | |     |
|  @  | | @@@ | |  @  | | @@@ | |  @  | | @@@ |
|  @  | |     | |  @  | |     | |  @  | |     |
|     | |     | |     | |     | |     | |     |
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+

+-------+
|       |
|  @    |
|   @   |
| @@@   |
|       |
|       |
|       |
+-------+
7

+-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+
|       | |       | |       | |       | |       | |       | |       | |       |
|  @    | |       | |       | |       | |       | |       | |       | |       |
|   @   | | @ @   | |   @   | |  @    | |   @   | |       | |       | |       |
| @@@   | |  @@   | | @ @   | |   @@  | |    @  | |  @ @  | |    @  | |   @   |
|       | |  @    | |  @@   | |  @@   | |  @@@  | |   @@  | |  @ @  | |    @@ |
|       | |       | |       | |       | |       | |   @   | |   @@  | |   @@  |
|       | |       | |       | |       | |       | |       | |       | |       |
+-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+ +-------+

Esta tarefa inclui dois testes fechados.

Dicas de Python 3 para esta tarefa:

• Cada quadro pode ser armazenado como uma lista de lista de caracteres (" " ou "@") ou inteiros (0 ou 1).

• Exercite o uso de estruturas com três dimensões armazenando a sequência de quadros como uma lista de quadros.

• Ao trabalhar com listas, precisamos diferenciar as operações que geram novas listas das que criam referências distintas para a mesma lista. Observe os exemplos:

  $ python3
  >>> a = [0, 0, 0] 
  >>> b = a         # b é uma referência para a 
  >>> b[0] = 1      
  >>> print(a)      # a lista referenciada por a e b foi alterada
  [1, 0, 0]
  
  >>> c = [0, 0, 0]
  >>> d = c.copy() # d é uma cópia de c
  >>> d[0] = 1     
  >>> print(c)     # a lista referenciada por c não foi alterada
  [0, 0, 0]
  
  >>> e = [[0],[0],[0]] # e é uma lista composta por 3 sublistas
  >>> f = e.copy()      # f referencia as mesmas sublistas de e 
  >>> f[0][0] = 1       
  >>> print(e)          # a primeira sublista referenciada por e e f foi alterada
  [[1], [0], [0]]
  
  >>> g = [[0],[0],[0]]
  >>> h = [sl.copy() for sl in g] # podemos copiar todas as sublistas
  >>> h[0][0] = 1
  >>> print(g)
  [[0],[0],[0]]
  
  # ou utilizar a função deepcopy que faz cópia em profundidade de 
  # uma lista, ou seja, duplicando todas as sublistas componentes.
  >>> import copy
  >>> i = [0,[0,0],[[0],[0]]]
  >>> j = copy.deepcopy(i)
  >>> j[0] = 1
  >>> j[1][0] = 1
  >>> j[2][0][0] = 1
  >>> print(j)
  [1, [1, 0], [[1], [0]]]
  >>> print(i)
  [0, [0, 0], [[0], [0]]]
  

• Recomenda-se a escrita de funções para estruturar o seu programa.

• O uso de outras bibliotecas padrão Python para resolver esta tarefa é permitido, mas não é necessário.

Orientações para submissão

Veja aqui a página de submissão da tarefa. Lembre-se que o arquivo a ser submetido deve se chamar main.py. No link Arquivos auxiliares há um arquivo arqs-09.zip que contém todos os arquivos de testes abertos e seus respectivos resultados compactados. Os arquivos executa-testes.py e executa-testes-windows.py também estão neste pacote.

Observe o limite máximo de 20 submissões

A nota final é proporcional ao número de testes que executaram corretamente. A submissão de um código que não implementa o algoritmo solicitado, mas que exibe as saídas esperadas dos testes abertos a partir da comparação de trechos da entrada será considerada fraude e acarretará a atribuição de nota zero à média final da disciplina.

O peso desta tarefa é 3.

O prazo final para submissão é 24/06/2018.