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ą Boolean / -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
- i (tj. nie jest pusty Polyomino)
- masz pewność, że są tak małe, jak to możliwe (tzn. wszystkie są przycięte, aby pasowały do i
- 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 :
[[1,1,1,1,1]]
[[1],[1],[1],[1],[1]]
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]]
""
(pusty ciąg), czy spełniłem wszystkie wymagania?Odpowiedzi:
Python 2 , 48 bajtów
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
0
jest nieszkodliwa,max
ponieważ jest mniejsza niż jakakolwiek lista. Ponadto,zip
tworzy 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).źródło
Python 3 , 63 bajty
Wypróbuj online!
Znajduje obrót z minimum leksykalnym i drukuje to.
Forma lambda występuje w tej samej liczbie bajtów:
Wypróbuj online!
źródło
lambda
może doprowadzić cię do 58lambda m,M=[]:exec("m=[*zip(*m[::-1])];M+=m,;"*4)or min(M)
.. Działa, ponieważexec
zawsze powracaNone
.M
jest już zaludnione ...M[-4:]
może doprowadzić do takiej samej liczby bajtów.Galaretka , 5 bajtów
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.źródło
Czysty , 136 bajtów
Wypróbuj online!
Obejmuje weryfikator testu.
źródło
K (ngn / k) , 16 bajtów
Wypróbuj online!
min obrotów
{
}
funkcja z argumentemx
{+|x}
rotate, tj. reverse (|
) i transpose (+
)3{
}\
zastosować 3 razy zachowując wyniki pośrednie; zwraca listę 4 obrotówa:
Przypisać doa
<
ascend (oblicz permutację sortującą rosnąco)*
pierwszya@
indeksuja
z tymźródło
Japt
-g
, 6 bajtówSpróbuj
źródło
-g
flaga 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.J , 16 bajtów
-2 bajty dzięki Shaggy
Wypróbuj online!
J , 18 bajtów
Wypróbuj online!
Zwraca pierwszy element z listy posortowanych leksykograficznie obrotów poliomino.
Wyjaśnienie:
źródło
05AB1E ,
108 bajtów-2 bajty dzięki @Shaggy .
Wypróbuj online lub sprawdź wszystkie przypadki testowe .
Wyjaśnienie:
UWAGA: Biorąc minimum z
ß
lubW
domyś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 .źródło
}
robi się to domyślnie, jeśli nic po nim nie nastąpi.