Imagine que temos algum poliomino e gostaríamos de identificá-los exclusivamente, no entanto, os poliominos podem ser rotacionados, portanto, o hash cego não nos dará a mesma impressão digital de uma peça e uma rotação da mesma (em geral).

Por exemplo, se tivermos o L-tetromino

x
x
xx

gostaríamos que ela tivesse a mesma impressão digital que qualquer uma destas:

         xx
  x       x      xxx
xxx  ,    x  or  x

Nota: somente permitimos rotações no plano (ou seja, são poliominos unilaterais) e, portanto, o seguinte poliomino seria diferente:

 x
 x
xx 

Desafio

A tarefa para este desafio é implementar uma função / programa de impressão digital que utiliza uma matriz booleana $m\times n$ / lista de listas / string / .. codificando um polyomino e retornando uma string - a impressão digital de um polyomino . A impressão digital deve ser igual para todas as rotações possíveis (em geral 4).$0,1$

Entrada / Saída

• $m \geq 1$ e$n \geq 1$ (isto é. não Polyomino vazio)
• você tem a garantia de que são tão pequenos quanto possível (ie. todo são cortado para caber e$m,n$$0$$m$$n$
• você está garantido que a entrada é
  • simplesmente conectado
  • não tem buracos
• A saída deve ser uma sequência que seja a mesma para cada rotação possível de um poliomino

Exemplos

Aqui estão algumas classes de equivalência, para cada classe a impressão digital deve ser a mesma e, para quaisquer dois polioinos de duas classes distintas, eles devem diferir.

As rotações do L-tetromino a partir do exemplo:

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

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

A unidade polyomino:

[[1]]

Uma barra $5\times 1$ :

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

A $2\times 2$ canto:

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

Experimente online!

Toma a maior das quatro rotações em termos de comparação de lista. Baseado na solução da FlipTack .

O código usa a capacidade do Python 2 para comparar objetos de diferentes tipos. O valor do caso base de 0é inofensivo maxporque é menor que qualquer lista. Além disso, zipproduz uma lista de tuplas enquanto a entrada é uma lista de listas, mas as tuplas são maiores que as listas, portanto a lista de listas de entrada nunca é um candidato. É por isso que giramos 5 vezes em vez de 4, para voltarmos a uma versão tuplificada da lista inicial. (Fazer uma lista de tuplas também funcionaria, se essa for uma forma de entrada permitida.)

Python 3 , 63 bytes

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

Experimente online!

Encontra a rotação com o mínimo lexográfico e imprime isso.

Um formulário lambda entra na mesma contagem de bytes:

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

Experimente online!

Gelatina , 5 bytes

ZU$ƬṂ

Experimente online!

Programa completo.

Simplesmente gera todas as rotações possíveis e escolhe o mínimo lexicográfico.

Observe que as listas singleton não estão agrupadas na []saída. Isso não importa, pois o único caso em que as listas de singleton existiriam na entrada seria uma linha vertical (incluindo a unidade polyomino), que é igual a uma linha horizontal com o mesmo tamanho (onde as que não estão agrupadas) ) O único caso em que o exterior []também não existe é a unidade polyomino.

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

Experimente online!

Inclui verificador de teste.

K (ngn / k) , 16 bytes

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

Experimente online!

min de rotações

{ } função com argumento x

{+|x}rodar, ou seja, inverter ( |) e transpor ( +)

3{ }\aplicar 3 vezes preservando resultados intermediários; isso retorna uma lista das 4 rotações

a: atribuir a a

< ascender (calcular a permutação de classificação ascendente)

* primeiro

a@indexe acom isso

Japonês -g, 6 bytes

4Æ=zÃñ

Tente

           :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 graças a Shaggy

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

Experimente online!

J , 18 bytes

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

Experimente online!

Retorna o primeiro item da lista de rotações lexicograpicamente classificadas do polyomino.

Explicação:

            ^:(<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 graças a @Shaggy .

Experimente online ou verifique todos os casos de teste .

Explicação:

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)

OBSERVAÇÃO: Tomar o mínimo com ßou Wachatar implicitamente, o mesmo ocorrerá 0. E classificar com {parece não funcionar para uma lista de matrizes, e é por isso que eu uso Σ˜.