Rotación de huellas dactilares invariantes

15

Imagine que tenemos algo de poliomino y nos gustaría identificarlos de manera única, sin embargo, los poliominos se pueden rotar, por lo que el hash ciego no nos dará la misma huella digital para una pieza y una rotación de la misma (en general).

Por ejemplo si tenemos el L-tetromino

x
x
xx

nos gustaría que tuviera la misma huella digital que cualquiera de estos:

         xx
  x       x      xxx
xxx  ,    x  or  x

Nota: Solo permitimos rotaciones en el plano (es decir, son poliominos de un solo lado) y, por lo tanto, el siguiente poliomino sería diferente:

 x
 x
xx 

Desafío

La tarea para este desafío es implementar una función / programa de huellas dactilares que tome una matriz / lista de listas / cadenas / ... con valor metro×norte booleano / 0 0,1 codifique un poliomino y devuelva una cadena: la huella digital de un poliomino . La huella digital debe ser igual para todas las rotaciones posibles (en general 4).

De entrada y salida

  • metro1 ynorte1 (es decir. no polyomino vacío)
  • tiene la garantía de que metro,norte son lo más pequeño posible (es decir. todo 0 0 se recortan para que metro y norte
  • tienes garantizado que la entrada es
    • simplemente conectado
    • no tiene agujeros
  • la salida debe ser una cadena que sea igual para cada posible rotación de un poliomino

Ejemplos

Aquí hay algunas clases de equivalencia, para cada clase la huella digital debe ser la misma y para dos poliominos de dos clases distintas deben ser diferentes.

Las rotaciones del L-tetromino del ejemplo:

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

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

La unidad poliomino:

[[1]]

Una barra 5 5×1 :

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

Una esquina de 2×2 :

[[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]]
ბიმო
fuente
Relacionados .
ბიმო
Si siempre envío ""(la cadena vacía), ¿he satisfecho todos los requisitos?
Daniel Wagner
@DanielWagner: "[..] para dos poliominos de dos clases distintas [las huellas dactilares] deben diferir ", así que no, eso no sería válido.
ბიმო
¿La salida de todas las rotaciones posibles de una matriz, ordenada consistentemente, es válida? Ejemplo
Shaggy
1
@ Shaggy: Sí, eso cumpliría todos los criterios.
ბიმო

Respuestas:

7

Python 2 , 48 bytes

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

Pruébalo en línea!

Toma la mayor de las cuatro rotaciones en términos de comparación de listas. Basado en la solución de FlipTack .

El código usa la capacidad de Python 2 para comparar objetos de diferentes tipos. El valor del caso base de 0es inofensivo maxporque es más pequeño que cualquier lista. Además, zipproduce una lista de tuplas mientras que la entrada es una lista de listas, pero las tuplas son más grandes que las listas, por lo que la lista de listas de entrada nunca es un contendiente. Es por eso que rotamos 5 veces en lugar de 4, de modo que volvamos a una versión tuplificada de la lista inicial. (Tomar una lista de tuplas también funcionaría, si esa es una forma permitida de entrada).

xnor
fuente
4

Python 3 , 63 bytes

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

Pruébalo en línea!

Encuentra la rotación con el mínimo lexográfico e imprime eso.

Una forma lambda viene en el mismo número de bytes:

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

Pruébalo en línea!

FlipTack
fuente
Reescribir como lambdapuede llevarte a 58 lambda m,M=[]:exec("m=[*zip(*m[::-1])];M+=m,;"*4)or min(M).. Funciona porque execsiempre regresa None.
nedla2004
@ nedla2004 Eso solo se puede ejecutar una vez, y luego se pone poco fiable como Mya está poblado ...
FlipTack
@ nedla2004 ... pero dar cuenta del problema M[-4:]puede llevarte al mismo número de bytes.
FlipTack
Ya veo, la prueba que estaba usando solo estaba verificando entradas con el mismo "hash", así que nunca me encontré con eso. Eso tiene sentido.
nedla2004
2

Jalea , 5 bytes

ZU$ƬṂ

Pruébalo en línea!

Programa completo

Simplemente genera todas las rotaciones posibles y selecciona el mínimo lexicográfico.

Tenga en cuenta que las listas singleton no están incluidas []en la salida. Eso no importa, ya que el único caso en el que las listas singleton existirían en la entrada sería una línea vertical (incluida la unidad polyomino), que es lo mismo que una línea horizontal con el mismo tamaño (donde las que no están ajustadas) ) El único caso donde el exterior []tampoco existirá es la unidad polyomino.

Erik el Outgolfer
fuente
cuando leí el desafío supe que esto sucedería :)
ngn
2

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

Pruébalo en línea!

Incluye verificador de prueba.

Οurous
fuente
2

K (ngn / k) , 16 bytes

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

Pruébalo en línea!

min de rotaciones

{ } funcionar con argumento x

{+|x}rotar, es decir, invertir ( |) y transponer ( +)

3{ }\aplicar 3 veces conservando resultados intermedios; esto devuelve una lista de las 4 rotaciones

a: asignar a a

< ascender (calcular la permutación ascendente)

* primero

a@indexar acon eso

ngn
fuente
1

Japt -g, 6 bytes

4Æ=zÃñ

Intentalo

           :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
Lanudo
fuente
¿Es -gnecesaria la bandera? Ordenar debería significar que todas las rotaciones iniciales terminan con la misma lista, por lo que la lista completa debería funcionar bien como la huella digital a menos que me falte algo.
Kamil Drakari
@KamilDrakari, bien podría estar en lo cierto, como dije, no estoy seguro de haber entendido completamente el desafío. Sin embargo, no hay nada de malo en dejarlo, no está costando bytes.
Shaggy
@KamilDrakari: No es necesario, pero tampoco es perjudicial ya que no se cuenta para el recuento de bytes.
ბიმო
1

J , 16 bytes

-2 bytes gracias a Shaggy

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

Pruébalo en línea!

J , 18 bytes

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

Pruébalo en línea!

Devuelve el primer elemento de la lista de rotaciones ordenadas lexicográficamente del poliomino.

Explicación:

            ^:(<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
fuente
@ Shaggy Gracias!
Galen Ivanov
0

05AB1E , 10 8 bytes

3FÂø})Σ˜

-2 bytes gracias a @Shaggy .

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

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)

NOTA: Tomar el mínimo con ßo Wse aplanará implícitamente, por lo que saldrá 0. Y ordenar con {no parece funcionar para una lista de matrices, por eso lo uso Σ˜en su lugar.

Kevin Cruijssen
fuente
1
@ Shaggy Gracias! :) En ese caso, los dos últimos bytes se pueden eliminar, ya que }se hace implícitamente si no hay nada después.
Kevin Cruijssen
1
¡Hoy aprendí algo sobre 05AB1E! :) Es lo mismo en Japt.
Shaggy