Desafio

Dada uma imagem raster colorida * com a mesma largura e altura, produza a imagem transformada no mapa de gatos de Arnold . (* detalhes veja abaixo)

Definição

Dado o tamanho da imagem N, assumimos que as coordenadas de um pixel são dadas como números entre 0e N-1.

O mapa de gatos de Arnold é então definido da seguinte forma:

Um pixel nas coordenadas [x,y]é movido para [(2*x + y) mod N, (x + y) mod N].

Isso não passa de uma transformação linear no toro: a parte amarela, violeta e verde é mapeada de volta para o quadrado inicial devido ao mod N.

Este mapa (vamos chamá-lo f) possui as seguintes propriedades:

• É bijetivo , isso significa reversível: é uma transformação linear com a matriz [[2,1],[1,1]]. Como tem determinante 1ee possui apenas entradas inteiras, o inverso também possui apenas entradas inteiras e é dado por [[1,-1],[-1,2]], isso significa que também é bijetivo nas coordenadas inteiras.

• É um elemento de torção do grupo de mapas de N x Nimagens bijetivos , ou seja, se você o aplicar o suficiente, você receberá a imagem original de volta: f(f(...f(x)...)) = xA quantidade de vezes que o mapa aplicado a si próprio resulta na identidade é garantida como menor ou igual a 3*N. A seguir, é possível ver a imagem de um gato após um determinado número de aplicativos iterados do mapa de gatos de Arnold e uma animação de como é um aplicativo repetido:

Detalhes

• Seu programa não precisa necessariamente lidar com imagens, mas matrizes / matrizes 2D, strings ou estruturas 2D similares também são aceitáveis.

• Não importa se o seu (0,0)ponto está no canto inferior esquerdo ou no canto superior esquerdo. (Ou em qualquer outro canto, se isso for mais conveniente no seu idioma.) Especifique qual convenção você usa ao enviar.

Casos de teste

Em forma de matriz ( [1,2,3,4]é a linha superior, 1tem índice (0,0), 2tem índice (1,0), 5tem índice (0,1))

 1     2     3     4
 5     6     7     8
 9    10    11    12
13    14    15    16

maps to:

 1    14    11     8
12     5     2    15
 3    16     9     6
10     7     4    13

 --------------------

 1     2     3
 4     5     6
 7     8     9

 map to:

 1     8     6
 9     4     2
 5     3     7

Como imagem (canto inferior esquerdo (0,0)):

Geléia , 9 bytes

Zṙ"JC$µ2¡

Experimente online! As coordenadas são como na resposta.

Explicação

      µ2¡   Twice:
Z             Transpose, then
 ṙ"           Rotate rows left by
   JC$          0, -1, -2, -3, …, 1-n units.

Isso envolve a matriz em uma direção e depois na outra.

MATL , 23 bytes

tt&n:qt&+&y\tb+&y\b*+Q(

O (0,0)ponto está no canto superior esquerdo, como nos exemplos no texto do desafio.

Experimente online!

Explicação

Uma matriz em MATL pode ser indexada com um único índice em vez de dois. Isso é chamado de indexação linear e usa a ordem principal da coluna . Isso é ilustrado pela seguinte matriz 4 × 4, na qual o valor em cada entrada coincide com seu índice linear:

1   5   9  13
2   6  10  14
3   7  11  15
4   8  12  16

Existem duas abordagens semelhantes para implementar o mapeamento no desafio:

1. Crie uma matriz de indexação que represente o mapeamento inverso de Arnold em índices lineares e use-a para selecionar os valores da matriz original. Para o caso 4 × 4, a matriz de indexação seria

    1  8 11 14
   15  2  5 12
    9 16  3  6
    7 10 13  4
   

   dizendo que, por exemplo, o original 5em x = 2, y = 1 vai para x = 3, y = 2. Essa operação é chamada de indexação de referência : use a matriz de indexação para dizer qual elemento escolher da matriz original. Este é o functon ), que recebe duas entradas (em sua configuração padrão).

