Exercício do Exame de Final de 1998: Problema

Com este exercício pretende-se que implementem um jogo da vida unidimensional com regras de evolução fixas, codificadas da seguinte maneira:

        regra(0,0,0).
        regra(0,1,1).
        regra(1,0,1).
        regra(1,1,0).

Passamos a explicar. Convencionamos que 0 representa uma célula morta enquanto 1 representa uma célula viva. Uma colónia de seres unicelulares será então representada por uma lista de zeros e uns. Por exemplo,

        [0,1,0,1,1,0,1,0,1,0,0,1,1,0]

Com as regras de evolução, vamos poder obter as gerações que se seguem à colónia inicial. As regras apresentadas acima, significam que:

• se houver um 0 (na lista) com um 0 à sua direita, não se altera o 0 (a célula continua morta na próxima geração);
• se houver um 0 com um 1 à sua direita, então o 0 passa a 1;
• se houver um 1 com um 0 à sua direita, não se altera o 1;
• se houver um 1 com um 1 à sua direita, então o 1 passa a zero.

Pretendemos:

a)

Que implementem um predicado proxima_geracao/2 que recebe no primeiro argumento uma lista de 0's e 1's e retorne no segundo argumento, de acordo com as regras descritas, a colónia de células que a sucede.
Exemplos:

         ?- proxima_geracao([1,0,0,0,1,1],L).
            L = [1,0,0,1,0,1]

         ?- proxima_geracao([1,1,1,1,0],L).
            L = [0,0,0,1,0]

b)

Que implementem um predicado jogo_vida/3 que recebe no primeiro argumento o número N de gerações seguintes que pretendemos conhecer; no segundo argumento a colónia de células ``actual''; e que retorna no último argumento a lista com as próximas N gerações (cada geração de células é uma lista de 0's e 1's). Exemplo:

         ?- jogo_vida(2,[1,0,1],L).
            L = [[1,1,1],[0,0,1]]