Herausforderung
Wenn Sie ein Farbrasterbild * mit der gleichen Breite und Höhe erhalten, geben Sie das Bild transformiert unter Arnolds Katzenkarte aus . (* Details siehe unten)
Definition
Bei der Größe des Bildes N
nehmen wir an, dass die Koordinaten eines Pixels als Zahlen zwischen 0
und angegeben werden N-1
.
Arnolds Katzenkarte wird dann folgendermaßen definiert:
Ein Pixel an Koordinaten [x,y]
wird nach verschoben [(2*x + y) mod N, (x + y) mod N]
.
Dies ist nichts anderes als eine lineare Transformation auf dem Torus: Der gelbe, violette und grüne Teil werden aufgrund von auf das Anfangsquadrat zurück abgebildet mod N
.
Diese Karte (nennen wir sie f
) hat folgende Eigenschaften:
Es ist bijektiv , das heißt reversibel: Es ist eine lineare Transformation mit der Matrix
[[2,1],[1,1]]
. Da es eine Determinante hat1
und nur ganzzahlige Einträge hat, hat das Inverse auch nur ganzzahlige Einträge und ist gegeben durch[[1,-1],[-1,2]]
, dh es ist auch bijektiv für ganzzahlige Koordinaten.Es ist ein Torsionselement der Gruppe der bijektiven Karten von
N x N
Bildern, dh wenn Sie es ausreichend oft anwenden, erhalten Sie das Originalbild zurück:f(f(...f(x)...)) = x
Die Häufigkeit, mit der die Karte auf sich selbst angewendet wird, führt garantiert zu einer geringeren Identität oder gleich3*N
. Im Folgenden sehen Sie das Bild einer Katze nach einer bestimmten Anzahl iterierter Anwendungen von Arnolds Katzenkarte und eine Animation, wie eine wiederholte Anwendung aussieht:
Einzelheiten
Ihr Programm muss sich nicht unbedingt mit Bildern befassen, aber auch 2D-Arrays / Matrizen, Strings oder ähnliche 2D-Strukturen sind akzeptabel.
Es spielt keine Rolle, ob sich Ihr
(0,0)
Punkt links unten oder links oben befindet. (Oder in einer anderen Ecke, wenn dies in Ihrer Sprache praktischer ist.) Bitte geben Sie an, welche Konvention Sie in Ihrer Einreichung verwenden.
Testfälle
In Matrixform ( [1,2,3,4]
ist die oberste Zeile, 1
hat Index(0,0)
, 2
hat Index (1,0)
, 5
hat 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
Als Bild (links unten ist (0,0)
):
quelle
Antworten:
Gelee , 9 Bytes
Probieren Sie es online! Die Koordinaten sind wie in der Antwort.
Erläuterung
Diese Wicklung schert die Matrix in die eine Richtung und dann in die andere.
quelle
MATL , 23 Bytes
Der
(0,0)
Punkt ist oben links, wie in den Beispielen im Herausforderungstext.Probieren Sie es online!
Erläuterung
Eine Matrix in MATL kann mit einem Index anstelle von zwei Indizes indiziert werden. Dies wird als lineare Indizierung bezeichnet und verwendet die Hauptreihenfolge der Spalten . Dies wird durch die folgende 4 × 4-Matrix veranschaulicht, in der der Wert an jedem Eintrag mit seinem linearen Index übereinstimmt:
Es gibt zwei ähnliche Ansätze, um das Mapping in der Challenge zu implementieren:
Erstellen Sie eine Indizierungsmatrix, die die inverse Abbildung von Arnold auf lineare Indizes darstellt, und wählen Sie die Werte aus der ursprünglichen Matrix aus. Für den 4 × 4-Fall wäre die Indexierungsmatrix
man sagt zum Beispiel, dass das Original
5
bei x = 2, y = 1 zu x = 3, y = 2 geht. Diese Operation wird als Referenzindizierung bezeichnet : Verwenden Sie die Indexierungsmatrix, um zu bestimmen, welches Element aus der ursprünglichen Matrix ausgewählt werden soll. Dies ist eine Funktion)
, die zwei Eingaben akzeptiert (in der Standardkonfiguration).Erstellen Sie eine Indexierungsmatrix, die Arnolds direkte Zuordnung zu linearen Indizes darstellt, und schreiben Sie die Werte in die ursprüngliche Matrix. Für den 4 × 4-Fall wäre die Indexierungsmatrix
Mitteilen , dass der Eintrag x = 2, y = 1 der neuen Matrix auf den Eintrag mit linearem Index überschrieben wird
10
, das, ist x = 3, y = 2 ist . Dies wird als Zuweisungsindizierung bezeichnet : Verwenden Sie die Indexierungsmatrix, eine Datenmatrix und die Originalmatrix, und schreiben Sie die Daten an den angegebenen Indizes auf die Originalmatrix. Dies ist die Funktion(
, die (in der Standardkonfiguration) drei Eingaben akzeptiert.Methode 1 ist einfacher, aber Methode 2 hat sich als kürzer herausgestellt.
quelle
Mathematica, 44 Bytes
Eine Portierung von Lynns fantastischem Algorithmus . Es gibt ein unsichtbares 3-Byte-Zeichen, U + F3C7 in der UTF-8-Codierung, vor dem letzten
]
. Mathematica gibt es hochgestellt wiederT
und übernimmt die Transponierung einer Matrix.Mathematica, 54 Bytes
Unbenannte Funktion, die zwei Argumente verwendet, eine positive Ganzzahl
#
und ein 2D-Array#2
mit den Dimensionen#
x#
, und ein 2D-Array mit ähnlicher Form zurückgibt. Wie im gegebenen Testfall befindet sich der Punkt mit den Koordinaten {0,0} oben links und die x-Achse ist horizontal. Einfache Implementierung mit dem[[1,-1],[-1,2]]
in der Frage erwähnten Inversen , wobei-1
in der ersten Koordinate berücksichtigt wird, dass Arrays in Mathematica von Natur aus 1-indiziert sind. Wenn wir die Dimension der Matrix nicht als zusätzliches Argument verwenden dürfen, wird diese Lösung neun Byte länger (ersetzen Sie das erste#
- nicht das#2
- mita=Length@#
und alle nachfolgenden#
s durcha
s).quelle
Python 2,
89827773 BytesDie Eingabe ist eine Liste von Listen.
Die Zeichenfolge in der Exec transponiert die Liste von Listen und dreht jede Liste zyklisch um den Zeilenindex (0 basierend - die 3. Zeile wird zweimal nach rechts gedreht).
Dieser Vorgang wird zweimal für die Eingabe ausgeführt.
+4 Bytes, die die Transformation N-mal durchführen
quelle
Haskell, 55 Bytes
Anwendungsbeispiel:
[[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
ist die obere linke Ecke. Dies verwendet die inverse Transformation.quelle
Python, 69 Bytes
Eine Verbesserung gegenüber Rods Transponierungs- und Shift-2-Methode . Wendet die Operation
M -> [r[-i:]+r[:-i]for i,r in enumerate(zip(*M))]
zweimal an, indem die Zeichenfolge erstellt und ausgewertet wirdDamit wird eine direkte Transformation (70 Byte) knapp unterbunden, vorausgesetzt, das Bild ist quadratisch und seine Länge kann als Eingabe verwendet werden:
quelle
ImageJ-Makro, 29 Byte
quelle
v=getPixel((2*y-x)%w,(x-y)%h)
.2*x+y
geändert zu2*y+x
f(x,y) = (2x+y, x+y)
diese inverse Transformation wird durch beschriebenf^(-1) = (x-y, 2y-x)
. (Mein anderer Kommentar war falsch.) Also sollte Ihr Code seinv=getPixel((x-y)%w,(2*y-x)%h)
.Java, 160
Golf gespielt:
Ungolfed:
quelle