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 booleano / 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
- y (es decir. no polyomino vacío)
- tiene la garantía de que son lo más pequeño posible (es decir. todo se recortan para que y
- 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 :
[[1,1,1,1,1]]
[[1],[1],[1],[1],[1]]
Una esquina de :
[[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]]
""
(la cadena vacía), ¿he satisfecho todos los requisitos?Respuestas:
Python 2 , 48 bytes
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
0
es inofensivomax
porque es más pequeño que cualquier lista. Además,zip
produce 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).fuente
Python 3 , 63 bytes
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:
Pruébalo en línea!
fuente
lambda
puede llevarte a 58lambda m,M=[]:exec("m=[*zip(*m[::-1])];M+=m,;"*4)or min(M)
.. Funciona porqueexec
siempre regresaNone
.M
ya está poblado ...M[-4:]
puede llevarte al mismo número de bytes.Jalea , 5 bytes
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.fuente
Limpio , 136 bytes
Pruébalo en línea!
Incluye verificador de prueba.
fuente
K (ngn / k) , 16 bytes
Pruébalo en línea!
min de rotaciones
{
}
funcionar con argumentox
{+|x}
rotar, es decir, invertir (|
) y transponer (+
)3{
}\
aplicar 3 veces conservando resultados intermedios; esto devuelve una lista de las 4 rotacionesa:
asignar aa
<
ascender (calcular la permutación ascendente)*
primeroa@
indexara
con esofuente
Japt
-g
, 6 bytesIntentalo
fuente
-g
necesaria 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.J , 16 bytes
-2 bytes gracias a Shaggy
Pruébalo en línea!
J , 18 bytes
Pruébalo en línea!
Devuelve el primer elemento de la lista de rotaciones ordenadas lexicográficamente del poliomino.
Explicación:
fuente
05AB1E ,
108 bytes-2 bytes gracias a @Shaggy .
Pruébelo en línea o verifique todos los casos de prueba .
Explicación:
NOTA: Tomar el mínimo con
ß
oW
se 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.fuente
}
se hace implícitamente si no hay nada después.