A formiga de Langton

A formiga de Langton é uma máquina de Turing bidimensional inventada no final da década de 1980. A formiga começa em uma grade de células pretas e brancas e segue um conjunto simples de regras que produz um comportamento emergente complexo.

A formiga pode se mover em qualquer uma das quatro direções cardeais a cada passo. A formiga se move de acordo com as seguintes regras:

• Em uma casa branca (1), vire 90° para a direita, inverta a cor da casa e avance uma unidade.
• Em uma casa preta (0), vire 90° para a esquerda, inverta a cor da casa e avance uma unidade.
• A grade não tem limites e, portanto, se a formiga se mover para fora das bordas, a grade deverá ser expandida com 0s, mantendo a forma retangular.

Crie uma função Langton's Ant com os seguintes parâmetros:

grid - a two-dimensional list of 1s and 0s
# representing white and black cells respectively

column - horizontal position of the ant

row - ant's vertical position

n - number of iterations

direction - ant's current direction
# 0 - north, 1 - east, 2 - south, 3 - west
# default value will be 0

... e retorne o estado da grade após n iterações.

Exemplos

langtons_ant([[1]], 0, 0, 1, 0) ➞ [[0, 0]]
# Initially facing north (0), at the first iteration the ant turns
# right because it stands on a white square, 1. After that, it flips
# the square and moves forward.

langtons_ant([[0]], 0, 0, 1, 0) ➞ [[0, 1]]

langtons_ant([[0, 0, 0], [0, 0, 0], [0, 0, 0]], 2, 2, 10, 1) ➞ [[0, 0, 0, 0], [0, 1, 1, 0], [0, 1, 1, 1], [0, 0, 0, 1]]

Observações

N/A