DIRS = "NESW"
MOVES = {
    "N": (-1, 0),
    "S": (1, 0),
    "W": (0, -1),
    "E": (0, 1)
}


def run_langton(rules, size):
    grid = [[0 for _ in range(size)] for __ in range(size)]  # grid inicial, todos espaços são zero
    pos = size // 2, size // 2  # começar no centro

    direction = "N"  # começa apontando para o norte

    count = 0  # armazena número de passos

    while True:
        count += 1

        # mudar cor da célula atual
        grid[pos[0]][pos[1]] = (grid[pos[0]][pos[1]] + 1) % len(rules)

        # movimento da formiga, atualiza posição
        pos = pos[0] + MOVES[direction][0], pos[1] + MOVES[direction][1]

        if not (0 <= pos[0] < size and 0 <= pos[1] < size):
            break  # formiga saiu do grid

        # rotação dependendo da cor da nova célula
        rotation = 1 if rules[grid[pos[0]][pos[1]]] == "R" else -1
        direction = DIRS[(DIRS.index(direction) + rotation) % len(DIRS)]

    return count, grid