Wyzwanie

Biorąc pod uwagę kolorowy obraz rastrowy * o tej samej szerokości i wysokości, wydrukuj obraz przekształcony pod mapą kota Arnolda . (* szczegóły patrz poniżej)

Definicja

Biorąc pod uwagę rozmiar obrazu N, zakładamy, że współrzędne piksela są podane jako liczby pomiędzy 0i N-1.

Mapa kota Arnolda jest następnie definiowana w następujący sposób:

Piksel o współrzędnych [x,y]jest przenoszony do [(2*x + y) mod N, (x + y) mod N].

To nic innego jak liniowa transformacja torusa: część żółta, fioletowa i zielona są odwzorowywane z powrotem na początkowy kwadrat z powodu mod N.

Ta mapa (nazwijmy ją f) ma następujące właściwości:

• Jest bijectywny , co oznacza odwracalne: jest to transformacja liniowa z matrycą [[2,1],[1,1]]. Ponieważ ma on wyznacznik 1i ma tylko wpisy liczb całkowitych, odwrotność ma także tylko wpisy liczb całkowitych i jest podany przez [[1,-1],[-1,2]], co oznacza, że ​​jest również brzemienny we współrzędne liczb całkowitych.

• Jest to element skrętny grupy bijectywnych map N x Nobrazów, co oznacza, że ​​jeśli zastosujesz go wystarczająco wiele razy, odzyskasz oryginalny obraz: f(f(...f(x)...)) = xIlość przypadków, w których mapa zastosowana do siebie daje w wyniku tożsamość, jest mniejsza lub równa 3*N. Poniżej możesz zobaczyć obraz kota po określonej liczbie iterowanych aplikacji mapy kota Arnolda oraz animację tego, jak wygląda powtarzana aplikacja:

Detale

• Twój program niekoniecznie musi radzić sobie z obrazami, ale akceptowalne są również tablice / macierze 2D, łańcuchy lub podobne struktury 2D.

• Nie ma znaczenia, czy Twój (0,0)punkt znajduje się w lewym dolnym rogu, czy w lewym górnym rogu. (Lub w dowolnym innym rogu, jeśli jest to wygodniejsze w Twoim języku.) Proszę określić, jakiej konwencji używasz w swoim zgłoszeniu.

Przypadki testowe

W postaci macierzy ( [1,2,3,4]jest górnym wierszem, 1ma indeks (0,0), 2ma indeks (1,0), 5ma 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

Jak obrazek (u dołu po lewej (0,0)):

Galaretka , 9 bajtów

Zṙ"JC$µ2¡

Wypróbuj online! Współrzędne są jak w odpowiedzi.

Wyjaśnienie

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

To owijanie tnie matrycę w jednym kierunku, a potem w drugim.

MATL , 23 bajty

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

(0,0)Punkt górny lewy, jak w przykładach w tekście wyzwanie.

Wypróbuj online!

Wyjaśnienie

Macierz w MATL może być indeksowana za pomocą jednego indeksu zamiast dwóch. Nazywa się to indeksowaniem liniowym i wykorzystuje kolejność według kolumn . Ilustruje to następująca macierz 4 × 4, w której wartość przy każdym wejściu pokrywa się z jej indeksem liniowym:

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

Istnieją dwa podobne podejścia do wdrożenia mapowania w wyzwaniu:

1. Zbuduj macierz indeksującą reprezentującą odwrotne odwzorowanie Arnolda na indeksach liniowych i użyj jej do wybrania wartości z oryginalnej macierzy. W przypadku 4 × 4 macierz indeksowania byłaby

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

   mówiąc, że na przykład oryginał 5przy x = 2, y = 1 idzie do x = 3, y = 2. Ta operacja nazywa się indeksowaniem referencyjnym : użyj macierzy indeksowania, aby określić, który element wybrać z oryginalnej macierzy. Jest to funkcja ), która pobiera dwa wejścia (w domyślnej konfiguracji).

2. Zbuduj macierz indeksującą, która reprezentuje bezpośrednie mapowanie Arnolda na indeksach liniowych, i użyj jej do zapisania wartości w oryginalnej macierzy. W przypadku 4 × 4 macierz indeksowania byłaby

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

   mówiąc, że wpis x = 2, y = 1 nowej macierzy zostanie zastąpiony wpisem indeksem liniowym 10, to znaczy x = 3, y = 2. Nazywa się to indeksowaniem przypisań : użyj matrycy indeksującej, macierzy danych i oryginalnej macierzy i zapisz dane na oryginalnej macierzy przy określonych indeksach. Jest to funkcja (, która pobiera trzy wejścia (w domyślnej konfiguracji).

Metoda 1 jest prostsza, ale metoda 2 okazała się krótsza.

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 bajty

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

Port fantastycznego algorytmu Lynn . Przed ostatnim jest niewidoczny 3-bajtowy znak U + F3C7 w kodowaniu UTF-8 ]; Mathematica renderuje go jako indeks górny Ti przyjmuje transpozycję macierzy.

Mathematica, 54 bajty

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

Funkcja bez nazwy, która przyjmuje dwa argumenty, dodatnią liczbę całkowitą #i tablicę 2D #2o wymiarach #x #i zwraca tablicę 2D o podobnym kształcie. Podobnie jak w danym przypadku testowym, punkt o współrzędnych {0,0} znajduje się w lewym górnym rogu, a oś x jest pozioma. Prosta implementacja z wykorzystaniem odwrotności [[1,-1],[-1,2]]wspomnianej w pytaniu, z -1pierwszą współrzędną, aby uwzględnić fakt, że tablice są z natury indeksowane 1 w Mathematica. Jeśli nie wolno nam traktować wymiaru macierzy jako dodatkowego argumentu, wówczas to rozwiązanie staje się dziewięć bajtów dłuższe (zamień pierwszy #- nie na #2- a=Length@#i wszystkie kolejne #s na as).

Python 2, 89 82 77 73 bajtów

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

Dane wejściowe to lista list
. Ciąg wewnątrz exec transponuje listę list i cyklicznie obraca każdą listę o indeks linii (na podstawie 0 - 3. linia jest obracana 2 razy w prawo).
Ten proces jest wykonywany 2 razy na wejściu.

+4 bajty, które dokonają transformacji N razy

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

Haskell, 55 bajtów

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

Przykład użycia: [[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,0to lewy górny róg. Wykorzystuje odwrotną transformację.

Python, 69 bajtów

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

Ulepszenie metody Rod transpozycji i przesunięcia dwukrotnie . M -> [r[-i:]+r[:-i]for i,r in enumerate(zip(*M))]Dwukrotnie stosuje operację , tworząc i oceniając ciąg

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

To wąsko pokonuje bezpośrednią transformację (70 bajtów), zakładając, że obraz jest kwadratowy, a jego długość można przyjąć jako dane wejściowe:

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

Makro ImageJ, 29 bajtów

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

• Otwarty obraz Leny
• Z menu Process wybierz Math / Macro ...

Java, 160

Gra w golfa:

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

Nie golfowany:

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