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 0
i 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 wyznacznik1
i 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 N
obrazów, co oznacza, że jeśli zastosujesz go wystarczająco wiele razy, odzyskasz oryginalny obraz:f(f(...f(x)...)) = x
Ilość przypadków, w których mapa zastosowana do siebie daje w wyniku tożsamość, jest mniejsza lub równa3*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, 1
ma indeks (0,0)
, 2
ma indeks (1,0)
, 5
ma 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)
):
Odpowiedzi:
Galaretka , 9 bajtów
Wypróbuj online! Współrzędne są jak w odpowiedzi.
Wyjaśnienie
To owijanie tnie matrycę w jednym kierunku, a potem w drugim.
źródło
MATL , 23 bajty
(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:
Istnieją dwa podobne podejścia do wdrożenia mapowania w wyzwaniu:
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
mówiąc, że na przykład oryginał
5
przy 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).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
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.
źródło
Mathematica, 44 bajty
Port fantastycznego algorytmu Lynn . Przed ostatnim jest niewidoczny 3-bajtowy znak U + F3C7 w kodowaniu UTF-8
]
; Mathematica renderuje go jako indeks górnyT
i przyjmuje transpozycję macierzy.Mathematica, 54 bajty
Funkcja bez nazwy, która przyjmuje dwa argumenty, dodatnią liczbę całkowitą
#
i tablicę 2D#2
o 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-1
pierwszą 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 naa
s).źródło
Python 2,
89827773 bajtówDane 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
źródło
Haskell, 55 bajtów
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,0
to lewy górny róg. Wykorzystuje odwrotną transformację.źródło
Python, 69 bajtów
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ągTo 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:
źródło
Makro ImageJ, 29 bajtów
źródło
v=getPixel((2*y-x)%w,(x-y)%h)
.2*x+y
zmieniono na2*y+x
f(x,y) = (2x+y, x+y)
tej odwrotnej transformacji jest opisany przezf^(-1) = (x-y, 2y-x)
. (Mój drugi komentarz był niepoprawny.) Więc twój kod powinien być sholdv=getPixel((x-y)%w,(2*y-x)%h)
.Java, 160
Gra w golfa:
Nie golfowany:
źródło