Wyobraźmy sobie, że mamy poliomino i chcielibyśmy je jednoznacznie zidentyfikować, jednak poliaminy można obracać, więc ślepe ich haszowanie nie da nam tego samego odcisku palca dla kawałka i jego obrotu (ogólnie).

Na przykład, jeśli mamy L-tetromino

x
x
xx

chcielibyśmy mieć taki sam odcisk palca, jak którykolwiek z tych:

         xx
  x       x      xxx
xxx  ,    x  or  x

Uwaga: Dopuszczamy tylko obroty na płaszczyźnie (tzn. Są to jednostronne poliaminy), dlatego następujący poliomino byłby inny:

 x
 x
xx 

Wyzwanie

Zadaniem tego wyzwania jest zaimplementowanie funkcji / programu do pobierania odcisków palców, który pobiera macierz logiczną $m\times n$ Boolean / $0,1$ -wartość / listę list / ciąg / .. kodującą polyomino i zwraca ciąg znaków - odcisk palca polyomino . Odcisk palca musi być taki sam dla wszystkich możliwych obrotów (ogólnie 4).

Wejście wyjście

• $m \geq 1$ i$n \geq 1$ (tj. nie jest pusty Polyomino)
• masz pewność, że $m,n$ są tak małe, jak to możliwe (tzn. wszystkie $0$ są przycięte, aby pasowały do $m$ i $n$
• masz gwarancję, że dane wejściowe są
  • po prostu podłączony
  • nie ma dziur
• wyjście musi być ciągiem, który jest taki sam dla każdego możliwego obrotu poliomino

Przykłady

Oto niektóre klasy równoważności, dla każdej klasy odcisk palca musi być taki sam, a dla dowolnych dwóch wielomianów z dwóch różnych klas muszą się różnić.

Obroty L-tetromino z przykładu:

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

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

Jednostka poliomino:

[[1]]

Pasek $5\times 1$ :

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

$2\times 2$ narożnik:

[[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 bajtów

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

Wypróbuj online!

Zajmuje największą z czterech rotacji pod względem porównania list. Oparty na rozwiązaniu FlipTack .

Kod wykorzystuje zdolność Pythona 2 do porównywania obiektów różnych typów. Podstawowa wartość przypadku 0jest nieszkodliwa, maxponieważ jest mniejsza niż jakakolwiek lista. Ponadto, ziptworzy listę krotek podczas gdy wejście jest lista list, ale są większe niż krotki list więc wejście list-z-listy nigdy nie jest kandydatem. Właśnie dlatego obracamy 5 razy zamiast 4, abyśmy wrócili do ulepszonej wersji początkowej listy. (Przyjęcie listy krotek również by działało, jeśli jest to dozwolona forma wprowadzania danych).

Python 3 , 63 bajty

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

Wypróbuj online!

Znajduje obrót z minimum leksykalnym i drukuje to.

Forma lambda występuje w tej samej liczbie bajtów:

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

Wypróbuj online!

Galaretka , 5 bajtów

ZU$ƬṂ

Wypróbuj online!

Pełny program

Po prostu generuje wszystkie możliwe obroty i wybiera minimum leksykograficzne.

Zauważ, że listy singletonów nie są zawijane w []wyniku. To nie ma znaczenia, ponieważ jedynym przypadkiem, w którym na wejściu istniałyby listy singletonów, byłaby linia pionowa (w tym jednostka poliomino), która jest taka sama jak linia pozioma o tym samym rozmiarze (gdzie te nie są zawijane ). Jedynym przypadkiem, w którym zewnętrzna []również nie będzie istniała, jest jednostka poliomino.

Czysty , 136 bajtów

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

Wypróbuj online!

Obejmuje weryfikator testu.

K (ngn / k) , 16 bajtów

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

Wypróbuj online!

min obrotów

{ } funkcja z argumentem x

{+|x}rotate, tj. reverse ( |) i transpose ( +)

3{ }\zastosować 3 razy zachowując wyniki pośrednie; zwraca listę 4 obrotów

a: Przypisać do a

< ascend (oblicz permutację sortującą rosnąco)

* pierwszy

a@indeksuj az tym

Japt -g, 6 bajtów

4Æ=zÃñ

Spróbuj

           :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 bajtów

-2 bajty dzięki Shaggy

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

Wypróbuj online!

J , 18 bajtów

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

Wypróbuj online!

Zwraca pierwszy element z listy posortowanych leksykograficznie obrotów poliomino.

Wyjaśnienie:

            ^:(<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 bajtów

3FÂø})Σ˜

-2 bajty dzięki @Shaggy .

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

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)

UWAGA: Biorąc minimum z ßlub Wdomyślnie spłaszcza się, więc będzie generować 0. A sortowanie za pomocą {nie wydaje się działać dla listy macierzy, dlatego Σ˜zamiast tego używam .