Arnold's Cat Map

Question

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

Answer 1

Jelly, 9 bytes

Zṙ"JC$µ2¡

Try it online! The coordinates are as in the answer.

Explanation

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

This wrap-shears the matrix in one direction, then the other.

Answer 2

MATL, 23 bytes

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

The (0,0) point is upper left, as in the examples in the challenge text.

Try it online!

Explanation

A matrix in MATL can be indexed with a single index instead of two. This is called linear indexing, and uses column-major order. This is illustrated by the following 4×4 matrix, in which the value at each entry coincides with its linear index:

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

There are two similar approaches to implement the mapping in the challenge:

1. Build an indexing matrix that represents Arnold's inverse mapping on linear indices, and use it to select the values from the original matrix. For the 4×4 case, the indexing matrix would be

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

   telling that for example the original 5 at x=2, y=1 goes to x=3, y=2. This operation is called reference indexing: use the indexing matrix to tell which element to pick from the original matrix. This is functon ), which takes two inputs (in its default configuration).

2. Build an indexing matrix that represents Arnold's direct mapping on linear indices, and use it to write the values into the original matrix. For the 4×4 case, the indexing matrix would be

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

   telling that the entry x=2, y=1 of the new matrix will be overwritten onto the entry with linear index 10, that is, x=3, y=2. This is called assignment indexing: use the indexing matrix, a data matrix and the original matrix, and write the data onto the original matrix at the specified indices. This is function (, which takes three inputs (in its default configuration).

Method 1 is more straightforward, but method 2 turned out to be shorter.

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

Answer 3

Mathematica, 44 bytes

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

A port of Lynn's fantastic algorithm. There's an invisible 3-byte character, U+F3C7 in the UTF-8 encoding, before the last ]; Mathematica renders it as a superscript T, and it takes the transpose of a matrix.

Mathematica, 54 bytes

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

Unnamed function taking two arguments, a positive integer # and a 2D array #2 of dimensions #x#, and returning a 2D array of similar shape. As in the given test case, the point with coordinates {0,0} is in the upper left and the x-axis is horizontal. Straightforward implementation using the inverse [[1,-1],[-1,2]] mentioned in the question, with a -1 in the first coordinate to account for the fact that arrays are inherently 1-indexed in Mathematica. If we're not allowed to take the dimension of the matrix as an additional argument, then this solution becomes nine bytes longer (replace the first #—not the #2—with a=Length@# and all the subsequent #s with as).

Answer 4

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

Input is a list of lists
The string inside the exec transpose the list of lists and cyclically rotate each list by the line index (0 based - 3rd line is rotated 2 times to the right).
This process is done 2 times to the input.

+4 bytes that will do the transformation N times

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

Answer 5

Haskell, 55 bytes

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

Usage example: [[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 is the upper left corner. This uses the inverse transformation.

Answer 6

ImageJ macro, 29 bytes

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

• Open image of Lena
• From Process menu select Math / Macro...

Answer 7

Python, 69 bytes

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

An improvement on Rod's transpose-and-shift-twice method. Applies the operation M -> [r[-i:]+r[:-i]for i,r in enumerate(zip(*M))] twice by creating and evaluating the string

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

This narrowly beats out a direct transformation (70 bytes), assuming the image is square and its length can be taken as input:

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

Answer 8

Java, 160

Golfed:

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;
  }