Rotationsinvariantes Fingerprinting

15

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×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

  • m1 undn1 (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×1 bar:

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

Eine 2×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]]
ბიმო
quelle
Verwandte .
16.
Wenn ich immer ""(die leere Zeichenfolge) ausgegeben habe , habe ich alle Anforderungen erfüllt?
Daniel Wagner
@DanielWagner: "[..] für zwei beliebige Polyominos aus zwei verschiedenen Klassen [die Fingerabdrücke] müssen sich unterscheiden " - also nein, das wäre ungültig.
17.
Ist die Ausgabe aller möglichen Rotationen eines Arrays, konsistent sortiert, gültig? Beispiel
Shaggy
1
@ Shaggy: Ja, das würde alle Kriterien erfüllen.
ბიმო

Antworten:

7

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.)

xnor
quelle
4

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!

FlipTack
quelle
Umschreiben als lambdakann man bis 58 bekommen lambda m,M=[]:exec("m=[*zip(*m[::-1])];M+=m,;"*4)or min(M). Funktioniert da execimmer wieder None.
nedla2004
@ Nedla2004 Das kann nur einmal ausgeführt werden, und wird dann zwielichtig, wie Mbereits besiedelt ...
FlipTack
@nedla2004 ... aber M[-4:]wenn man das Problem mit berücksichtigt, kann man auf die gleiche Byteanzahl kommen.
FlipTack
Ich sehe, der Test, den ich verwendete, überprüfte nur Eingaben mit dem gleichen "Hash", also bin ich nie darauf gestoßen. Das macht Sinn.
nedla2004
2

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.

Erik der Outgolfer
quelle
Als ich die Herausforderung las, wusste ich, dass dies passieren würde :)
ngn
2

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.

Οurous
quelle
2

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

ngn
quelle
1

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
Zottelig
quelle
Ist die -gFlagge notwendig? Sortieren sollte bedeuten, dass alle anfänglichen Rotationen mit derselben Liste enden, sodass die vollständige Liste als Fingerabdruck gut funktionieren sollte, es sei denn, mir fehlt etwas.
Kamil Drakari
@KamilDrakari, Sie könnten gut Recht haben - wie gesagt, ich bin mir nicht sicher, ob ich die Herausforderung vollständig verstanden habe. Es schadet aber nicht, es zu belassen, es kostet keine Bytes.
Shaggy
@KamilDrakari: Es ist nicht notwendig, aber es schadet auch nicht, da es nicht zum bytecount gezählt wird.
ბიმო
1

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  
Galen Ivanov
quelle
@ Shaggy Danke!
Galen Ivanov
0

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.

Kevin Cruijssen
quelle
1
@ Shaggy Danke! :) In diesem Fall können die letzten beiden Bytes entfernt werden, da das }implizit gemacht wird, wenn nichts danach kommt.
Kevin Cruijssen
1
Heute habe ich etwas über 05AB1E gelernt! :) In Japt ist es dasselbe.
Shaggy