2. Crie uma matriz de indexação que represente o mapeamento direto de Arnold em índices lineares e use-a para gravar os valores na matriz original. Para o caso 4 × 4, a matriz de indexação seria

    1 10  3 12
    6 15  8 13
   11  4  9  2
   16  5 14  7
   

   informando que a entrada x = 2, y = 1 da nova matriz será substituída na entrada com índice linear 10, ou seja, x = 3, y = 2. Isso é chamado de indexação de atribuição : use a matriz de indexação, uma matriz de dados e a matriz original e escreva os dados na matriz original nos índices especificados. Essa é a função (, que recebe três entradas (em sua configuração padrão).

O método 1 é mais direto, mas o método 2 acabou sendo mais curto.

tt     % Take the input implicitly and push two more copies
&n     % Get its size as two (equal) numbers: N, N
:qt    % Push range [0  1 ... N-1] twice. This represents the original x values
&+     % Matrix of all pairwise additions. This represents x+y
&y     % Push a copy of N onto the top of the stack
\      % Modulo. This is the new y coordinate: y_new
t      % Push another copy
b+     % Bubble up the remaining copy of [0 1 ... N-1] and add. This is 2*x+y
&y     % Push a copy of N onto the top of the stack
\      % Modulo. This is the new x coordinate: x_new
b*+    % Bubble up the remaining copy of N, multiply, add. This computes
       % x_new*N+y_new, which is the linear index for those x_new, y_new 
Q      % Add 1, because MATL uses 1-based indexing
(      % Assigmnent indexing: write the values of the original matrix into
       % (another copy of) the original matrix at the entries given by the
       % indexing matrix. Implicitly display the result

Mathematica, 44 bytes

(n=MapIndexed[RotateLeft[#,1-#2]&,#]&)@*n

Uma porta do fantástico algoritmo de Lynn . Há um caractere invisível de 3 bytes, U + F3C7 na codificação UTF-8, antes da última ]; O Mathematica o processa como um sobrescrito Te leva a transposição de uma matriz.

Mathematica, 54 bytes

Table[#2[[Mod[2x-y-1,#]+1,Mod[y-x,#]+1]],{x,#},{y,#}]&

Função sem nome, recebendo dois argumentos, um número inteiro positivo #e uma matriz 2D #2de dimensões #xe #retornando uma matriz 2D de forma semelhante. Como no caso de teste fornecido, o ponto com coordenadas {0,0} está no canto superior esquerdo e o eixo x é horizontal. Implementação direta usando o inverso [[1,-1],[-1,2]]mencionado na pergunta, com um -1na primeira coordenada para explicar o fato de que as matrizes são inerentemente indexadas 1 no Mathematica. Se não pudermos considerar a dimensão da matriz como um argumento adicional, essa solução se tornará nove bytes mais longa (substitua o primeiro #- não o #2- com a=Length@#e todos os #s subsequentes por as).

Python 2, 89 82 77 73 bytes

def f(a):exec'a=[l[-i:]+l[:-i]for i,l in enumerate(zip(*a))];'*2;return a

Entrada é uma lista de listas
A sequência dentro do exec transpõe a lista de listas e gira ciclicamente cada lista pelo índice de linhas (com base em 0 - a terceira linha é girada 2 vezes para a direita).
Este processo é realizado 2 vezes na entrada.

+4 bytes que farão a transformação N vezes

def f(a,n):exec'a=[l[-i:]+l[:-i]for i,l in enumerate(zip(*a))];'*2*n;return a

Haskell, 55 bytes

m#n|r<-[0..n-1]=[[m!!mod(2*y-x)n!!mod(x-y)n|x<-r]|y<-r]

Exemplo de uso: [[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]] # 4-> [[1,14,11,8],[12,5,2,15],[3,16,9,6],[10,7,4,13]].

0,0é o canto superior esquerdo. Isso usa a transformação inversa.

Python, 69 bytes

lambda M:eval("[r[-i:]+r[:-i]for i,r in enumerate(zip(*"*2+"M))]))]")

Uma melhoria no método de transposição e deslocamento duas vezes de Rod . Aplica a operação M -> [r[-i:]+r[:-i]for i,r in enumerate(zip(*M))]duas vezes criando e avaliando a sequência

[r[-i:]+r[:-i]for i,r in enumerate(zip(*[r[-i:]+r[:-i]for i,r in enumerate(zip(*M))]))]

Isso supera uma transformação direta (70 bytes), assumindo que a imagem é quadrada e seu comprimento pode ser tomado como entrada:

lambda M,n:[[M[(2*j-i)%n][(i-j)%n]for i in range(n)]for j in range(n)]

Macro ImageJ, 29 bytes

v=getPixel((x+y)%w,(2*y+x)%h)

• Abrir imagem de Lena
• No menu Process, selecione Math / Macro ...

Java, 160

Golfe:

int[][]f(int[][]m){int x=0,y,l=m.length,r[][]=new int[l][];for(;x<l;++x)r[x]=new int[l];for(x=0;x<l;++x)for(y=0;y<l;++y)r[(x+y)%l][(2*x+y)%l]=m[y][x];return r;}

Ungolfed:

  int[][] f(int[][] m) {
    int x = 0, y, l = m.length, r[][] = new int[l][];
    for (; x < l; ++x) {
      r[x] = new int[l];
    }
    for (x = 0; x < l; ++x) {
      for (y = 0; y < l; ++y) {
        r[(x + y) % l][(2 * x + y) % l] = m[y][x];
      }
    }
    return r;
  }