21

4

### Challenge

Given a colour raster image* with the same width and height, output the image transformed under *Arnold's cat map*. (*details see below)

### Definition

Given the size of the image `N`

we assume that the coordinates of a pixel are given as numbers between `0`

and `N-1`

.

*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 `mod N`

.

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`1`

and 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 N`

images, that means if you apply it sufficiently many times, you will get the original image back:`f(f(...f(x)...)) = x`

The 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:

### Details

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.**

### Testcases

In matrix form (`[1,2,3,4]`

is the top row, `1`

has index `(0,0)`

, `2`

has index `(1,0)`

, `5`

has index `(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
```

As image (bottom left is `(0,0)`

):

1Poor Lena. I hope you kept iterating long enough – Luis Mendo – 2017-01-02T20:11:57.917

2Can we take the image size as input? Is it always square? – xnor – 2017-01-02T21:20:28.737

1Yes the image is always square, and I'm not sure about the size, is there anything

againstallowing that? – flawr – 2017-01-02T22:41:49.687