Tantangan

Diberi gambar raster warna * dengan lebar dan tinggi yang sama, menampilkan gambar yang diubah di bawah peta kucing Arnold . (* detail lihat di bawah)

Definisi

Mengingat ukuran gambar, Nkami mengasumsikan bahwa koordinat piksel diberikan sebagai angka antara 0dan N-1.

Peta kucing Arnold kemudian didefinisikan sebagai berikut:

Piksel pada koordinat [x,y]dipindahkan ke [(2*x + y) mod N, (x + y) mod N].

Ini tidak lain adalah transformasi linear pada torus: Bagian kuning, ungu dan hijau dipetakan kembali ke kotak awal karena mod N.

Peta ini (sebut saja f) memiliki properti berikut:

• Ini adalah kata sifat , itu berarti reversibel: Ini adalah transformasi linear dengan matriks [[2,1],[1,1]]. Karena memiliki determinan 1dan dan hanya memiliki entri bilangan bulat, kebalikannya juga hanya memiliki entri bilangan bulat dan diberikan oleh [[1,-1],[-1,2]], ini berarti ia juga bijektif pada koordinat bilangan bulat.

• Ini adalah elemen puntir dari kelompok peta bijektif N x Ngambar, yang berarti jika Anda menerapkannya berkali-kali, Anda akan mendapatkan gambar asli kembali: f(f(...f(x)...)) = xJumlah kali peta diterapkan untuk dirinya sendiri menghasilkan identitas dijamin kurang atau sama dengan 3*N. Berikut ini Anda dapat melihat gambar kucing setelah sejumlah aplikasi iterated dari peta kucing Arnold , dan animasi seperti apa aplikasi yang berulang itu terlihat:

Detail

• Program Anda tidak harus berurusan dengan gambar, tetapi 2D-array / matriks, string atau struktur 2D serupa juga dapat diterima.

• Tidak masalah apakah (0,0)titik Anda ada di kiri bawah atau di kiri atas. (Atau di sudut lain, jika ini lebih nyaman dalam bahasa Anda.) Silakan tentukan konvensi apa yang Anda gunakan dalam kiriman Anda.

Testcases

Dalam bentuk matriks ( [1,2,3,4]adalah baris teratas, 1memiliki indeks (0,0), 2memiliki indeks (1,0), 5memiliki indeks (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

Seperti gambar (kiri bawah adalah (0,0)):

Jelly , 9 byte

Zṙ"JC$µ2¡

Cobalah online! Koordinat seperti pada jawaban.

Penjelasan

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

Ini membungkus-geser matriks dalam satu arah, lalu yang lain.

MATL , 23 byte

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

The (0,0)point kiri atas, seperti pada contoh dalam teks tantangan.

Cobalah online!

Penjelasan

Matriks dalam MATL dapat diindeks dengan satu indeks, bukan dua. Ini disebut pengindeksan linear , dan menggunakan urutan kolom-utama . Ini diilustrasikan oleh matriks 4 × 4 berikut, di mana nilai pada setiap entri bertepatan dengan indeks liniernya:

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

Ada dua pendekatan serupa untuk mengimplementasikan pemetaan dalam tantangan:

1. Bangun matriks pengindeksan yang mewakili pemetaan terbalik Arnold pada indeks linier, dan gunakan untuk memilih nilai dari matriks asli. Untuk kasus 4x4, matriks pengindeksan akan

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

   mengatakan bahwa misalnya aslinya 5di x = 2, y = 1 pergi ke x = 3, y = 2. Operasi ini disebut pengindeksan referensi : gunakan matriks pengindeksan untuk mengetahui elemen mana yang harus dipilih dari matriks asli. Ini adalah functon ), yang mengambil dua input (dalam konfigurasi default-nya).

2. Bangun matriks pengindeksan yang mewakili pemetaan langsung Arnold pada indeks linier, dan gunakan untuk menulis nilai ke dalam matriks asli. Untuk kasus 4x4, matriks pengindeksan akan

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

   mengatakan bahwa entri x = 2, y = 1 dari matriks baru akan ditimpa ke entri dengan indeks linier 10, yaitu, x = 3, y = 2. Ini disebut pengindeksan tugas : gunakan matriks pengindeksan, matriks data dan matriks asli, dan tulis data ke dalam matriks asli pada indeks yang ditentukan. Ini adalah fungsi (, yang mengambil tiga input (dalam konfigurasi standarnya).

Metode 1 lebih mudah, tetapi metode 2 ternyata lebih pendek.

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 byte

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

Port dari algoritma Lynn yang fantastis . Ada karakter 3-byte yang tidak terlihat, U + F3C7 dalam pengkodean UTF-8, sebelum yang terakhir ]; Mathematica menerjemahkannya sebagai superscript T, dan ia mengambil transpos dari sebuah matriks.

Mathematica, 54 byte

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

Fungsi yang tidak disebutkan namanya mengambil dua argumen, bilangan bulat positif #dan array 2D #2dimensi #x #, dan mengembalikan array 2D dengan bentuk yang sama. Seperti pada test case yang diberikan, titik dengan koordinat {0,0} berada di kiri atas dan sumbu x horizontal. Implementasi langsung menggunakan invers yang [[1,-1],[-1,2]]disebutkan dalam pertanyaan, dengan -1koordinat pertama untuk memperhitungkan fakta bahwa array secara inheren 1-diindeks dalam Mathematica. Jika kita tidak diizinkan untuk mengambil dimensi matriks sebagai argumen tambahan, maka solusi ini menjadi sembilan byte lebih lama (ganti yang pertama# — bukan yang #2— dengan a=Length@#dan semua yang berikutnya #dengan as).

Python 2, 89 82 77 73 byte

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

Input adalah daftar daftar
. String di dalam eksekutif mengubah posisi daftar dan memutar setiap daftar secara berurutan dengan indeks garis (0 berbasis - baris 3 diputar 2 kali ke kanan).
Proses ini dilakukan 2 kali untuk input.

+4 byte yang akan melakukan transformasi N kali

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

Haskell, 55 byte

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

Contoh penggunaan: [[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,0adalah sudut kiri atas. Ini menggunakan transformasi terbalik.

Python, 69 byte

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

Peningkatan pada metode transpos-dan-shift-dua kali Rod . Terapkan operasi M -> [r[-i:]+r[:-i]for i,r in enumerate(zip(*M))]dua kali dengan membuat dan mengevaluasi string

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

Ini secara sempit mengalahkan transformasi langsung (70 byte), dengan asumsi gambar berbentuk bujur sangkar dan panjangnya dapat diambil sebagai input:

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

ImageJ macro, 29 byte

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

• Buka gambar Lena
• Dari menu Proses pilih Matematika / Makro ...

Java, 160

Golf:

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

Tidak Disatukan:

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