Turmites

Este exercício explora uma nova forma de extender o conceito de formiga de Langton. Agora, o comportamento da formiga não depende apenas da cor no chão, mas também do estado interno dela (representado por um valor inteiro). A ideia de transformar a formiga num autômato vem naturalmente do conceito de máquina de Turing. Isto explica o nome destes novos animais, que é um amálgama de Turing e Termite (se não sabe o que uma máquina de Turing é, vá à wikipédia, por que é impossível ser um cientista da computação de verdade sem conhecê-la).

Novamente, tem que simplesmente escrever o método step(), encarregado de fazer o turmite dar um passo. Novamente, deve primeiro encontrar o rank da cor do chão da célula atual na sequência de cores. Mas agora, os dados de rule (regras) dependem tanto da cor atual quanto do estado atual. A rule na verdade contém 3 informações em cada situação: a cor que a escreve, o movimento a fazer e o valor do próximo estado. Por exemplo, [!java|python]rule[1][0][/!][!scala]rule(1)(0)[/!] contém as informações para usar quando state==1 e color==0. Em outros mundos, pode recuperar a informação relativa à sua situação atual a usar [!java|python]rule[state][currentColor][/!][!scala]rule(state)(currentColor)[/!].

Cada um destes conjuntos de informações contém 3 valores. O primeiro é o rank da cor para escrever no chão. O segundo é o movimento para fazer, com a seguinte notação: 0=stop, 1=noturn, 2=left, 4=u-turn, 8=right. Observe que se o comando é stop, não se pode mover nem para a frente neste passo (mas também não pode parar o programa: os próximos passos podem fazer algo mais num estado futuro). Finalmente, o terceiro inteiro é o próximo valor do state a ir dentro da próxima iteração.

Uma vez que estas notações arbitrárias são de certa forma difíceis de lembrar, deve definir um conjunto de constantes que deve usar no lugar dos valores numéricos diretos. Os nomes deles podem ser NOTURN, LEFT, RIGHT etc. [!scala]Simplesmente declare-as a usar keyword val no lugar de var. Deve sempre usar val no lugar de var quando possível de qualquer forma.[/!] [!java]Os modificadores final static antes do tipo dele é a forma de marcar variáveis como constantes em Java. Deve escrever, por exemplo, static final int NOTURN=1; Desculpe pela complesxidade desta notação. [/!] [!python]Por convenção, tais variáveis constantes são escritas em maiúsculas no python. Tecnicamente, ainda pode modificá-las, mas isto é uma má ideia.[/!] Deve escrevê-las fora de qualquer método para que elas se tornem visíveis globalmente.

Usar tais constantes ajuda em muito a fazer o código mais legível. Compare os dois blocos de código a seguir:

[!java]if (rule[state][currentColor][NEXT_MOVE] == LEFT) {[/!][!python]if rule[state][currentColor][NEXT_MOVE] == LEFT:[/!][!scala]if (rule(state)(currentColor)(NEXT_MOVE) == LEFT) {[/!]
    left()[!java];[/!]
[!java|scala]}[/!]

Isto é muito mais fácil de se ler (embora seja mais longo) do que o seguinte:

[!java]if (rule[i][j][1] == 2) {[/!][!python]if rule[i][j][1] == 2:[/!][!scala]if (rule(i)(j)(1) == 2) {[/!]
    left()[!java];[/!]
[!java|scala]}[/!]
[!python]

Finalmente, provavelmente vai escrever um ramo elif para a condição STOP também. Ter um ramo else a mostrar uma mensagem de erro tal como "unknown case" é uma boa prática: faz as suas suposições sobre o seu código mais explícitas e tem uma mensagem de erro se elas falharem. Quando fizer isto, o próximo problema vai ser que não tem nada para fazer no caso do STOP, mas python não permite que escreva ramos elif vazios. Deve usar a instrução pass como substituto, que diz ao python que tem um ramo aqui e que não faz nada.

[/!] [!java|scala]

Provavelmente deve usar uma construção [!java]switch case[/!][!scala]pattern matching[/!] para manter o seu código legível. Se não se lembra o que isto é, veja este exercício.

[/!]

Agora tem informação o suficiente para conseguir.

Notas bibliográficas

De acordo com a wikipédia, os turmites foram inventados independentemente no final dos anos oitenta. Foi provado que turmites em geral são exatamente equivalentes em capacidade a máquinas de turing uni-dimensionais com uma fita infinita, pois um pode simular o outro. Isto significa que qualquer programa que possa conceber pode teoricamente ser executado neste aparelho...