Stellen Sie sich vor, wir haben ein Polyomino und möchten es eindeutig identifizieren, aber die Polyominos können gedreht werden, so dass sie blindlings nicht den gleichen Fingerabdruck für ein Stück und eine Drehung davon (im Allgemeinen) ergeben.

Zum Beispiel, wenn wir den L-Tetromino haben

x
x
xx

Wir möchten, dass es den gleichen Fingerabdruck wie die folgenden hat:

         xx
  x       x      xxx
xxx  ,    x  or  x

Hinweis: Wir erlauben nur Rotationen in der Ebene (dh es handelt sich um einseitige Polyominos) und daher wäre das folgende Polyomino ein anderes:

 x
 x
xx 

Herausforderung

Die Aufgabe für diese Herausforderung ist eine Abnahme von Fingerabdrücken-Funktion / Programm zu implementieren , die eine nimmt $m\times n$ Boolean / $0,1$ -wertigen Matrix / Liste von Listen / string / .. Codieren eines polyomino und gibt einen String - den Fingerabdruck eines polyomino . Der Fingerabdruck muss für alle möglichen Rotationen gleich sein (in der Regel 4).

Input-Output

• $m \geq 1$ und$n \geq 1$ (dh kein leeres Polyomino)
• Sie haben die Garantie, dass $m,n$ so klein wie möglich ist (dh alle $0$ werden auf $m$ und n zugeschnitten)$n$
• Ihnen wird garantiert, dass der Eingang ist
  • einfach verbunden
  • hat keine Löcher
• output muss eine Zeichenfolge sein, die für jede mögliche Drehung eines Polyominos gleich ist

Beispiele

Hier sind einige Äquivalenzklassen: Für jede Klasse muss der Fingerabdruck derselbe sein und für zwei beliebige Polyominos aus zwei verschiedenen Klassen müssen sie sich unterscheiden.

Die Drehungen des L-Tetrominos aus dem Beispiel:

[[1,0],[1,0],[1,1]]
[[0,0,1],[1,1,1]]
[[1,1],[0,1],[0,1]]
[[1,1,1],[1,0,0]]

Der J-Tetromino:

[[0,1],[0,1],[1,1]]
[[1,1,1],[0,0,1]]
[[1,1],[1,0],[1,0]]
[[1,0,0],[1,1,1]]

Die Einheit Polyomino:

[[1]]

A $5\times 1$ bar:

[[1,1,1,1,1]]
[[1],[1],[1],[1],[1]]

Eine $2\times 2$ Ecke:

[[1,1],[1,0]]
[[1,0],[1,1]]
[[0,1],[1,1]]
[[1,1],[0,1]]

W-Pentomino:

[[1,0,0],[1,1,0],[0,1,1]]
[[0,0,1],[0,1,1],[1,1,0]]
[[1,1,0],[0,1,1],[0,0,1]]
[[0,1,1],[1,1,0],[1,0,0]]

Python 2 , 48 Bytes

f=lambda l,z=5:z and max(l,f(zip(*l)[::-1],z-1))

Probieren Sie es online!

Nimmt die größte der vier Umdrehungen in Bezug auf den Listenvergleich ein. Basierend auf der FlipTack-Lösung .

Der Code verwendet die Fähigkeit von Python 2, Objekte verschiedener Typen zu vergleichen. Der Basisfallwert von 0ist harmlos, maxweil er kleiner als jede Liste ist. Außerdem ziperzeugt eine Liste von Tupeln , während die Eingabe eine Liste von Listen, aber Tupel größer ist als Listen , damit die Eingabeliste-of-Listen sind nie ein Anwärter. Aus diesem Grund drehen wir uns fünfmal anstatt viermal, sodass wir zu einer vervielfältigten Version der ursprünglichen Liste zurückkehren. (Das Aufnehmen einer Liste von Tupeln würde auch funktionieren, wenn dies eine zulässige Form der Eingabe ist.)

Python 3 , 63 Bytes

def f(m):M=[];exec("m=[*zip(*m[::-1])];M+=m,;"*4);return min(M)

Probieren Sie es online!

Findet die Rotation mit dem lexografischen Minimum und druckt diese aus.

Eine Lambda-Form kommt mit der gleichen Anzahl von Bytes:

lambda m,M=[]:exec("m=[*zip(*m[::-1])];M+=m,;"*4)or min(M[-4:])

Probieren Sie es online!

Gelee , 5 Bytes

ZU$ƬṂ

Probieren Sie es online!

Volles Programm.

Erzeugt einfach alle möglichen Rotationen und wählt das lexikografische Minimum aus.

Beachten Sie, dass Singleton-Listen []in der Ausgabe nicht eingeschlossen sind. Dies spielt keine Rolle, da der einzige Fall, in dem Singleton-Listen in der Eingabe vorhanden wären, eine vertikale Linie (einschließlich der Einheit Polyomino) ist, die mit einer horizontalen Linie mit derselben Größe (in der die Listen nicht umbrochen sind) identisch ist ). Der einzige Fall, in dem das Äußere []auch nicht existiert, ist die Einheit Polyomino.

Sauber , 136 Bytes

import StdEnv,Data.List
r=reverse;t=transpose;f=flatten
$l=[if((a==b)==(c==d))'x''X'\\a<-f l&b<-f(r(map r l))&c<-f(r(t l))&d<-f(t(r l))]

Probieren Sie es online!

Beinhaltet Testverifizierer.

K (ngn / k) , 16 Bytes

{a@*<a:3{+|x}\x}

Probieren Sie es online!

min Umdrehungen

{ } Funktion mit Argument x

{+|x}drehen, dh umkehren ( |) und transponieren ( +)

3{ }\dreimal auftragen, dabei Zwischenergebnisse erhalten; Dies gibt eine Liste der 4 Umdrehungen zurück

a: zuweisen a

< ascend (berechne die sortiere aufsteigende Permutation)

* zuerst

a@Index adamit

Japt -g, 6 Bytes

4Æ=zÃñ

Versuch es

           :Implicit input of 2d-array U
4Æ         :Map the range [0,4)
   z       :  Rotate U 90 degrees
  =        :  Reassign to U
    Ã      :End map
     ñ     :Sort
           :Implicit output of first element

J , 16 Bytes

-2 Bytes dank Shaggy

[:/:~|.@|:^:(<4)

Probieren Sie es online!

J , 18 Bytes

0{[:/:~|.@|:^:(<4)

Probieren Sie es online!

Gibt das erste Element in der Liste der lexikographisch sortierten Rotationen des Polyominos zurück.

Erläuterung:

            ^:(<4)  - do the verb on the left 4 times, storing all the steps
       |.@|:        - tranpose and reverse
    /:~             - sort up the 4 matrices
  [:                - cap the fork
0{                  - take the first matrix  

05AB1E , 10 8 Bytes

3FÂø})Σ˜

-2 Bytes dank @Shaggy .

Probieren Sie es online aus oder überprüfen Sie alle Testfälle .

Erläuterung:

3F  }       # Loop 3 times
  Â         #  Bifurcate (short for Duplicate & Reverse) the top of the stack
            #  (which is the input-matrix implicitly the first iteration)
   ø        #  Transpose: swap rows/columns
     )      # After the loop, wrap everything on the stack in a list
      Σ˜    # Sort this list of matrices by their flattened array (and output implicitly)

HINWEIS: Wenn Sie das Minimum mit ßoder Wnehmen, wird die Ausgabe implizit abgeflacht 0. Und das Sortieren mit {scheint für eine Liste von Matrizen nicht zu funktionieren, weshalb ich Σ˜stattdessen verwende.