Given a colour raster image* with the same width and height, output the image transformed under Arnold's cat map. (*details see below)
Given the size of the image
N we assume that the coordinates of a pixel are given as numbers between
Arnold's cat map is then defined as follows:
A pixel at coordinates
[x,y] is moved to
[(2*x + y) mod N, (x + y) mod N].
This is nothing but a linear transform on torus: The yellow, violet and green part get mapped back onto the initial square due to the
This map (let's call it
f) has following properties:
It is bijective, that means reversible: It is a linear transformation with the matrix
[[2,1],[1,1]]. Since it has determinant
1and and it has only integer entries, the inverse also has only integer entries and is given by
[[1,-1],[-1,2]], this means it is also bijective on integer coordinates.
It is a torsion element of the group of bijective maps of
N x Nimages, that means if you apply it sufficiently many times, you will get the original image back:
f(f(...f(x)...)) = xThe amount of times the map applied to itself results in the identity is guaranteed to be less or equal to
3*N. In the following you can see the image of a cat after a given number of iterated applications of Arnold's cat map, and an animation of what a repeated application looks like:
Your program does not necessarily have to deal with images, but 2D-arrays/matrices, strings or similar 2D-structures are acceptable too.
It does not matter whether your
(0,0)point is on the bottom left or on the top left. (Or in any other corner, if this is more convenient in your language.) Please specify what convention you use in your submission.
In matrix form (
[1,2,3,4] is the top row,
1 has index
2 has index
5 has index
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
As image (bottom left is