Submissões no período de 06 a 12 de julho só serão computadas para alun*s em recuperação de Média dos Laboratórios.
Nesta tarefa, exercitaremos o uso estruturas multidimencionais em Python. O tema será o autômato celular Jogo da Vida proposto por John Horton Conway em 1970. John foi um matemático inglês com contribuições em áreas como teoria dos grupos finitos, teoria dos nós, teoria dos números, teoria combinatória dos jogos e teoria de códigos e que ficou mundialmente conhecido pelo autômato celular que estudaremos nesta tarefa. Ele faleceu em abril de 2020, aos 82 anos, vítima da COVID-19.
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 calculados simultaneamente, dando origem a uma sequência de quadros, como ilustrado abaixo.
+-----------------+ +-----------------+ +-----------------+ +-----------------+
| | | | | | | |
| @ @ | | | | | | @ @ |
| @ @ | | @@ @@ | | @@@ @@@ | | @ @ |
| @@ @@ | | @@ @@ | | | | @@ @@ |
| | | @ @ @ @ @ @ | | @ @ @ @ | | |
| @@@ @@ @@ @@@ | | @@@ @@ @@ @@@ | | @ @ @ @ | | @@@ @@ @@ @@@ |
| @ @ @ @ @ @ | | @ @ @ @ @ @ | | @ @ @ @ | | @ @ @ @ @ @ |
| @@ @@ | | @@@ @@@ | | @@@ @@@ | | @@ @@ |
| | | | | | | |
| @@ @@ | | @@@ @@@ | | @@@ @@@ | | @@ @@ |
| @ @ @ @ @ @ | | @ @ @ @ @ @ | | @ @ @ @ | | @ @ @ @ @ @ |
| @@@ @@ @@ @@@ | | @@@ @@ @@ @@@ | | @ @ @ @ | | @@@ @@ @@ @@@ |
| | | @ @ @ @ @ @ | | @ @ @ @ | | |
| @@ @@ | | @@ @@ | | | | @@ @@ |
| @ @ | | @@ @@ | | @@@ @@@ | | @ @ |
| @ @ | | | | | | @ @ |
| | | | | | | |
+-----------------+ +-----------------+ +-----------------+ +-----------------+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.
+------+
| |
| |
| @@@ |
| @@@ |
| |
| |
+------+
1A saída conterá uma repetição do diagrama inicial seguida do(s) quadro(s) solicitado(s). Para o exemplo acima, a saída será:
+------+
| |
| |
| @@@ |
| @@@ |
| |
| |
+------+
+------+
| |
| @ |
| @ @ |
| @ @ |
| @ |
| |
+------+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 os nove primeiros testes como exemplo na tabela abaixo. O padrão do teste 10 é mais elaborado e é o que ilustra o final da primeira seção deste enunciado. Os dois testes fechados são baseados em padrões que foram testados pelos testes abertos, mas com número diferente de quadros.
| arq01.in | arq02.in | arq03.in | arq04.in | arq05.in | arq06.in | arq07.in | arq08.in | arq09.in |
|---|---|---|---|---|---|---|---|---|
|
|
|
|
|
|
|
|
|
| arq01.res | arq02.res | arq03.res | arq04.res | arq05.res | arq06.res | arq07.res | arq08.res | arq09.res |
|
|
|
|
|
|
|
|
|
Releia, se necessário, as instruções para fazer os testes em Testes com o SuSy.
Cada quadro pode ser armazenado como uma lista de lista de
caracteres (" " ou "@") ou inteiros (0 ou 1).
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 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]]]
O uso de outras bibliotecas padrão Python para resolver esta tarefa é permitido, mas não é necessário. Neste caso, você precisará verificar com uma submissão teste se a biblioteca que você deseja utilizar encontra-se instalada no SuSy.
Veja aqui a
página de submissão da tarefa. O arquivo a ser
submetido deve se chamar lab10.py. No
link Arquivos
auxiliares há um
arquivo aux10.zip que
contém todos os arquivos de testes abertos e seus respectivos
resultados compactados.
O limite máximo será de 30 submissões. Serão considerados os resultados da última submissão.
O peso desta tarefa é 3.
O prazo final para submissão é 21/06/2020.
A nota desta tarefa é proporcional ao número de testes que executaram corretamente, desde que o código esteja coerente com o enunciado. A submissão de um código que não implementa o algoritmo requisitado, 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.