Reto
Dada una imagen ráster de color * con el mismo ancho y alto, genera la imagen transformada bajo el mapa del gato de Arnold . (* detalles ver abajo)
Definición
Dado el tamaño de la imagen N
, suponemos que las coordenadas de un píxel se dan como números entre 0
y N-1
.
El mapa del gato de Arnold se define de la siguiente manera:
Se [x,y]
mueve un píxel en las coordenadas [(2*x + y) mod N, (x + y) mod N]
.
Esto no es más que una transformación lineal en el toro: la parte amarilla, violeta y verde se mapea de nuevo en el cuadrado inicial debido a mod N
.
Este mapa (llamémoslo f
) tiene las siguientes propiedades:
Es biyectivo , eso significa reversible: es una transformación lineal con la matriz
[[2,1],[1,1]]
. Como tiene determinante1
y solo tiene entradas enteras, el inverso también tiene solo entradas enteras y está dado por[[1,-1],[-1,2]]
, esto significa que también es biyectivo en coordenadas enteras.Es un elemento de torsión del grupo de mapas biyectivos de
N x N
imágenes, lo que significa que si lo aplica muchas veces, recuperará la imagen original:f(f(...f(x)...)) = x
la cantidad de veces que el mapa aplicado a sí mismo da como resultado la identidad será menor. o igual a3*N
. A continuación, puede ver la imagen de un gato después de un número determinado de aplicaciones iteradas del mapa del gato de Arnold , y una animación de cómo se ve una aplicación repetida:
Detalles
Su programa no necesariamente tiene que lidiar con imágenes, pero también son aceptables matrices / matrices 2D, cadenas o estructuras 2D similares.
No importa si su
(0,0)
punto está en la parte inferior izquierda o en la parte superior izquierda. (O en cualquier otro rincón, si esto es más conveniente en su idioma). Especifique qué convención utiliza en su envío.
Casos de prueba
En forma de matriz ( [1,2,3,4]
es la fila superior, 1
tiene índice (0,0)
, 2
tiene índice (1,0)
, 5
tiene í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 imagen (abajo a la izquierda (0,0)
):
Respuestas:
Jalea , 9 bytes
Pruébalo en línea! Las coordenadas son como en la respuesta.
Explicación
Esto envuelve la matriz en una dirección, luego en la otra.
fuente
MATL , 23 bytes
El
(0,0)
punto está en la parte superior izquierda, como en los ejemplos en el texto del desafío.Pruébalo en línea!
Explicación
Una matriz en MATL puede indexarse con un solo índice en lugar de dos. Esto se llama indexación lineal y utiliza el orden de columnas principales . Esto se ilustra en la siguiente matriz 4 × 4, en la que el valor en cada entrada coincide con su índice lineal:
Hay dos enfoques similares para implementar el mapeo en el desafío:
Cree una matriz de indexación que represente la asignación inversa de Arnold en índices lineales y úsela para seleccionar los valores de la matriz original. Para el caso 4 × 4, la matriz de indexación sería
diciendo que, por ejemplo, el original
5
en x = 2, y = 1 va a x = 3, y = 2. Esta operación se denomina indexación de referencia : use la matriz de indexación para indicar qué elemento elegir de la matriz original. Esta es la función)
, que toma dos entradas (en su configuración predeterminada).Cree una matriz de indexación que represente la asignación directa de Arnold en índices lineales y úsela para escribir los valores en la matriz original. Para el caso 4 × 4, la matriz de indexación sería
diciendo que la entrada x = 2, y = 1 de la nueva matriz se sobrescribirá en la entrada con índice lineal
10
, es decir, x = 3, y = 2. Esto se llama indexación de asignación : use la matriz de indexación, una matriz de datos y la matriz original, y escriba los datos en la matriz original en los índices especificados. Esta es la función(
, que toma tres entradas (en su configuración predeterminada).El método 1 es más sencillo, pero el método 2 resultó ser más corto.
fuente
Mathematica, 44 bytes
Un puerto del fantástico algoritmo de Lynn . Hay un carácter invisible de 3 bytes, U + F3C7 en la codificación UTF-8, antes del último
]
; Mathematica lo representa como un superíndiceT
y toma la transposición de una matriz.Mathematica, 54 bytes
Función sin nombre que toma dos argumentos, un entero positivo
#
y una matriz 2D#2
de dimensiones#
x#
, y devuelve una matriz 2D de forma similar. Como en el caso de prueba dado, el punto con coordenadas {0,0} está en la esquina superior izquierda y el eje x es horizontal. Implementación directa usando el inverso[[1,-1],[-1,2]]
mencionado en la pregunta, con una-1
en la primera coordenada para tener en cuenta el hecho de que las matrices están inherentemente indexadas en 1 en Mathematica. Si no se nos permite tomar la dimensión de la matriz como argumento adicional, entonces esta solución se alargará nueve bytes (reemplace el primero#
—no el#2
—cona=Length@#
y todos los#
s posteriores cona
s).fuente
Python 2,
89827773 bytesLa entrada es una lista de listas
La cadena dentro del archivo ejecutivo transpone la lista de listas y rota cíclicamente cada lista por el índice de línea (basado en 0 - la tercera línea se gira 2 veces a la derecha).
Este proceso se realiza 2 veces a la entrada.
+4 bytes que harán la transformación N veces
fuente
Haskell, 55 bytes
Ejemplo 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
es la esquina superior izquierda Esto usa la transformación inversa.fuente
Python, 69 bytes
Una mejora en el método de transposición y desplazamiento de Rod dos veces . Aplica la operación
M -> [r[-i:]+r[:-i]for i,r in enumerate(zip(*M))]
dos veces creando y evaluando la cadenaEsto supera por poco una transformación directa (70 bytes), suponiendo que la imagen es cuadrada y su longitud se puede tomar como entrada:
fuente
Macro ImageJ, 29 bytes
fuente
v=getPixel((2*y-x)%w,(x-y)%h)
.2*x+y
cambiado a2*y+x
f(x,y) = (2x+y, x+y)
esta transformación inversa se describe porf^(-1) = (x-y, 2y-x)
. (Mi otro comentario fue incorrecto). Entonces su código debe serv=getPixel((x-y)%w,(2*y-x)%h)
.Java, 160
Golfizado:
Sin golf:
fuente