Odcisk palca niezmiennie rotacyjny

15

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

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

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

2)×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]]
ბიმო
źródło
Związane .
ბიმო
Jeśli zawsze wysyłam dane wyjściowe ""(pusty ciąg), czy spełniłem wszystkie wymagania?
Daniel Wagner,
@DanielWagner: „[...] dla dwóch dowolnych poliamoli z dwóch różnych klas [odciski palców] muszą się różnić ” - więc nie, to byłoby nieprawidłowe.
ბიმო
Czy wyprowadzanie wszystkich możliwych obrotów tablicy, konsekwentnie sortowanych jest prawidłowe? Przykład
Kudłaty
1
@Shaggy: Tak, to spełni wszystkie kryteria.
ბიმო

Odpowiedzi:

7

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

xnor
źródło
4

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!

FlipTack
źródło
Przepisywanie jako lambdamoże doprowadzić cię do 58 lambda m,M=[]:exec("m=[*zip(*m[::-1])];M+=m,;"*4)or min(M).. Działa, ponieważ execzawsze powraca None.
nedla2004
@ nedla2004 To może być uruchomione tylko raz, a następnie robi się podejrzane, ponieważ Mjest już zaludnione ...
FlipTack
@ nedla2004 ... ale uwzględnienie problemu z M[-4:]może doprowadzić do takiej samej liczby bajtów.
FlipTack,
Rozumiem, że test, którego użyłem, polegał tylko na sprawdzeniu danych wejściowych przy użyciu tego samego „skrótu”, więc nigdy na to nie wpadłem. To ma sens.
nedla2004
2

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.

Erik the Outgolfer
źródło
kiedy przeczytałem wyzwanie, wiedziałem, że tak się stanie :)
ngn
2

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.

Obrzydliwe
źródło
2

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

ngn
źródło
1

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
Kudłaty
źródło
Czy -gflaga jest konieczna? Sortowanie powinno oznaczać, że wszystkie początkowe obroty kończą się na tej samej liście, więc pełna lista powinna działać dobrze jak odcisk palca, chyba że coś mi brakuje.
Kamil Drakari,
@KamilDrakari, możesz mieć rację - tak jak powiedziałem, nie jestem pewien, czy w pełni zrozumiałem wyzwanie. Jednak nie ma w tym nic złego, nie kosztuje to żadnych bajtów.
Kudłaty
@KamilDrakari: Nie jest to konieczne, ale nie szkodzi, ponieważ nie jest wliczane do liczby bajtów.
ბიმო
1

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  
Galen Iwanow
źródło
@Shaggy Thanks!
Galen Iwanow,
0

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 .

Kevin Cruijssen
źródło
1
@Shaggy Thanks! :) W takim przypadku można usunąć dwa ostatnie bajty, ponieważ }robi się to domyślnie, jeśli nic po nim nie nastąpi.
Kevin Cruijssen,
1
Dzisiaj dowiedziałem się czegoś o 05AB1E! :) Tak samo jest w Japt.
Kudłaty